实体关系标注工具最佳实践

　　＂  如果你有机会采访一下 AI 算法工程师，什么是机器学习中最重要的事儿？
　　他们大概率会咆哮着告诉你：数据！数据！数据！
　　如何获得高质量的标注数据？如何提高标注同学的工作效率？是每个 AI 团队最重要的思考之一。
　　本文向大家详细阐述了来也科技 AI 研发中心在实现 ＂实体关系标注工具＂ 上的最佳实践。
　　＂
　　首先，为了您能顺利理解本文内容，对常见的技术名词说明如下：
　　NLP ：Natural Language Processing 自然语言处理
　　实体关系 ：见下图
　　数据标注 ：数据标注即通过分类、画框、标注、注释等，对图片、语音、文本等数据进行处理，标记对象的特征，以作为机器学习的基础素材。
　　标注数据的流转 ：见下图
　　背景
　　对话机器人是来也科技的当家产品之一。对话机器人的核心能力之一就是自然语言处理（NLP），而标明实体关系的数据则是提升 NLP 能力的重要输入。
　　来也科技在标注实例关系数据上，历经了 3 个阶段：  借助 Excel 标注数据  使用市面上现有的标注工具  自主研发标注工具
　　Excel 标注
　　Excel 标注的缺点是显而易见的：
　　操作、协同不便  所有关系维护在一个表格中，需要手动查找及复制  不方便多人操作统一数据集，且容易误操作  共享表格，权限无法细化  标注状态、审核状态等不方便维护
　　市面上的标注工具（我们以百度大脑举例）
　　这个工具相较 Excel 有很明显的优点：  通过刷选文本取代过去复制粘贴文本的标注方式  通过共享实体和实体类型取代过去靠成员间约定的维护方式  通过高亮文本并添加指示线取代在原文档中大海捞针的审核方式  各实体持有关系数展示  点击标注结果时会用虚线指向2个实体
　　但也有不满足我们需求的地方：  同一段文本不能被标为多种实体：实际业务场景中同段文本可能需要被拆分成多个实体，彼此之间创建实体关系。如图：
　　跨行标注时会扰乱原本的文本结构，影响标注体验。如图：
　　查看实体关系的实体高亮不明显，实体间的虚线可能会被文本遮盖，实际作用不大  标注时不能创建实体类型和关系类型，需要到另一个页面编辑，但我们希望可以不要切换
　　自主研发
　　在此背景下，我们决定研发自己的实体关系标注工具。除了基本的标注需求外，我们还抽象出以下几点重点需求：
　　标注页面可以实时维护类型信息  同段文本可标注为多个实体  分行排版  获取字符位置  跨行实体不会被拆成单独的一行
　　来也科技实体关系标注工具实践
　　通过对需求的反复分析，我们确定了实体关系标注工具的目标使用方式：
　　标注页面可以实时维护类型信息
　　这是比较简单的需求，我们只需要在标注页面添加类型维护，并且使其在更新后可以立刻投入使用即可。
　　同段文本可标注为多个实体
　　我们的需求是，同一段文字可被多次标注。如下图：
　　这个需求比较具有挑战性，且当前业内并没有一套可参照的方案满足我们的业务场景。
　　通过调研分析，我们发现：一段文本之所以无法被标注为多个实体，是因为现有的标注方式是在已有的文本元素上添加样式，不论是背景色、下划线，其本质都是在利用原本的文本元素。
　　因为 DOM 元素的固有限制，一段文本最多只能对应一种背景色，以及一种下划线。
　　要想让一段文本可以被标注为多个实体，那么文本和标注肯定不是 一个  DOM 元素。所以，我们采取＂引入额外线段＂的方式来表示标注，并通过＂绝对定位＂定位到文本下方。这样，一段文本就可以对应多个标注了。
　　我们需要准确的获取标注文本的位置信息。可并没有现成的组件，能够返回指定字符在给定文本中的具体位置。
　　所以，我们就自己实现了一个文字排版容器：  把文本逐字填入容器，当超过容器宽度时，就将文本放入下一行。  选中的文本宽度可以通过 DOM 属性 offsetWidth 直接获取。
　　，时长 00:08
　　伪代码如下：  function breakIntoLines(str, width) {     // 获取测试宽度的span，该span继承标注工具的文字样式     const span = getTestSpanInstance();       // 分行信息     const lines = [];       // 当前行的文本     let tokens = ＂＂;     // 当前行行首在str中的index     let stIndex = 0;       // 遍历字符串     while (str.length) {         // 判断当前文本再加一个字符会不会超宽         span.innerText = tokens + str[0];           // 如果超宽，就将之前的文本放入分行信息中，超出部分单起一行         if(span.offsetWidth >= width) {             lines.push({                 stIndex,                 tokens,             });             stIndex += tokens.length;             tokens = str[0];         }         // 如果未超宽，则将该字符添加到当前行         else {             tokens += str[0];         }           // 吐出被插入的字符         str = str.slice(1);     }       // 插入最后一行     if(tokens) {         lines.push({             stIndex,             tokens,         })     }       return lines; }
　　获取字符位置
　　如何对标注的数据进行展示呢？  横向偏移量计算：每行分完，通过计算文字的宽度即可获取标注的横向偏移量  纵向偏移量计算：判断是否与已处理完成的标注重叠，计算纵向偏移量
　　function injectMarksIntoLines (lines, marks) {     for(let line of lines) {         // 获取每行内的标注         for(let mark of marks) {             if(isMarkInLine(mark, line) {                 line.marks = line.marks ? line.marks.concat(mark) : [mark]             }         }           // 根据重叠数量，确定每个标注的垂直偏移量         line.marks = line.marks.map((mark, i, arr) => {             let y = 0;             for(let j = 0; j < i; j++) {                 if(isOverlap(mark, arr[j])) {                     y++;                 }             }             return {                 ...mark,                 y,             }         })     } }
　　跨行实体不会被拆成单独的一行
　　市面上的工具在标注跨行文本时，会因为标注不能拆分为多行，而将标注的文字机械化的放在同一行，这就造成了两个问题：
　　不必要的分行  文本一行展示不下时，超宽内容不可见
　　这样的处理方式，会使得文本难以阅读。如下图所示：
　　来也科技自主研发的标注工具，已经摆脱通过文本样式实现标注这种枷锁，我们可以将一个标注拆成多个 DOM 元素。
　　只要标注的全部或部分内容在当前行，就可以在本行标注文本下展示标注组件，彻底解决跨行文本被拆分的这个问题。
　　function injectMarksIntoLines(str, width) {     // ...             if(isMarkInLine(mark, line) {                 mark.stIndex = Math.max(line.stIndex, mark.stIndex);                 mark.endIndex = Math.min(line.endIndex, mark.endIndex);                   line.marks = line.marks ? line.marks.concat(mark) : [mark]             }     // ... }
　　优化
　　渲染时间过长
　　当标注文本较多时，首屏渲染时会出现较长的白屏时间。且文本字数、标注数量越多，白屏时间越长。
　　我们以一段500字左右的文本为例，获取其性能数据：
　　结合performance和代码进行分析，我们发现耗能主要在以下两方面：
　　分行算法会频繁获取   offsetWidth   ：每调用一次，都会导致页面重排，严重耗时；  计算标注纵向偏移量时，会先遍历全部标注，过滤出在当前行的标注，然后进行遍历，得到重叠高度信息，遍历次数过高；
　　我们来逐一优化。
　　分行算法优化
　　按照上文描述，初版的分行算法时间复杂度为 O(n) ，n 为文本字数。我们着重考虑通过减少调用次数来实现性能优化。通过实际观察实际应用场景，我们得出以下结论：  每行文本的字数相差不多，因为中文字的宽度相同，导致字数差异的是数字、字母等；  中文业务场景中数字和字母远没有中文字数多；  即使在最小的屏幕上展示，每行最少也有30个字符；
　　基于这些信息，我们做出如下优化：
　　处理第一行时，我们不再逐字测宽，而是直接截取前30个字符测宽，多退少补直至宽度正确；  记录第一行的字数，作为下一行期望的字数 except，多退少补直至正确；  记录新的一行的字数 n，修正except = ( except + n ) / 2 。重复此步骤，直至文本分行结束
　　结果对比：
　　优化前
　　优化后
　　渲染 500 字  233.29 ms
　　79.5 ms
　　渲染 2 万字  11232ms
　　91ms
　　可见优化效果显著。
　　获取标注位置算法优化
　　在展示标注结果时，初版获取标注纵向偏移的算法为：检查所有标注数据后，过滤出本行标注进行展示，复杂度为 O(l * n * n)，其中 l 为行数，n 为标注数。
　　此方式引入了很多不必要的计算。其实，要获取每个标注的垂直偏移量，只需要对比当前行的标注即可。
　　针对这个问题，优化思路如下：
　　将标注按起始位置升序排列。假设第一行有30个字，那么我们就从升序数组中拿出起始位置小于30的，这就是本行要添加的标注。  判断这些标注是否重叠。假设用户添加了两个标注：  如果二者不重叠，那二者应该展示在一行；  如果二者重叠，那么就要将后处理的标注放在前者的下一行；  遍历数组，把在本行结束的标注剔除。保证每行展示的标注，要么是上一行没有结束的，要么是在本行开始的。
　　伪代码如下：  function getMarkPosition(lines, marks) {     // 起始位置升序     const stIndexArr  = marks.sort((a, b) => a.stIndex  - b.stIndex);     const st = 0;       // 本行需要添加的标注     let current = [];       for (let line of lines) {         // 获取当前行的标注         while(stIndexArr[st].stIndex <= line.endIndex) {             current.push(stIndexArr[st]);             st++;         }           // 获取标注         mark.offsetX = getTextLength(line.text.slice(0, mark.stIndex - line.stIndex))         // 添加标注行         addMarkLines(line, current);           // 剔除本行结束的标注         current = current.filter(oldMark => oldMark.endIndex > line.endIndex);     } }   // 添加标注行 function addMarkLines (line, marks) {     const markLines = [[]];     let inserted = false;       // 遍历所有标注         marks.forEach(mark => {         // 遍历所有行         for(let i = 0; i < markLines.length; i++) {             // 如果本行没有和新标注重叠的，则放入本行             if(!markLines[i].find(oldMark => isOverlap(oldMark, mark))) {                 mark.offsetY = i;                 markLines.push(mark);                 inserted = true;                 break;             }         }           // 如果所有行都重叠，则单开一行                 if(!inserted) {             mark.offsetY = markLines.length;             markLines.push([mark]);         }     })       line.markLines = markLines; }
　　总结
　　实体关系标注工具在来也科技内部已经上线半年。至今日，公司内部全部的 NLP 标注需求已全部接入。标注文档超过 3 万篇，标注效率提升 35%，标注准确率提升至 96.8% 。
　　本文作者：贾思齐
　　来源:微信公众号: 来也技术团队
　　出处:https://mp.weixin.qq.com/s/mXfGtyTtbbjq-v2KB5ryHw