句子比较相似度的算法实现?

吴宏洲

摘要：一种文本句子比较相似度算法，以连续文字串为单元块，相同单元块越大越多越相似，相异部分的单元块越小越少越相似，依此计算相似度值。可用来消除传统相似度取值置信区间中模糊区，精确到一个非此即彼的二元逻辑值。

关键词：文本句子比较；连续文字串；单元块；相似度

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）07-0183-07

The Realization of the Sentences to Compare Similarity Algorithm

WU Hong-zhou

（The China Patent Information Center， Beijing 100088， China）

Abstract： A comparison a text sentence similarity algorithm， order to a continuous text string as a unit， the same parts of unit block ， the more and bigger the more similar， the different parts of unit block，the less and more small the more similar， according to it to calculate the similarity values.It can be used to eliminate the traditional similarity confidence interval of fuzzy area， accurate to a “yes or no” binary logic values.

Key words： the comparison of the text sentence；Continuous text string；Unit block；Similarity

在专利文献自动摘要的技术研究与应用中，需要了解专利说明书中最具代表性的发明内容部分、权利要求书中最具代表性的独立权利要求部分，还包括发明的有益效果。这些部分摘选组合搭配是重构专利摘要的重要依据。从文献中抽取所需的最能代表发明专利中其技术方法的最重要的句子成分，作为文摘参考备选，这一过程是自动摘要的一个重要技术环节。然而在抽取技术特征最为集中的句子时，如果单单以句子本身的权重为依据来抽取句子的话，那么很有可能将某些句子权重高、相似度也高的句子同时都抽取出来。从而忽略了其他次重要的句子，从而导致算法偏好失衡。这时就需要用到一个句子比较相似度的方法，将相似内容的句子依据权重以及位置作取舍，对舍去的句子作参考值权重的衰减，从而达到消除相似或重复的内容的目的，使算法趋于偏好均衡。目前句子比较相似度算法大家公认的算法多采用cosine相似度算法，该算法取值通常会在[下限值，上限值] 置信区间的广阔中间区域出现判断上的不确定性，使得相似度算法的能力受到质疑。因此，笔者在重新考察句子间似与不似的成因时，发现了一个更简单有效的算法，可以很好地区分似与不似问题。其实验效果与笔者的预想有某种契合，笔者还不能证明其是否真正合理，或者说还没有找到一个反例推翻实验的巧合。这就是本文公开这一算法的真正目的。

1 实验背景

笔者在专利文献自动摘要的研究试验中发现，解读分析专利的权力要求，会大量出现内容相同或相似的句子，在不同的权力要求中反复出现，特别是某些重要的句子。如果，按照权重来简单抽取句子的话，那么等于该句子被抄写了N遍，挤掉了其他句子的出现机会。所以就加入了cosine相似度算法去重。对相似度高的句子，依据位置、权重作取舍，对舍去的句子作权重作衰减。试验还是不理想，结果也和预想的不一致。大概是该去的还在，该留的没了。索性对相似度相关算法重新调研，又纳入了3个算法。实验结论是已有算法多以词频统计为基本原理，来猜测两个句子之间的相似度。会忽略词的内涵和顺序问题。句式相似度很高，结论相反的句子，不能识别。参见《表1.句子相似度算法效果比对样例》序号2样例。笔者将重要的对比句子样例，按照cosine相似度排序依依列出来，然后重新标注出相同、相异的连续文字串单元块。参照jaccard方法，按照块数计算，按照字符串长度计算，两者合取的结果恰恰将表1的样例，似与不似，分得清清楚楚。后来花费了一些时间，网上搜索了与字符串匹配相关的方法，没有找到与笔者完全相似的方法，以及用于相似度计算的类似方法也很有限。现在可以对文本句子比较相似度的方法重新进行归纳了。

文本句子比较相似度的简约方法目前有基于词频的统计方法和基于连续字符串的方法。

1.1 基于词频统计的相似度算法

该方法主要通过分词技术和统计词频的思路来计算相似度。其中比较流行的是cosine、tanimoto、euclid和jaccard算法[1]。还有对数似然相似度算法，但是笔者将其列为复杂算法而略去。

