语言信息处理-文本相似度相关研究

1、1 引言出于个人对语言信息处理相关内容的兴趣，对两段文本之间如何比较相似性也有很大的好奇，在之前的工作中也用到相关知识，于是在本次的报告中，根据自己的能力实现了一个可以比较两段文本相似程度的小算法，算法原理简单，只是从“词”的角度进行分析，没有加入语义的分析，但是如果在特定的领域也会有不错的效果。报告中会主要介绍算法的原理、自己在原理上进行的处理以及成果的展示。2 算法思想本文所研究的算法是基于文本相似度匹配而实现的。首先将文本处理成为相对应的向量，根据空间里向量的相近程度来反映出两个文本之间的相似度。由于文本数据具有无结构的特性，需要对其进行一定的预处理，这样才能转换成为数值计算。本文所采用

2、的思路是首先对文本进行中文分词处理，然后对分词之后的结果进行词频统计，统计时可以同时完成对数据的降维操作。将统计结果排列成为两个向量，最后利用向量计算的相关公式进行相似度计算。其总体流程如图1所示。图1算法流程图3 基于文本相似度匹配的文本匹配算法3.1文本分词一整段的文本由多个词语组成，我们要进行文本之间相似度匹配的检测。第一步是对文本进行中文分词，分成一些关键的词语组，其中要剔除掉语意词、助词等等对文章大意没有影响的词汇。英文分词是相对容易的，因为每两个单词之间会有空格进行区分，这就使得分词工作变成了检测文章中的空格，然后加以分割。但中文句子并没有这样的特征，一个词汇是由多个汉字组成，而且

3、有可能出现一个字与前后两个字都能组成词语的情况，需要根据语境进行判定区分，所以中文的分词技术相对来说要难很多。但目前中文分词技术也日渐成熟，出现了很多强大的中文分词工具，也提供了很多不能编程语言的接口。单字分词、二分法和词典分词是目前分词的主要方法。 单字分词，顾名思义即在对中文文本进行分词时，以字为单位进行切分。字索引很灵活，但是实现单字匹配算法却很复杂，也往往需要大量的CPU运算进行支撑。二分法，即将每两个字当作一个词语进行切分，然后建立索引，使用二分法可以明显地减少每个词条后位置信息的长度。 在进行了对比分析之后，词典分词的方法最为适合本系统的需要。词典分词的基本思想是先构造出一个基本词

4、汇的词典，然后将遇到的文本同词典比对分析进行分词，这是当前相对准确的方法，也被广泛使用。本文使用的时Ansj中文分词，是一个基于google语义模型+条件随机场模型的中文分词的java实现，词速度达到每秒钟200万字左右，准确率能达到96%以上,目前实现了中文分词、中文姓名识别、用户自定义词典等功能,可以应用到自然语言处理等方面,适用于对分词效果要求高的各种项目。在文本中匹配单词时，正向最大匹配算法和逆向最大匹配法是词典分词法经常用到的算法，从左侧开始依次读入数据，尝试把几个连续出现的字符与词库中存在的词条进行匹配，如果成功，就可以分出一个词条，这是正向，而逆向是从文本的末端开始，每次都取最末

5、端连续出现的几个字符进行匹配，如果匹配失败，那么加入该字段最前面的一个字，继续进行匹配Error! Reference source not found.。当文本比较复杂，需要比较精确的分词的时候，就要用多种方式对文本进行切分，对不同方式的切分结果进行比对，相同的切分结果得到的词语就是真正需要的词。3.2词频统计与数据降维 上文中我们提到了要用到每个词条的出现的次数，那么就需要进行词频统计，也就是词条频率，用来评价一个词对于一段文本的重要性。 在信息领域，基于匹配的词频统计算法和基于树结构的词频统计算法是最为经典也是最被认可的词频统计方法，被广泛使用。 在单关键词

6、匹配算法中，比较著名的有BF算法、KMP算法、BM算法等。 （1）BF算法 BF算法也被称为是蛮力算法，它的基本思想是：首先，A1和B1比较，如果相等，再对A2和B2进行比较，一直到Bm为止；如果A1和B1不相等，则B右移一下，继续进行比较。如果存在k，1kn，且Ak+1k+m=T1m，则匹配成功，否则失败。 （2）KMP算法 KMP算法是由高德纳（Donald Ervin Knuth）和 Vaughan Pratt 在1977年合作发明的。其基本思想为：如果在匹配的进程中，判断Ai和Bj是否相等，如果相

