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

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

一整段的文本由多个词语组成,我们要进行文本之间相似度匹配的检测。第一步是对文本进行中文分词,分成一些关键的词语组,其中要剔除掉语意词、助词等等对文章大意没有影响的词汇。英文分词是相对容易的,因为每两个单词之间会有空格进行区分,这就使得分词工作变成了检测文章中的空格,然后加以分割。但中文句子并没有这样的特征,一个词汇是由多个汉字组成,而且有可能出现一个字与前后两个字都能组成词语的情况,需要根据语境进行判定区分,所以中文的分词技术相对来说要难很多。但目前中文分词技术也日渐成熟,出现了很多强大的中文分词工具,也提供了很多不能编程语言的接口。单字分词、二分法和词典分词是目前分词的主要方法。
单字分词,顾名思义即在对中文文本进行分词时,以字为单位进行切分。字索引很灵活,但是实现单字匹配算法却很复杂,也往往需要大量的CPU运算进行支撑。二分法,即将每两个字当作一个词语进行切分,然后建立索引,使用二分法可以明显地减少每个词条后位置信息的长度。
在进行了对比分析之后,词典分词的方法最为适合本系统的需要。词典分词的基本思想是先构造出一个基本词汇的词典,然后将遇到的文本同词典比对分析进行分词,这是当前相对准确的方法,也被广泛使用。本文使用的时Ansj中文分词,是一个基于google语义模型+条件随机场模型的中文分词的java实现,词速度达到每秒钟200万字左右,准确率能达到96%以上,目前实现了中文分词、中文姓名识别、用户自定义词典等功能,可以应用到自然语言处理等方面,适用于对分词效果要求高的各种项目。在文本中匹配单词时,正向最大匹配算法和逆向最大匹配法是词典分词法经常用到的算法,从左侧开始依次读入数据,尝试把几个连续出现的字符与词库中存在的词条进行匹配,如果成功,就可以分出一个词条,这是正向,而逆向是从文本的末端开始,每次都取最末端连续出现的几个字符进行匹配,如果匹配失败,那么加入该字段最前面的一个字,继续进行匹配Error! Reference source not found.。
当文本比较复杂,需要比较精确的分词的时候,就要用多种方式对文本进行切分,对不同方式的切分结果进行比对,相同的切分结果得到的词语就是真正需要的词。
 
上文中我们提到了要用到每个词条的出现的次数,那么就需要进行词频统计,也就是词条频率,用来评价一个词对于一段文本的重要性。 
在信息领域,基于匹配的词频统计算法和基于树结构的词频统计算法是最为经典也是最被认可的词频统计方法,被广泛使用。 
在单关键词匹配算法中,比较著名的有BF算法、KMP算法、BM算法等。 
(1)BF算法 
BF算法也被称为是蛮力算法,它的基本思想是:首先,A[1]和B[1]比较,如果相等,再对A[2]和B[2]进行比较,一直到B[m]为止;如果A[1]
和B[1]不相等,则B右移一下,继续进行比较。如果存在k,1≤k≤n,且A[k+1…k+m]=T[1…m],则匹配成功,否则失败。 
(2)KMP算法 
KMP算法是由高德纳(Donald Ervin Knuth)和 Vaughan Pratt 在1977年合作发明的。其基本思想为:如果在匹配的进程中,判断A[i]和B[j]是否相等,如果相等,那么继续对A[i+1]和B[j+1]进行判断;如果两者不相等,讨论一下两种情况,若j=1,向右移动,判断A[i+1]和B[1]相等与否,若1<j<=m,则右移j-next(j)位,检查A[i]和B[next(j)]是否匹配,重复此过程直到j=m或i=n结束。 
(3)BM算法 
BM算法1977年由Bob Boyer 和J Strother Moore提出,是一个字符串匹配算法。