信息检索中一种句子相似度的计算方法

刘云芳，杨燕，贾真，尹红风，杨宇飞

西南交通大学信息科学与技术学院，四川成都 610031

信息检索是指根据用户提出的问题从大量文档资源集合中自动地找到与用户查询请求相关的各种信息［1］，即为使用户的查询句子或词语与文档集信息匹配的一个过程，其实质就是对自然语言进行相关的处理，从而使匹配的效果达到令人相对满意的程度［2］。信息检索的主要目的是获取用户所需的全面的且精确的信息，这就需要对信息检索中运用的技术进行相应的改进与完善。信息索引技术主要涉及信息词语切分和词语语法分析、进行词性标注及相关自然语言处理、建立索引项索引、检索结果处理技术，其中检索结果处理技术是关键技术，其核心是依据计算结果与查询语句的相关程度来排序。检索结果排序则应用到了句子相似度计算等技术。关于句子相似度的计算，不同的学者提出了不同的方法。如文献［3］主要依据分词以及词性标注技术对句子表面相似度进行了计算。文献［4］通过比较两句相同词的个数及其位置关系，得到两句的词形相似度和词序相似度，再通过词形相似度和词序相似度计算句子的相似度。文献［5］主要根据编辑距离与依存文法对句子进行相似度计算。文献［6］则是基于知网的句子相似度计算方法，而文献［7］中基于本体的句子相似度方法与文献［6］有异曲同工之效。由于对句子的分析角度不同，可以将句子相似度计算方法分为2种，一种是基于向量空间模型的计算方法，也就是句子表面相似度的计算方法，另一种是基于句法和语义的句子相似度计算方法。由于在信息检索中用户使用的查询语句较短，有时还缺乏必要的语境，因此单纯的使用关键词进行匹配并不能令人满意。为解决这一问题，有学者提出了查询扩展技术［8］，即在对查询语句进行扩展的基础上再进行句子相似度的计算。由于以上方法中对句子主成分的分析较少且不明确，因此文中依据句法依存树对用户问句进行了处理，并依此来确定句子中的关键字词以及其对应的权重。同时，文中在句子相似度计算方面提出了一种新的基于二叉树带权路径长度计算的方法。二叉树的带权路径长度计算即是计算每个叶子节点的权值与结点到根结点距离的乘积之和，而在文中中，叶子节点的权值即为句子中关键词的权重。最后计算句子间二叉树带权路径长度的比值，得到句子间的相似度。由于在信息检索中主要还是对有标题且标题总结性比较强的信息进行检索，所以文中在对关键字词进行扩展时只考虑了同义词近义词扩展。

1 算法原理

1.1 句子分析以及关键词提取

首先对句子进行依存句法分析，依存句法分析是将句子由一个线性序列转化为结构化的依存树，即利用依存标注表示出各词汇之间的关系，同时对每个词汇做了词性标注、词义消歧、命名实体等处理［9］。如句子“刘德华的电影有哪些”经过分词处理、词性标注以及句法分析后的结果如表1。

表1 例句处理结果

句子的依存树结构如图1所示。

图1 句子的依存树结构

国内部分学者研究得出有90%左右的用户输入的中文检索单字为2～6个，其中2个字词的占58%，4个字词的约占18%，3个字词约占14%。因此可以只对中文单句进行分析。

根据语言学知识，对中文单句进行分析可知，除了单个字词外，几乎每个句子都包含主语、谓语、宾语这些主要成分，有些还包含了修饰的部分，即定语、状语、补语等。句子的主要成分毫无疑问对句子的贡献度是比较大的，而这些成分中的词不可能包含所有词性的词，如连词等，因此，在保留句子关键词时，选择了保留部分词性的词，保留规则如下:

1)保留词性标注为 a、b、g、i、j、m、x、r、ws、v 以及以n开头的词语，但一般不保留动词“是、有”等。

2)若句首的词语的依存关系为HED，且词性为v的则去除。

由于在句子中，谓语是起到了承上启下的桥梁作用，而主语和宾语对句子的语义贡献度较大，因此，选出贡献度最大的词语对计算句子相似度有很大的帮助，查找贡献度最大的词语的规则如下:

1)若句中含依存关系为SBV的词，且词性标注不为r，则为贡献度最大的词语。