7、等，那么继续对Ai+1和Bj+1进行判断；如果两者不相等，讨论一下两种情况，若j=1，向右移动，判断Ai+1和B1相等与否，若1<j<=m，则右移j-next(j)位，检查Ai和Bnext(j)是否匹配，重复此过程直到j=m或i=n结束。 （3）BM算法 BM算法1977年由Bob Boyer 和J Strother Moore提出，是一个字符串匹配算法。其基本思想是：设定一个位置i，将主串i起由左至右的进行判断，若发现不相等，则下次应从主串的i + distance(si)位置开始继续进行接下去的判断

8、，即跳过distance(si)个字符而无需进行比较。 （4）本文使用的算法基于匹配的词频统计方法，是在对待处理文本进行多次了扫描的基础上进行的，需要付出大量的时间和空间代价，尤其在文本数据量较大时，则更难以实现。针对这个难点，提出了基于树结构的算法来对词条进行统计。其基本思想是：首先根据已有的关键词集合构建一棵查找树，然后利用这个查找树对文档进行扫描，从而进行关键词的统计。利用树形结构的好处是，在统计时，对文本进行一次扫描就可以完成一个词与查找树的比较，进而可统计出所有的词条信息。利用树形结构大大减少了不必要的匹配过程，提高了统计效率。本系统在借助HashMap的基础上进行词条的频

9、率统计，这种方式相对更加简单明了，易于理解和使用。其基本思想是：利用HashMap，把关键字设置成词条，其value等于该词条出现的次数。对已经分词完毕的文本逐个词条地进行分析，先进行判断，如果该词条不存在于HashMap，那么就将该词条加入其中，并将其value设置为1；如果词条已经存在于HashMap，就将该词条的value加1，进行一个算法复杂度为O（n）的操作之后，就可以将整个文本的词频统计出来。具体算法如算法1所示。算法1 词频统计算法输入： 文本分词结果的list  HashMap hm=new HashMap()；/初始化一个HashMapwhile(list

10、中仍有未处理词条)if（词条有效）then if（本词条不存在于hm） then 相应value=1；else if(本词条存在于hm) then 相应value+1；elsecontinue；rerurn;利用HashMap进行词频统计虽然很有效，但是也有弊端，那就是它最终的结果是无序的，而且当对两个文本进行利用HashMap的方法进行词频统计之后，很难保证两个文本同一词条在HashMap的位置是一样的。如果同一词条所对应的词频不能出现在最终两个向量的同一个维度，那么接下去的计算必然是无效的。所以在第二个文本进行填充HashMap之后就要进行一定的操作处理，最终使得两个向量相同的词条的词频出

11、现在相同的维度。因此，设计了算法对此进行实现，其基本思想是：设置两个数组和两个迭代器，两个数组用来最终存储两个向量的值，分别进行迭代操作判断出现顺序完成统计。首先，用第一个迭代器对第一个HashMap进行遍历，将对应关键字的键值从数组第一个位置起往后存储。与此同时，遍历每一个关键字之后，对这个关键字在第二个HashMap中是否存在进行判断：如果存在，这说明两个文本中都存在这个词条；如果不存在，这说明这个词条只在第一个文本中出现。判断可知该算法的时间复杂度为O(n)。接下来要对利用第二个迭代器遍历第二个HashMap，这时候只需要对词条只出现在第二个文本的情况进行统计。对应的条件就是判断该关键字

12、的键值在第一个HashMap中是否为空，是的话那就说明这个词条的频率需要统计。由此一来，既可以将所有出现在两个文本中的词条进行统计并在最终的向量数组中存储，又可以使得两个向量保证以相同的词条顺序存储，那么接下来的计算就是准确的。具体算法如算法2所示。算法2 向量生成算法输入：存储词频统计结果的HashMap，hm1和hm2。输出：存储向量的vector1，vector。Integer vector1;Integer vector2;/ 初始化两个数组Iterator iterator1 = hm1.keySet().iterator();/初始化两个iterator Iterator iter