1.1.1 余弦相似度

定义：

1.2 基于字符串的相似度算法

在已有技术中，基于字符串的匹配的相似度算法，目前还不多见。有些流行的方法，大都是与串匹配的方法相关，与相似度算法不直接相关。例如：kmp、horspool、boyer-mou和Sunday等算法[2]。另外，网上目前能够见到的两个常用字符串相似度算法是：最长公共子串（LCS）[3-4]，编辑距离或者Levenshtein距离相似度方法[5]。

1.2.1 编辑距离Levenshtein相似性算法

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。

例如：GUMBO和GAMBOL；由GUMBO变为GAMBOL，需要编辑变动最少要3次。则：

Lev=1-3/max（len（GUMBO），len（GAMBOL））=1-3/6=0.5

1.2.2 最长公共子串相似度算法

求两个字符串最长公共子串[3]。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，并替换成自然数序列。其对应的位置就是最长匹配子串的位置。

例如：字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。为“21232”长度为5。

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0

0 1 0 0 0 0 0 0 0 2 1 0 0 0 0

1 0 2 0 1 0 1 0 0 0 0 0 1 0 0

0 2 0 0 0 0 0 0 0 1 1 0 0 0 0

1 0 3 0 1 0 1 0 0 0 0 0 1 0 0

0 0 0 4 0 0 0 2 1 0 0 1 0 0 0

1 0 1 0 5 0 1 0 0 0 0 0 2 0 0

1 0 1 0 1 0 1 0 0 0 0 0 1 0 0

0 0 0 2 0 0 0 2 1 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

另外落稿前还发现了一种以寻求病毒或基因序列为特征的最长公共子序列的算法，如：发明专利号CN201110152462.1 [4]。

1.2.3 SWHZ字符串单元块相似度算法

SWHZ相似度算法属于笔者自定义的方法，以连续文字串为单元块，相同单元块越大越多越相似，相异部分的单元块越小越少越相似，依此计算相似度值。由两个互为修正的子算法组成，该算法不仅与单元块相关，还受限于块的大小，与块的大小或字符数相关。是由两者的合取得到的。与本算法比较接近的算法有jaccard算法、kmp算法和发明专利CN201110152462.1算法，但在用途、适用场景和算法实现上都有一定区别。

1） 基于连续文字串单元块，以单元块为单位统计块数，相同单元块数和相异单元块数之间的占比算法，用SWHZ1表示；

定义：SWHZ1=BA∩B/（BA∪B）= BA∩B/（BA∩B +（BA-B + BB-A））=V

BA∩B表示相同单元块数；BA∪B表示相同单元块数加相异单元块数；（BA-B + BB-A）表示相异部分单元块数。

V≥50%，认为相似；V<50%，认为不相似。

2） 基于连续字符串单元块字符数，以单元块为单位统计字符数，相同单元块的字符数和相异单元块字符数之间的占比算法，用SWHZ2表示。

定义：SWHZ2=CA∩B/（CA∪B）= CA∩B/（CA∩B +（CA-B + CB-A））=V

CA∩B表示相同单元块字符数；CA∪B表示相同单元块字符数加相异单元块字符数；（CA-B + CB-A）表示相异部分单元块字符数。

V≥50%，认为相似；V<50%，认为不相似。

3） SWHZ1与SWHZ2的合取用SWHZ表示。

定义：SWHZ= SWHZ1* SWHZ1。

V≥25%，基本相似；V<25%，基本不相似。

2 SWHZ句子比对相似度算法的技术实现

两个句子比对相似度算法，描述如下：