2)若句中不含依存关系为SBV的词，含有依存关系为POB的词，则依存关系为POB的词为贡献度最大的词语。

3)若依存关系不包含SBV和POB的词，含有依存关系为VOB且词性标注是以n开头的词，则为贡献度最大的词语。

4)若句子中不包含依存关系为SBV、POB以及VOB的词，且依存关系为HED的词的词性不为动词或疑问代词，则该词为贡献度最大的。如句子“刘德华的电影有哪些”经过处理后保留关键词“刘德华”、“电影”、“哪些”，根据以上规则可知贡献度最大的关键词为“电影”。

1.2 树的带权路径长度算法

带权路径长度(weighted path length of tree，WPL)算法是用在树结构中的一种算法，该算法包含了结点的权值、结点到树根之间的路径长度与结点的带权路径长度。

结点的权值:在一些应用中赋予树中结点的一个有某种意义的实数。

结点到树根之间的路径长度:树根层数为0时，结点所在的层数。

结点的带权路径长度:结点到树根之间的路径长度与该节点权值的乘积。

WPL:树中所有叶结点的带权路径长度之和。

文中主要用到了最优二叉树的带权路径长度的计算方法。

如一组数(2，4，5，7，8，9)形成的最优二叉树结构如图2所示。

图2 最优二叉树结构

该二叉树由下而上叶子结点的权值是由小到大的。图2中二叉树的带权路径长度计算公式为

2 实现方法

方法流程如图3。算法实现主要步骤包括句子预处理、关键词权重设置、关键词扩展、二叉树带权路径长度计算以及问句与标题句的相似度计算。

1)句子预处理:该部分包含了分词处理和句法分析2个部分，主要是对用户问句中关键词权重的设置做基础。

2)关键词权重设置:根据问句中关键词的词性以及在句子中的依存关系，为每个关键词设置权重。

3)关键词扩展:由于有些词有同义词和近义词，为了更准确的与标题句进行相似度的计算，对问句中的关键词进行了相应的同义词近义词扩展。

4)二叉树带权路径长度计算:将用户中的所有关键词对应的权重以最优二叉树的形式表示出来，并计算该二叉树的带权路径长度。

5)问句与标题句的相似度计算:根据问句的带权路径长度和标题句中包含的关键词，对问句与标题句之间的相似度进行计算。

图3 算法实现步骤

2.1 句子预处理

在对用户问句进行句法分析之前，要对问句进行分词以及词性标注处理，同时也要对标题句进行分词处理，文中主要运用了西南交通大学思维与智慧研究所的耶宝分词系统。由于耶宝分词具有超大规模的语料库和分词词库，以及较准确的歧义和未登录词识别，分词准确率较高，因此能对句子进行较准确的分词［10］，为后面句子相似度的计算做了良好的铺垫。

文中在使用分词系统以及句法分析系统时也做了一些处理。由于西南交大的分词系统中应用的是北大的词性标注，而哈工大的句法分析系统应用的是863词性标注，所以在用西南交大的分词系统进行分词后又将词性标注转换成了哈工大句法分析系统中的词性标注，以保证依存关系的准确性。

2.2 关键词权重的设置

由主观判断，认为一个句子中贡献度最大的词的权重将占整个句子权重的一半以上，而疑问词对句子信息的贡献度极小，可赋予一个很小的权重值，并经过多个单句之间相似度计算的测试，对关键词的权重设置运用了如下一些规则，即句中若含有贡献度最大的词，根据经验值将其权重设置为0.5，若剩下的关键词中含有词性为r或v的个数为m，设每个词的权重为x，其余的词个数为n，设权重为y，则求权重公式为

2.3 同义词近义词扩展

文中对用户问句进行处理后提取句中关键词，并找出每个关键词的同义词、近义词，组成不同的向量，关键词与其同义词对应的权重相同。其中，同义词、近义词的扩展主要依据一个已经建立的同义词、近义词库，该库中的同义词、近义词不仅包含了同义词词林中的同义词近义词对，同时也包含了在大量的百度百科词条中基于规则抽取出的同义词对。

2.4 问句的二叉树带权路径长度计算

根据式(2)计算出所有关键词的权重，然后根据权重向量进行问句的二叉树带权路径长度的计算。计算方法如下:

1)若问句中只有1个或2个词，则设其二叉树的带权路径长度qw=1。

