基于语义相似性的中文文本检索算法研究

基于语义相似性的中文文本检索算法研究

1基于文本特征串的方法通过文本搜索，不仅可以保护知识产权，而且可以提高搜索效率。其核心内容就是判断两篇文本内容中是否存在雷同成分,并给出一个数值评估,这个值可以称为相似度。在计算相似度值前,需要提取文本特征。根据提取文本特征的方式可以将目前的研究方法分为两类,一类是采用基于字符串比较的方法,也称为基于语法的方法,如sif,COPS,shingling,YAP3,MDR;另外一种采用基于词频统计的方法,也称为基于语义的方法,如SCAM,CHECK,CDSDG。国内方面,哈尔滨工业大学信息检索试验室提出了用特征码的方法进行网页查重。清华大学也研究了类似的方法:采用“自然语句分隔标志”将文本切成若干“句子”,从句子中提取若干字符和汉字作为特征码,然后按照“句子”在文本的顺序连接形成特征串。还有LCS算法,即计算最长的公共子序列,根据其长度与文本长度的比值来判断文本内容是否重复,但是算法的时间复杂度和空间复杂度较高。本文根据汉语语言学的研究成果以及对中文动词使用频率的统计,提出了一种获取文本特征串的新方法,结合字符串比较算法,计算出中文文本的语法相似性;利用词频统计的方法计算出中文文本的语义相似性,根据改进的计算公式,可以得到两篇中文的相似度,从而进行中文的重稿检测。2算法理论基础两篇文章间的相似性可以从语法相似性和语义相似性两个方面进行度量。2.1扩展动词序列吕叔湘在其代表著《中国文法要略》中构建了动词为中心的句法模型。在分析句子时,认为句子中心是表示动作的动词,而表示动作之所由起,所终止,以及所关涉的各个方面的名词,都是对这个动词的补充,因而统统可称为“补词”。于是,句子中除动词这个中心以外,就有了“起词”,“止词”,“受词”,“关切补词”,“交与补词”,“凭借补词”等各种“补词”。也就是说,句子表达的意思体现在句中的中心动词上,因此段落中所有句子的中心动词组成的序列就体现了段落的中心意思,同理,文章中所有句子的中心动词组成的序列可以概括全文的中心意思。这样,动词序列不仅反映了文章中发生的动作,而且描述了动作的发生顺序,因此可以用动词序列作为文章的特征串。两篇文章间特征串的相似性反映了文章间的相似性。目前,基于这个假设,一些研究机构提出了关于提取句中主干动词的算法,以及用“句子骨架依存树”的概念来计算句子间的相似度。在本文中,通过扩展动词序列,即将文中所有动词组成的序列作为研究对象,来降低算法的复杂性。同时,为了降低动词序列的长度,从而降低算法的空间复杂度,排除了动词序列中所有的停用动词。停用动词是对信息检索领域中停用词的扩展。在信息检索中,集合文献中出现频率高于80%单词是没有用的,这些词常称为“停用词”,需要过滤掉。一般认为停用词包括冠词,介词,连词和语气词,还可以包括这些词之外的其他词,例如一些动词、副词和形容词。通过统计动词的使用频率,发现一批动词在文本中普遍存在。可以将这类词归为停用词,在这里称为停用动词。表一是从2378篇文本,共20.8M字节数据得到的动词使用频率的统计表。如表1所示:由表1可以看出,如“应”,“为”,“到”,“会”,“可以”等均可以视为停用动词。在排除停用动词后,可以降低动词序列的长度,即降低特征串的维数。2.2计算相似度的计算度量语义相似性可以参考信息检索中的向量模型。向量空间模型的基本思想是以向量来表示文本:(w1,w2,w3,….,wn),其中wi为第i个特征项的权重。可以选择字、词或者词组作为特征项,一般认为选取词作为特征项要优于用字和词组作为特征项,同时用词的相对词频表示向量的分量。最常用的权重计算方法是TF-IDF加权法:Wi,j=fi,j×logNni(1)fi,j=freqi,jmaxl(freql,j)(2)idfi=logNni(3)Wi,j=fi,j×logΝni(1)fi,j=freqi,jmaxl(freql,j)(2)idfi=logΝni(3)其中N为系统中文本总数,ni表示含有词ki的文本数目,fi,j表示词ki在文本dj中初始频率,在这里指在文本中出现的次数。则文本dj中词ki的标准化频率为fi,j,最大值是通过计算文本dj中所有词来获得的。idfi为词ki的逆文献频率,Wi,j为词ki在文本dj中的权重。在获得文章的特征向量后,就可以计算文章间的相似度。设文档di的特征向量为(w1i,w2i,w3i…,wni),文档dj的特征向量为(w1j,w2j,w3j…,wnj),其相似度一般以计算余弦角为基础。例如:Dice系数:Sim(Di,Dj)=2*∑k=1nwkiwkj∑k=1nw2ki+∑k=1nw2kj(4)Sim(Di,Dj)=2*∑k=1nwkiwkj∑k=1nwki2+∑k=1nwkj2(4)3算法流程3.1计算相似度假定两篇中文分别为A,B,算法流程描述如图1所示。在分别获得两篇文章的动词序列后,可以将动词序列看作一个字符串,因此两个动词序列的相似性可以通过计算两个字符串的公共子串的个数来获得。假设文章A的动词序列为V1,V2,V3,V2,V4;文章B的动词序列为V1,V3,V2,V4。则A→B公共子串的个数由图2可示,B→A公共子串的个数由图3可示。则A→B公共子串的个数为3,B→A公共子串的个数为4。则取二篇文章间最大公共子串个数作为实际公共子串个数。在获取到最大公共子串个数后,采用类似Dice系数来计算相似度。计算式为:f1=2×ca+b(5)f1=2×ca+b(5)c为公共子串的个数,a为文章A的动词序列中动词的个数,b为文章B的动词序列中动词的个数。根据此计算式,则上述两篇文章的语法相似度为88.89%。3.2交叉集的情形算法步骤为:1)中文分词;2)计算各词的权重;3)获得前N个权重最大的词作为特征串;4)计算两篇文章的特征串的交叉集;5)计算相似度。在第2)步,利用TF-IDF计算词的权重。在第3)步中需要排除停用词,还包括所有的动词。在第4)步中引用了交叉集的概念,设文章Di的特征串为(s1i,s2i…,sni),文章Dj的特征串为(s1j,s2j…,snj)。则交叉集C(Di,Dj)为:C(Di,Dj)=(s1i,s2i…,sni)∩(s1j,s2j…,snj)交叉集C(Di,Dj)包含文章Di,Dj中均存在的特征词。在第5)步中采用以下计算式得到文章间的相似度:f2=∑k=1mmin(wki,wkj)max(wki,wkj)N(6)f2=∑k=1mmin(wki,wkj)max(wki,wkj)Ν(6)其中m为交叉集中元素的个数,wki为文章Di特征串中第k个词的权重,wkj为文章Dj特征串中第k个词的权重。N为文章特征串中元素的个数。计算公式中考虑到相同的特征在两篇文章间可能有不同权重的情况。通过权重的相除,可以量化相同特征分量在两篇文章中的不同作用。3.3计算相似性度量在获得了两篇中文的语义和语法相似性度量值之后,需要计算总的相似度,可以采用下述计算式来计算文章间的相似性:f=α*f1+β*f2(α>0,β>0,α+β=1)(7)f1为语法相似性度量值,f2为语义相似性度量值。α,β为加权系数,其值可以根据试验过程中语法结构、语义结构在度量文章相似性的权重确定,初始值可以设为0.5,0.5。4算法测试4.1文件的翻译从http://./part1.html中下载了150对文件,共447K,每对是对同一个英文文件的不同翻译版本,既包括成品,也有半成品。还有来自于复旦大学提供的语料库中的部分文本,共3042个纯文本文件,共47.5M字节,这些文件被用来作为干扰语料。4.2测试结果(表2)5计算对比算法综合考虑两篇中文的语法相似性和语义相似性,识别正确率以及查全率均超过了95%。