[两个句子比对相似度算法，描述如下：

//s1：串1传参；s2：串2传参；

diff_set←null；same_set←null；

tmp_1←null；tmp_2←null；b_exit←0；

while（s1≠null || s2≠null） {

s1_1←getfirstword（s1）；// 首个汉字或西文字母

if（s1_1！∈ s2） {

b_exit←cat（tmp_1，s1_1，s2）； /*

while（s1_1.string ﹦ COMMA） || （s1_1.string ！∈ s2）） { // 逗号不作首字

tmp_1.string ← tmp_1.string +

s1_1.string； delfirstword（s1，0，s1_1.word_num）；

if（s1﹦null） {b_exit←1；break；}

s1_1←getfirstword（s1）；

} */

}

if（b_exit﹦0） { // 确定首字符

s2_1←getfirstword（s2）；

if（s2_1 ！∈ s1） {b_exit←cat（tmp_2，s2_1）；} // if（s2﹦null） b_exit←2

}

if（b_exit﹦0） {

if（s1_1.string∈s2） { // 取位置集，分别计算首字在串中匹配位置长度串长

pos_1←get_pos_len（&s1_1，s2，s1，&pos_set_1）； /*

get_pos（&s1_1，s2，&pos_set_1）；

for（i←0；i

for（k←0，j←pos_set_1.match_set[i].position；k

if（s1[k] > 127 && s2[j] > 127） { // 全角汉字

if（strncmp（&（s1[k]），&（s2[j+k]），2） ﹦ 0） {k++；continue；} else {break；}

} else if（s1[k] < 128 && s2[j+k] < 128） { // ascii

if（s1[k] ﹦ s2[j+k]） {continue；} else {break；}

} else {break；}

}

pos_set_1.match_set[i].length ← k；

}

pos_1.position← -1；pos_1.length←0；

if（pos_set_1.match_set_num>0） { // 在前最大串长

for（i←0；i

if（pos_1.length < pos_set_1.match_set[i].length） {

pos_1.position←pos_set_1.match_set[i].position；

pos_1.length←pos_set_1.match_set[i].length；}}

pos_set_1←null；} */

}

if（s2_1.string∈s1） { // 同理：取位置集，分别计算匹配串长

pos_2←get_pos_len（&s2_1，s1，s2，&pos_set_2）；

}

if（pos_1.length > pos_2.length） { select ← 1；}

else if（ pos_1.length < pos_2.length） {select ← 0；}

else if（pos_1.position ≤ pos_2.position） {select ← 1；}

else {select ← 0；}

if（select﹦1） { // 选择 pos_1

proc_select（&pos_1，s2，s1，&tmp_2，&diff_set，&same_set）；/*

if（pos_1.position > 0） { // 匹配前有前缀

strncpy（str1，s2，pos_1.position）；

if（len（tmp_2.string） ≠ 0） { strcat（tmp_2.string，str1）；

} else {strcpy（tmp_2.string，str1）；}

} ＼& tmp_2.word_num←len（tmp_2.string）；

if（tmp_2.word_num > 0） {

insert（&diff_set，tmp_2.string）；＼/＼* i←diff_set.block_num；

strcpy（diff_set.block_set[i].cut_statement，tmp_2.string）；

diff_set.block_set[i].word_num ← tmp_2.word_num；

diff_set.block_num++；＼*＼/

tmp_2←null；

}

tmp_1.word_num←len（tmp_1.string）；

if（tmp_a.word_num > 0） {insert（&diff_set，tmp_1.string）； tmp_1←null；}

strncpy（str1，s1，pos_1.length）；if（len（str1） > 0） {insert（&same_set，str1）； }

strcpy（str1，&（s1[pos_1.length]））；strcpy（s1，str1）；

strcpy（str1，&（s2[pos_1.position+pos_1.length]））；

strcpy（s2，str1）；pos_1←null；pos_2←null；*/

} else { // 选择 pos_2 ，同理：

proc_select（&pos_2，s1，s2，&tmp_1，&diff_set，&same_set）；

if（s1 ﹦ null） {b_exit ← 1；}

}

}

if（b_exit﹦1） {

bexit_proc（s1，s2，&tmp_1，&tmp_2，&diff_set，&same_set）；/*

if（s1﹦null） {

if（tmp_1≠null） {insert（&diff_set，tmp_1.string）；tmp_1←null；}

if（len（tmp_2.string） > 0） {strcat（tmp_2.string，s2）；}

else {strcpy（tmp_2.string，s2）；}

s2←null；

if（tmp_2 ≠ null） {insert（&diff_set，tmp_2.string）；tmp_2←null；}

}

s1←null；s2←null；*/

}

if（b_exit﹦2） {/* 同理*/bexit_proc（s2，s1，&tmp_2，&tmp_1，&diff_set，&same_set）；}

}

for（i←0；i

same_set.block_set[i].word_num←len（same_set.block_set[i].cut_statement）；

same_set.totle_word_num ←same_set.totle_word_num +

same_set.block_set[i].word_num；

}