2)若问句中的词如图4所示含有2个以上关键词，则可将其左边的向量转化成最优二叉树，然后计算二叉树的带权路径长度qw。

2.5 问句与标题句之间的相似度计算

对检索内容的标题进行处理，处理方法如下:

1)若标题中不含有问句中的关键词或关键词的同义词近义词，则其二叉树的带权路径长度aw=0。

2)若标题中只含1个词或只含2个词且均为问句中的关键词或关键词的同义词，则其带权路径长度aw=qw。

3)若标题中含有2个以上问句中的关键词或关键词的同义词近义词，去除句中停用词后总的词的个数为i，与问句中关键词或关键词的同义词近义词相同的词数为j，则标题中词的权重设置方法如下:

a)与问句中关键词或关键词的同义词相同的词的权重为

weightq(m)为与问句中关键词或关键词的同义词相同的词在问句中的权重。

b)与问句中关键词或关键词的同义词不相同的词的权重如下:

根据式(1)可计算出此标题句对应的二叉树带权路径长度aw

最后把标题句的权重视为其与问句之间的句子相似度Sim(a)。

3 实验分析

3.1 实验步骤

实验主要步骤如下:

1)运用分词系统以及句法分析系统对问句进行分析;

2)对问句中的关键词进行扩展，并设置权重，计算句子的二叉树带权路径长度;

3)对标题句进行去停用词以及提取关键词处理;

4)对标题中的词设置权重，并计算对应的二叉树带权路径，然后得到句子对应的权重，即与问句之间的相似度。

3.2 实验数据集

从哈工大信息检索研究室问答系统问题集中抽取104个问句，并对这104句中的关键词进行同义词近义词扩展，每个问句扩展出一个或以上相同相似的句子，然后在保证每个句子都有相似句子的情况下保留530个问句形成新的问题集。

由于百度是最大的中文搜索引擎，因此文中选择在百度搜索引擎中为这530个句子搜索出相应的答案，由于搜索结果的量较大，且统计用户翻阅答案的量是有限的，因此文中只选取了每个问题对应的搜索结果的前200个，又由于百度搜索存在竞价排名，所以会在搜索结果中的最前面出现广告干扰，文中将予以去除。同时所得搜素结果将包含标题句、网页链接以及对应网页的主要内容。其中主要内容的抽取文中首先利用正则表达式将网页中主要部分即＜body＞＜/body＞中的内容抽取出来，然后对已抽取内容进行分词以及词性标注处理，只保留词性标注不为 vyou、vshi且不以 w、u、c、p、d 以及 r开头的词，由于除了主要内容可能会含有英文单词外，网页源码中也存在很多英文单词，因此在处理词性标注以x开头的词时，根据网页结构，只保留了其前面词性标注以及后面的词性标注不同时为w或x的词，一般中文网页中大量的英文介绍内容很少，因此这种方法对主要内容的抽取影响不大，但网页噪声如广告等会对网页主要内容产生一些影响，文中不对该方面做深入研究。然后经过网页去重处理，最后形成含502173个搜索结果的信息检索结果集。

当用户提出问题时，首先运用关键词匹配以及tfidf算法对检索结果集进行检索和排序，然后再用文中算法对已检索结果进行二次排序。

文中采取平均查全率(mean of average recall，MAR)，查准率(mean of average precision，MAP)以及前30个返回的网页的查准率(precision of return results of top 30，PRRT30)作为检索结果的评测标准。

3.3 实验结果及分析

可先用如下实验结果来说明文中的句子相似度计算方法的效果。用户问句为“儿童电影有哪些”。文中根据搜索引擎给出的搜索结果设置了几个标题句，并利用不同方法对标题句与问句的相似度进行了计算与分析，计算结果如表2所示。

表2 相似度对比

方法1是一种基于词语共现统计的方法，利用了北大计算语言所提出的一种句子相似度计算公式:2c/(m+n)，式中:m、n分别为2个句子的词的个数，c是2个句子中相同词的个数［11］。

方法2是一种基于知网的句子相似度计算方法，利用了文献［6］中句子的表层相似度与语义偏移量相似度相结合的方法，其中用到的词语间相似度利用了文献［12］的词语间语义相似度的计算方法。