13、ator2 = hm2.keySet().iterator();while(iterator1.hasNext()不为空)vector1i=hm1.get(iterator.next();if(该关键字不存在于hm2) then buff2i = 0;else buff2i = hm2.get(iterator.next();while(iterator1.hasNext()不为空)if(该关键字不存在于hm1)then buff2i= hm2.get(iterator.next();buff1i=0;else break;return;如果数据的维度过大，无疑会大大增加程序的运行时间，所以词

14、频统计中数据降维是一个重要因素，想要提高效率必须要进行合适的降维操作。当文本中的词条的数量很多，又有很多的标点符号时，都会增加向量的维度，提高了计算的复杂程度。为了提高计算的效率，需要进行适当的降低向量维度的操作，去除一些无关紧要的词语、标点等，减少向量的维度。这样既可以有效的提高效率，又可以提高算法的精度。 本系统在处理这个问题时，是在进行HashMap填充之前，利用分词结果剔除一些标点、空格、一般常用语等对于相似度匹配来说的干扰项。这样可以进行简单地去除那些对文本相似度产生精确度影响的词条，也就是说，在把词条加入HashMap时，会先进行简单地判断该词条是否为对相似度判断无效的词

15、条，只有有用词条会被添加到HashMap中，否则就直接跳过，继续判断下一词条。3.3相似度计算VSM模型（VSM：Vector Space Model）即向量空间模型，由索顿等人于20世纪70年代提出，并成功地应用于著名的SMART文本检索系统Error! Reference source not found.。向量空间模型的基本思想是：用特征向量来表示原来的文本，这样抽象的文本相似度计算问题就转化成了可见的为空间向量之间的运算，由此大大降低了问题的复杂性，而其可行性也大为提升。它首先按照分词技术得到的分词结果，把原来的文本映射为一个n维的空间向量，文本的相似度就可以通过计算两段文本对应的向量

16、的余弦值来确定，利用了空间里向量的相近程度解决了文本之间的的相似性问题，简单易懂。对于计算机来说，模糊的文本数据在经过向量空间模型的处理之后，转换成了可被计算机识别处理的数据，在得出两个向量之间的相似性程度之后，两个文本之间的相似性问题也随之得到解决。每一篇文本，都是由许许多多的词条组成，文本和其中的词条之间存在一定的关系，我们需要对这个关系进行一个研究。我们可以把一段文本看成一个向量D（value1,value2,valuen），其中value1，value2是对应于组成这个文本的某个词条的一个值，在下文中会对这个值进行进一步的说明。这样，假设有在文本1中出现了3个词语a、b、c，在文本2中

17、出现了3个词语a，c，d，我们要比较文本1和文本2的相似度，那么我们选择两者并集所包含的词语数量作为两个文本的向量的维度数，也就是4维，那么接下来就是对每一维的值进行确定，我们使用TFIDF作为这个值，它的理论思想是这样的：一个在某个文本中多次出现而在其他文本中很少的词条对不同文本的区分具有很强的意义，根据这样的词语对文本进行分类处理可以得到很可靠的效果。那么首先让我们了解两个概念：词频 (term frequency, TF) 指的是某一个给定的词语在该文件中出现的次数Error! Reference source not found.。在下面的算式中 ni,j 

18、;是该词条的使用次数，文本中全部词条的出现次数的和作为分母。其计算如式（1）所示。 （1）逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。如果词条t在所有文本中出现次数越少，基数就会越小，IDF的值就越大，这就意味着t可以对不同文本进行很明显的区分。IDF可以由式（2）获得，其中，|D|：所匹配的库中的文本总数，：包含词语ti的文本数。 （2）上文中提到了文本所对应的向量有很多个维数，我们现在要给每个维的值进行赋值，也就是最后我们得到的TFIDF如式（3）所示： （3） 假设上文中，idf均为1，文本1词条a出现的频率为0.4，b出现的频

19、率为0.3，c出现的频率为0.3，文本2词条a出现的频率为0.6，c出现的频率为0.2，d出现的频率为0.2，按照相同词条的频率出现在向量的相同维度，由此可以得,两个文本向量为（0.4,0.3,0.3,0）和（0.6,0,0.2,0.2），再按照下文中的相似度计算方法计算相似度。首先把两段文本处理成为对应的两个向量，基于向量空间模型的理论，两段文本之间的相似度就可以认为是该文本所对应的向量在空间上的接近程度，也就是向量之间的夹角，夹角越大那就越不接近反之就越接近。我们对两个向量的余弦值进行计算，根据余弦值的大小来得出两段文本的相似程度，按照式（4）就可以得出最终的sim值。 

20、9;åå= （4）其中，T1、T2代表待比较的两个文本对应的向量，其中的i表示向量的第i维，n用来表示向量的维数。两个向量的余弦值是一个大于等于0小于等于1的数，如果向量一致余弦值就是1，如果向量正交就是0，这一点也符合相似度必然属于0到1这个区间的特性，0代表完全不同，1代表完全相同。由此我们就可以通过这个sim的值来对两短文本的相似度进行判断。4 算法测试与评估我们选取病历这一特定文本进行测试，医生在进行病理管理的过程中，需要进行相似病历查找的时候，更为准确的方式是利用患者的主诉和初步诊断结果在病历库中进行搜索，查找出最为相近的病历供医生参考使用。为测试算法的实用性和准

21、确性，选取了以患者主诉和初步诊断为基本内容的测试文本作为实验数据进行了实验，并对实验结果进行分析。Text作为实验文本，Text1至Text5为测试文本分别与其进行相似度检测。分词前后结果分别如表4-1和表4-2所示。表4-1文本内容文本内容Text咳嗽已有半月多，加重时发热伴有胸闷，呼吸困难，不能正常入睡，初步诊断为急性支气管肺炎，若药物治疗效果不明显建议尽快到医院进行手术治疗。Text1在检查前2小时，我在行走时不慎被摩托车撞倒，局部皮肤青紫，皮肤无破损，明确外伤史致腰部、右大腿疼痛，初步诊断为腰骶部软组织挫伤 右大腿软组织挫伤。Text2畏寒、发热伴咳嗽、咳痰多天，时常会呼吸困难，初步诊

22、断为右中、下肺肺炎，急性气管-支气管炎，建议尽快接受治疗Text3我十余天前无诱因下出现左上腹部阵发性隐痛，进食后疼痛加剧，按压后稍有缓解，初步诊断为胃癌伴幽门梗阻，建议尽快到医院就诊。Text4孩子由于受凉咳嗽三天，发热两天，有痰很难咳出，初步诊断为支气管肺炎、佝偻病，建议尽快到医院确诊。Text5阵发性心前区疼痛，不适1年，加重3天，持续时间几分钟，伴有咳嗽，服药后症状无缓解，初步诊断为冠心病。表4-2分词结果分词结果Text咳嗽/v, 、/w, 咳/e, 痰/n, 已/d, 有/v, 半月/m, 多/m, ，/w, 加重/v, 时/ng, 发热/v, 伴/v, 有/v, 胸/ng, 闷/

23、v, ，/w, 呼吸/v, 困难/an, ，/w, 不能/v, 正常/a, 入睡/v, ，/w, 初步/d, 诊断/v, 为/p, 急性/b, 支气管/n, 肺炎/n, ，/w, 若/c, 药物/n, 治疗/v, 效果/n, 不/d, 明显/a, 建议/n, 尽快/d, 到/v, 医院/n, 进行/v, 手术/v, 治疗/v, 。/wText1在/p, 检查/vn, 前/f, 2/m, 小时/n, ，/w, 我/r, 在/p, 行走/v, 时/ng, 不慎/d, 被/p, 摩托车/n, 撞/v, 倒/v, ，/w, 局部/n, 皮肤/n, 青/a, 紫/a, ，/w, 皮肤/n, 无/v, 破

24、损/v, ，/w, 明确/ad, 外伤/n, 史/ng, 致/v, 腰部/n, 、/w, 右/f, 大腿/n, 疼痛/an, ，/w, 初步/d, 诊断/v, 为/p, 腰/n, 骶, 部/q, 软组织/n, 挫伤/v, /nr, 右/f, 大腿/n, 软组织/n, 挫伤/v, 。/wText2畏/vg, 寒/ag, 、/w, 发热/v, 伴/v, 咳嗽/v, 、/w, 咳/e, 痰/n, 多天/m, ，/w, 时常/d, 会/v, 呼吸/v, 困难/an, ，/w, 初步/d, 诊断/v, 为/p, 右/f, 中/f, 、/w, 下/f, 肺/n, 肺炎/n, ，/w, 急性/b, 气管/n

25、, -, 支气管炎/n, ，/w, 建议/n, 尽快/d, 接受/v, 治疗/v, 。/wText3我/r, 十余天/m, 前/f, 无/v, 诱因/n, 下/f, 出现/v, 左上/f, 腹部/n, 阵/ng, 发/v, 性/ng, 隐痛/n, ，/w, 进食/v, 后/f, 疼痛/an, 加剧/v, ，/w, 按压/v, 后/f, 稍/d, 有/v, 缓解/v, ，/w, 初步/d, 诊断/v, 为/p, 胃癌/n, 伴/v, 幽门/n, 梗阻/v, ，/w, 建议/n, 尽快/d, 到/v, 医院/n, 就诊/v, 。/wText4孩子/n, 由于/c, 受凉/v, 咳嗽/v, 三天/m

26、, ，/w, 发热/v, 两天/m, ，/w, 有/v, 痰/n, 很/d, 难/a, 咳/e, 出/v, ，/w, 初步/d, 诊断/v, 为/p, 支气管/n, 肺炎/n, 、/w, 佝偻病/n, ，/w, 建议/n, 尽快/d, 到/v, 医院/n, 确诊/v, 。/wText5阵/ng, 发/v, 性/ng, 心/n, 前/f, 区/n, 疼痛/an, ，/w, 不适/a, 1年/m, ，/w, 加重/v, 3天/m, ，/w, 持续/vd, 时间/n, 几分钟/m, ，/w, 伴/v, 有/v, 咳嗽/v, ，/w, 服/v, 药/n, 后/f, 症状/n, 无/v, 缓解/v, ，/w, 初步/d, 诊断/v, 为/p, 冠心病/n, 。/w由于不同文本之间词条数量的差异，无法统一进行向量的生成，需要逐一地将测试文本同实验文本进行相似度计算的处理。在进行数据降维，除去标点符号之后进