中文短语文本相似度计算新方法

摘要：针对短语文本的分类、聚类、信息查询问题，提出了一种新的中文短语文本相似度计算方法。用该方法计算出的文本相似度及一个比较文本与多个被比较文本所得相似度变化趋势是合理的，因此可以满足短语文本分类/聚类和信息查询的需要。

关键词：相似度；文字匹配位置集合；文字匹配最小位置偏移值；文字匹配贡献值；短语文本相对相似度

中图分类号：TP312文献标识码：A文章编号：1672-7800（2011）01-0079-03

作者简介：王莹莹（1981-），女，山东临邑人，硕士，济南市科学信息研究所研究实习员，研究方向为软件工程、信息处理；任贤（1983-），女，湖南汨罗人，硕士，河池学院计算机与信息科学系助教，研究方向为网络安全、信息处理；龙鹏飞（1960-），男，湖南祁东人，长沙理工大学计算机与通信工程学院教授，研究方向为计算机软件、面向对象技术、信息处理。1中文短语文本相似度满足的要求

为了给两个短语文本的相似度建立统一的衡量标准，任意两个短语文本间的相似度计算公式的构造考虑了下列因素，做了如下设计：①相似度依赖于两个短语文本中相同文字的位置；②两个完全相同的短语文本，其相似度应为一常数，如常数1；当一个短语文本某个位置的文字在另一个短语文本中有多个位置上的文字相同时，其相似度仍然为该常数；③若两个短语文本相互不包含对方元素，则其相似度为0。

2相关定义

为了便于算法实现，用A=“A0A1，…，Am-1”和B=“B0,B1,…，Bn-1”分别表示长度为m和n的短语文本。

基于相似度依赖于两个短语文本中相同文字的位置，定义 C(A,i,B)={k|Bk=Ai,k=0,1,…，m-1|}(1)为A中第i个文字与B中相匹配文字的位置集合。当A的第i个文字在B中无相匹配文字时，C(A,i,B)为空集合。同时，定义d(A,i,B)= min{|k-i|k∈C(A,i,B)}当C(A,i,B)≠

n, 当C(A,i,B)=(2)为文字Ai的最小匹配偏移值，定义CC(A,i,B)= n-d(A,i,B)n(3)为文字Ai的匹配贡献值。定义SC(A,i,B)= 1 m∑mi=1CC(A,i,B) (4)为短语文本A相对于短语文本B的相似度。

式（4）符合相似度公式的要求，下面给出其证明。

证明：（1）当C(A,i,T)≠时，SC(A, B)= 1 m∑mi=1n-d(A,i,B)n=

1 m∑mi=1n-min{|k-i‖k∈(A,i,B)}n 所以，当两匹配文字偏移值|k-i|越大时，短语文本A对于短语文本B的相似度SC(A,B)越小，当|k-i|越小时，SC(A,B)越大，即相似度依赖于两个短语文本中相同文字的位置。

（2）当C(A,i,B)=时， SC(A, B)= 1 m∑mi=1n-n n=0即当两短语文本相互不包含对方元素时，相似度为0。

（3）当C(A,i,B)≠且两短语文本完全相等时，有 SC(A, B)= 1 m∑mi=1n-0 n=1m×m×1=1即两短语文本完全相等时相似度为常数1。

（4）在两短语文本完全相等的情况下，由于d(A,i,B)=min{|k-i|k∈C(A,i,B)}，那么短语文本A中的某一文字不管与短语文本B中多少个位置上的文字相同，与i不同位置的k不会对相似度有影响，即此种情况下d(A,i,B)始终为0。例如：短语文本A=B=“1中3中中6”，A的第2个位置上的“中”字，与短语文本B的第2、4、5个位置上的文字都相同，根据公式（2.1）有C(A,2,B)={2,4,5}，再根据公式（2）有d(A,2,B)=min{|k-2|k=2,4,5}=min{|2-2|,|4-2|,|5-2|}=min{0,2,3}=0，所以不管B中有几个文字与“中”字相同，d(A,2,B)始终为0。

由（4）式得到的SC(A,B)是一个相对值，它表征B相似于A的程度，而用同样的方法计算所得的SC(B,A)也是一个相对值，表征A相似于B的程度，一般情况下，SC(A,B)≠SC(B,A)，所以不能由（4）式得到的值作为最终的短语文本A与B之间的相似程度。然而聚类时对象之间的相似度不存在参照与被参照的关系，所以针对文本聚类的需要，我们另外定义S(A,B)= SC(A,B)+SC(B,A)2(5)作为短语文本A与短语文本B的相似度。

3代码描述

根据上述短语文本相似度的定义，用C#语言实现相似度计算中的主要函数，包括计算文字匹配最小位置偏移值PosOffset函数、文字匹配贡献值CC函数、相对相似度SC函数和短语文本相似度S函数。

public static int PosOffset(string A, int i, string B)