if（same_set.block_num﹦0） {same_set.totle_word_num←0；}

for（i←0；i

diff_set.block_set[i].word_num←len（diff_set.block_set[i].cut_statement）；

diff_set.totle_word_num ←diff_set.totle_word_num +

diff_set.block_set[i].word_num；

}

if（diff_set.block_num﹦0） {diff_set.totle_word_num←0；}

swhz1←1.0*same_set.block_num/（0.00001+same_set.block_num+diff_set.block_num）+

0.00001；

swhz2←1.0*same_set.totle_word_num/（0.00001+same_set.totle_word_num+

diff_set.totle_word_num）+0.00001；

swhz←swhz1*swhz2；＼&]

算法过程说明：

[初始：

Same_set={}，Diff_set={}；

两串比较开始：S1、S2

[

如表1所见。其中“结果I”是通过cosine相似度算法取值，当出现在62%～90%之间模糊区时，继续采用euclid算法取值，得到的结果，也不能将表1所列样例区分干净。“SWHZ标记”是本文算法得出的结论，“结果II”是人工标引的结论，两者基本一致。而“评测”是“结果I”与“结果II”的一致性标注，有6个“相反”的结论，说明传统算法存在误判。其中序号18的样例，是一个典型的量变到质变，由SWHZ2修正了SWHZ1的结论；同样序号3的样例，由SWHZ1修正了SWHZ2的结论；而序号2的样例，是一个cosine相似度高，结论相反的典型样例，被SWHZ检测出不相似，效果明显优于传统算法。

4 结论

在文本句子间比较相似度这一特定应用场景下，笔者所提出的SWHZ相似度算法，主要是针对已有传统基于词频统计的方法存在不足，取值范围会在某个最大临界点和最小临界点之间出现判断上的模糊区域，使得相似度算法应用受到质疑。SWHZ相似度算法可以用来消除传统相似度取值置信区间中的模糊区域，使之得到一个非此即彼的二元逻辑值：像或是不像。本文还推荐该方法并建议与传统cosine相似度简约算法相结合，作为cosine的补充算法。仅当cosine相似度取值在62%～90%区间时使用，用于进一步判断相似性。只有在判断符合相似的结论下，才宜用cosine相似度值作为相似程度的解释，否则应该衰减cosine取值到低于62%，或者用低于25%的SWHZ实际值取代。这样使得综合修正后的cosine相似度的有效取值，可以扩展范围到62%～100%之间。笔者需要特别强调的是该算法未证明直接适用于文本句子间比较以外的扩展用途。例如：直接文章比较、直接段落比较，以及用于基因序列比较等复杂应用场景。既不接受植入其它修正方案，也不推荐应用于本文特定场景以外，盲目扩大适用范围，从而导致侵犯其他专利权人的合法权益。

参考文献：

[1] 距离和相似度度量[EB/OL].http：//wenku.baidu.com/view/326b752f4b73f242336c5f1 8.html？re=view.

[2] Navarro G，Raffinot M.柔性字符串匹配[M].中科院计算所网络信息安全研究组，译.北京：电子工业出版社，2007.

[3] 最长公共子序列[EB/OL].http：//baike.baidu.com/view/2020307.htm.

[4] 一种获取字符串最长公共子串的方法[P].发明专利号CN201110152462.1.

[5] 编辑距离[EB/OL].http：//baike.baidu.com/link？url=03graKvnemYCUKSst-2s6_h96xP– mu137oc__RjrwW501ubGvyMv6jUVRshXvb4eOlql8mxwp3BX_ShLkuEU8q.