方法3是文中句子相似度计算方法，即对句子进行了分词，词性标注以及句法分析处理后，对句中的关键词进行抽取以及加权处理，然后基于带权路径长度计算方法计算句子间的相似度。

文中是对搜索结果进行二次排序，为获取更准确的信息，只对问句中的关键词做了同义词以及近义词扩展处理。

对表2进行分析可知，方法1中从标题句6到标题句9与问句1的相似度均为0，这显然是不合理的，因为从标题句6到标题句8中均含有问句中贡献度最大的词“电影”的同义词，而标题句9则含有“儿童”的同义词，方法3即文中方法用了关键词的同义词近义词扩展的方法，使以上含同义词近义词的句子之间的相似度计算结果更合理。标题句2在语义上与问题句1的相似度更大，因为并没有其他的限定词语，而标题句3中就含有限定词“经典”，所以标题句2与问句1的相似度应大于标题句3与问句1的相似度，而方法2中却是相反的，同时在方法2中标题句9与问句1之间的语义相似度和标题句10与问句1之间的语义相似度太大，而实际上标题句10与问句之间几乎没有联系，因此方法2是不符合实际的，文中方法则利用词性标注以及句法分析对句子进行分析处理，并采用二叉树带全路径长度计算方法对句子相似度进行计算使以上句子之间的语义相似度更符合人们的直观感受，如标题句10与问句1之间的相似度就比较合理。由以上分析可以看出，文中提出的计算方法更符合实际，具有一定的实用性。

基于已处理的数据集对文中方法进行评测，评测结果如表3所示。在未对问句进行扩展时，检索结果的查全率、查准率以及前30个检索结果的查准率较低，而对问句进行扩展后，都有所提高，最后再用文中方法对检索结果进行二次排序，在查全率不变的情况下检索结果的查准率有所提高。这说明文中方法在保证信息检索结果的查全率的情况下，能有效地提高信息检索结果的查准率，是可行的。

表3 评测结果对比

4 结束语

句子相似度的计算在自然语言处理领域中起到了不可或缺的作用，在文本聚类、机器问答等领域也占有重要地位。文中在对问句进行分词以及句法分析处理的基础上，利用了二叉树的带权路径长度的计算方法来计算问句与检索内容的标题句间的相似度，对检索结果进行了二次排序。由实验结果可知，文中提出的句子相似度计算方法比较符合人们的主观判断，能够很好地被运用到信息检索中检索结果的二次排序中去。在对句子处理方面文中运用到了句法分析系统，而句法分析系统分析句子结果的准确性和处理句子的速度都存在一些问题，因此文中在问句的处理上还存在一定的局限性。在下一步的工作中准备用其他的方法对问句中贡献度大的词进行提取。

［1］李立.中文信息检索系统研究［D］.武汉:华中师范大学，2008:15-28.

［2］王品，黄广源.信息检索中的句子相似度计算［J］.计算机工程，2011，37(12):38-40.

［3］周法国，杨炳儒.句子相似度计算新方法及在问答系统中的应用［J］.计算机工程与应用，2008，44(1):165-167.

［4］吕学强，任飞亮，黄志丹，等.句子相似模型和最相似句子查找算法［J］.东北大学学报:自然科学版，2003，24(6):531-534.

［5］刘宝艳，林鸿飞，赵晶.基于改进编辑距离和依存文法的汉语句子相似度计算［J］.计算机应用与软件，2008，25(7):33-34.

［6］程传朋，吴志刚.一种基于知网的句子相似度计算方法［J］.计算机工程与科学，2012，34(2):172-175.

［7］刘宏哲.一种基于本体的句子相似度计算［J］.计算机科学，2013，40(1):251-256.

［8］LISA BALLEDTEROS，BRUCE CROFT W.Statistical methods for cross-language information retrieval［M］.Boston:Kluwer Academic Publisers，1998:23-40.

［9］CHE W X，LI Z H，LIU T.A Chinese language technology platform［C］//Proc of the Coling 2010，Beijing.2010:13-16.

［10］西南交通大学中文分词系统［CP/OL］.［2013－12－25］.http://www.yebol.com.cn.

［11］王荣波，池哲儒，常宝宝，等.基于词串力度及权值的汉语句子相似度衡量［J］.计算机工程，2005，31(13):142-144.

［12］夏天.汉语词语语义相似度计算研究［J］.计算机工程，2007，33(6):191-193.