{//计算匹配文字Ai的最小匹配偏移值posOffset

int posOffset = B.Length;

for (int j = 0; j < B.Length; j++)

{

if (i+j>=0&&A[i] == B[i-j])

ruturn j;

if(i+j

return j;

}

return posOffset;

}

public static float CC(string A,int i, string B)

{//计算匹配文字Ai对于整体相似度的贡献量

return (B.Length - PosOffset(A,i,B)) / ((float)B.Length);

}

public static float SC(string A, string B)

{//计算短语文本A相对于短语文本B的相似度sc

float sc = 0.0f;

for (int i = 0; i < A.Length; i++)

c += CC(A,i,B);

sc /= A.Length; //归一化

return sc;

}

public static float S(string A, string B)

{//计算短语文本A与短语文本B之间的相似度

return (SC(A,B) + SC(B,A))/2;

}

设m、n分别为短语文本A和短语文本B的长度，那么当A与B相等时算法的时间复杂度为O(m+n)，当A与B不等时算法时间复杂度为O(mn)。由于算法只使用一维数组作为存储变量，所以算法的空间复杂度较小。

4算法的合理性检验

为了验证该算法的合理性，设计了一套方案进行测试，为了更好地反映各种因素对相似度值的影响，实验中测试数据多处用数字代替不同的汉字，具体内容如下：

（1）验证短语文本完全相同时相似度是否为1，完全不同时相似度是否为0。用“大学物理实验”分别与“马克思主义哲学”、“大学物理实验”比较，用“中华人民共和国”分别与“湖南省长沙市”、“中华人民共和国”比较，该算法计算的结果依次为“1”、“0”、“1”和“0”，与期望值是相同的。

（2）对于给定的两个短语文本A和B，验证算法结果是否与两文本的调用顺序有关。我们取三组文本进行验证，结果如表1所示。

表1实验内容（1）结果短语文本A短语文本B文本相似度高等数学离散数学0.5离散数学高等数学0.5毛泽东思想概论大学生思想品德修养0.2539683大学生思想品德修养毛泽东思想概论0.2539683计算机专业英语大学英语0.1785714大学英语计算机专业英语0.1785714由表1可以看出，计算结果与两文本的调用顺序无关，符合要求。

（3）验证文字匹配偏移值对算法结果的影响，即是否是偏移值越大，两文本相似度越小，反之越大。分别取1个、2个、3个文字匹配时的3组情形进行试验。

对于固定短语文本“语”，分别取“语”、“英语”、“1英语”、“12英语”、“123英语”、“1234英语”与之比较，得到的文字匹配偏移值—文本相似度，如图1所示。

对于固定短语文本“英语”，分别取“英语123”、“英1语23”、“语英123”、“1英2语3”、“31英语2”、“31英2语”与之比较，得到的文字匹配偏移值累加和——文本相似度如图2所示。

对于固定短语文本“信息所”，分别取“信息所12”、“信息1所2”、“息信所12”、“1信息所2”、“息所信12”、“息所1信2”、“息所12信”与之比较，得到的文字匹配偏移值累加和——文本相似度如图3所示。

图1实验内容（3）1个文字匹配的结果

图2实验内容（3）2个文字匹配的结果

图3实验内容（3）3个文字匹配的结果

（4）验证对于一个固定的短语文本，与另一短语文本的匹配文字位置相同情况下，另一短语文本的长度对于相似度值的影响。我们分别取第1个位置和第2、4个位置相同的情况进行实验。

对于固定短语文本“语用知识库”，分别取“语”、“语言”、“语议论”、“语法规则”、“语法（上）”、“语言学（二）”与之比较，得到的短语文本长度——文本相似度如图4所示。

图4实验内容（4）第1个位置相同时的结果

对于固定短语文本“原理与构成”，我们分别取短语文本“物理结构”、“1理2构3”、“1理2构34”、“1理2构345”、“1理2构3456”与之比较，得到的短语文本长度——文本相似度如图5所示。

（5）验证对于一个固定长度的短语文本，两文本匹配文字个数相同情况下，另一短语文本长度对于相似度值的影响。取有2个匹配文字、3个匹配文字和5个匹配文字的情况分别进行试验。实验结果如表2所示。

从以上各项实验内容可以看出，随着文本间相匹配情况的变化，用此方法计算出的两文本的相似度值受很多因素的影响出现相应的变化，且变化趋势与人们的主观判断相符合，所以说综合考虑以上各种因素而设计的相似度计算公式是合理的，可以将该公式用于短语文本的相似度计算。

图5实验内容（4）第2、4个位置相同时的结果

表2实验内容（5）结果短语文本A短语文本B短语文本B的长度文本相似度两个匹配文字中国567中国20.7国中567中国130.4国5中67中国1240.3国56中7中1国2350.2国567中12中3国460.1666667三个匹配文字中国龙67中国龙30.8国中龙671中国龙40.525国龙中67中国1龙250.4国龙6中7中1国23龙60.25国龙67中12中3国4龙70.2五个匹配文字中国龙电器中龙国电器50.92国中龙电器中国1c电器60.75国龙中电器中国龙12电器70.6285715国龙电中器中1国2龙3电器80.4375国龙电器中12中国3c电器490.45结束语

文章针对中文短语信息的处理问题，提出了一种新的中文短语文本相似度计算方法，并对其进行了详细的描述。该算法首先定义了文字匹配位置集合，然后定义了文字匹配最小位置偏移值，在此基础上提出了文字匹配贡献值的概念，又进一步定义了文本相对相似度，最后提出了两短语文本之间的相似度计算公式。算法合理性检验结果表明，用该方法计算出的不同短语文本之间相似度值的变化趋势是合理的，可以满足短语文本分类、聚类、信息检索等的基本需要。

参考文献：

[1]李星毅,增路平,施化吉.基于单词相似度的文本聚类[J].计算机工程与设计, 2009(8).

[2]何海江.一种适应短语文本的相关测度及其应用[J].计算机工程, 2009(6).

[3]周法国,杨炳儒.句子相似度计算新方法及在问答系统中的应用[J].计算机工程与应用, 2008(1).

[4]励子闰,余青松,陈胜东.基于全文检索引擎的信息检索技术的应用研究[J].计算机与数字工程, 2008(9).

（责任编辑：周晓辉）

推荐访问:短语 中文 新方法 文本 计算