句子比較相似度的算法實(shí)現(xiàn)?

吳宏洲

摘要：一種文本句子比較相似度算法，以連續(xù)文字串為單元塊，相同單元塊越大越多越相似，相異部分的單元塊越小越少越相似，依此計(jì)算相似度值?？捎脕?lái)消除傳統(tǒng)相似度取值置信區(qū)間中模糊區(qū)，精確到一個(gè)非此即彼的二元邏輯值。

關(guān)鍵詞：文本句子比較；連續(xù)文字串；單元塊；相似度

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

在專利文獻(xiàn)自動(dòng)摘要的技術(shù)研究與應(yīng)用中，需要了解專利說(shuō)明書中最具代表性的發(fā)明內(nèi)容部分、權(quán)利要求書中最具代表性的獨(dú)立權(quán)利要求部分，還包括發(fā)明的有益效果。這些部分摘選組合搭配是重構(gòu)專利摘要的重要依據(jù)。從文獻(xiàn)中抽取所需的最能代表發(fā)明專利中其技術(shù)方法的最重要的句子成分，作為文摘參考備選，這一過(guò)程是自動(dòng)摘要的一個(gè)重要技術(shù)環(huán)節(jié)。然而在抽取技術(shù)特征最為集中的句子時(shí)，如果單單以句子本身的權(quán)重為依據(jù)來(lái)抽取句子的話，那么很有可能將某些句子權(quán)重高、相似度也高的句子同時(shí)都抽取出來(lái)。從而忽略了其他次重要的句子，從而導(dǎo)致算法偏好失衡。這時(shí)就需要用到一個(gè)句子比較相似度的方法，將相似內(nèi)容的句子依據(jù)權(quán)重以及位置作取舍，對(duì)舍去的句子作參考值權(quán)重的衰減，從而達(dá)到消除相似或重復(fù)的內(nèi)容的目的，使算法趨于偏好均衡。目前句子比較相似度算法大家公認(rèn)的算法多采用cosine相似度算法，該算法取值通常會(huì)在[下限值，上限值] 置信區(qū)間的廣闊中間區(qū)域出現(xiàn)判斷上的不確定性，使得相似度算法的能力受到質(zhì)疑。因此，筆者在重新考察句子間似與不似的成因時(shí)，發(fā)現(xiàn)了一個(gè)更簡(jiǎn)單有效的算法，可以很好地區(qū)分似與不似問(wèn)題。其實(shí)驗(yàn)效果與筆者的預(yù)想有某種契合，筆者還不能證明其是否真正合理，或者說(shuō)還沒(méi)有找到一個(gè)反例推翻實(shí)驗(yàn)的巧合。這就是本文公開這一算法的真正目的。

1 實(shí)驗(yàn)背景

筆者在專利文獻(xiàn)自動(dòng)摘要的研究試驗(yàn)中發(fā)現(xiàn)，解讀分析專利的權(quán)力要求，會(huì)大量出現(xiàn)內(nèi)容相同或相似的句子，在不同的權(quán)力要求中反復(fù)出現(xiàn)，特別是某些重要的句子。如果，按照權(quán)重來(lái)簡(jiǎn)單抽取句子的話，那么等于該句子被抄寫了N遍，擠掉了其他句子的出現(xiàn)機(jī)會(huì)。所以就加入了cosine相似度算法去重。對(duì)相似度高的句子，依據(jù)位置、權(quán)重作取舍，對(duì)舍去的句子作權(quán)重作衰減。試驗(yàn)還是不理想，結(jié)果也和預(yù)想的不一致。大概是該去的還在，該留的沒(méi)了。索性對(duì)相似度相關(guān)算法重新調(diào)研，又納入了3個(gè)算法。實(shí)驗(yàn)結(jié)論是已有算法多以詞頻統(tǒng)計(jì)為基本原理，來(lái)猜測(cè)兩個(gè)句子之間的相似度。會(huì)忽略詞的內(nèi)涵和順序問(wèn)題。句式相似度很高，結(jié)論相反的句子，不能識(shí)別。參見(jiàn)《表1.句子相似度算法效果比對(duì)樣例》序號(hào)2樣例。筆者將重要的對(duì)比句子樣例，按照cosine相似度排序依依列出來(lái)，然后重新標(biāo)注出相同、相異的連續(xù)文字串單元塊。參照jaccard方法，按照塊數(shù)計(jì)算，按照字符串長(zhǎng)度計(jì)算，兩者合取的結(jié)果恰恰將表1的樣例，似與不似，分得清清楚楚。后來(lái)花費(fèi)了一些時(shí)間，網(wǎng)上搜索了與字符串匹配相關(guān)的方法，沒(méi)有找到與筆者完全相似的方法，以及用于相似度計(jì)算的類似方法也很有限。現(xiàn)在可以對(duì)文本句子比較相似度的方法重新進(jìn)行歸納了。

文本句子比較相似度的簡(jiǎn)約方法目前有基于詞頻的統(tǒng)計(jì)方法和基于連續(xù)字符串的方法。

1.1 基于詞頻統(tǒng)計(jì)的相似度算法

該方法主要通過(guò)分詞技術(shù)和統(tǒng)計(jì)詞頻的思路來(lái)計(jì)算相似度。其中比較流行的是cosine、tanimoto、euclid和jaccard算法[1]。還有對(duì)數(shù)似然相似度算法，但是筆者將其列為復(fù)雜算法而略去。

1.1.1 余弦相似度

定義：

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

在已有技術(shù)中，基于字符串的匹配的相似度算法，目前還不多見(jiàn)。有些流行的方法，大都是與串匹配的方法相關(guān)，與相似度算法不直接相關(guān)。例如：kmp、horspool、boyer-mou和Sunday等算法[2]。另外，網(wǎng)上目前能夠見(jiàn)到的兩個(gè)常用字符串相似度算法是：最長(zhǎng)公共子串（LCS）[3-4]，編輯距離或者Levenshtein距離相似度方法[5]。

1.2.1 編輯距離Levenshtein相似性算法

編輯距離，又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。一般來(lái)說(shuō)，編輯距離越小，兩個(gè)串的相似度越大。

例如：GUMBO和GAMBOL；由GUMBO變?yōu)镚AMBOL，需要編輯變動(dòng)最少要3次。則：

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

1.2.2 最長(zhǎng)公共子串相似度算法

求兩個(gè)字符串最長(zhǎng)公共子串[3]。解法就是用一個(gè)矩陣來(lái)記錄兩個(gè)字符串中所有位置的兩個(gè)字符之間的匹配情況，若是匹配則為1，否則為0。然后求出對(duì)角線最長(zhǎng)的1序列，并替換成自然數(shù)序列。其對(duì)應(yīng)的位置就是最長(zhǎng)匹配子串的位置。

例如：字符串21232523311324和字符串312123223445的匹配矩陣，前者為X方向的，后者為Y方向的。為“21232”長(zhǎng)度為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

另外落稿前還發(fā)現(xiàn)了一種以尋求病毒或基因序列為特征的最長(zhǎng)公共子序列的算法，如：發(fā)明專利號(hào)CN201110152462.1 [4]。

1.2.3 SWHZ字符串單元塊相似度算法

SWHZ相似度算法屬于筆者自定義的方法，以連續(xù)文字串為單元塊，相同單元塊越大越多越相似，相異部分的單元塊越小越少越相似，依此計(jì)算相似度值。由兩個(gè)互為修正的子算法組成，該算法不僅與單元塊相關(guān)，還受限于塊的大小，與塊的大小或字符數(shù)相關(guān)。是由兩者的合取得到的。與本算法比較接近的算法有jaccard算法、kmp算法和發(fā)明專利CN201110152462.1算法，但在用途、適用場(chǎng)景和算法實(shí)現(xiàn)上都有一定區(qū)別。

1） 基于連續(xù)文字串單元塊，以單元塊為單位統(tǒng)計(jì)塊數(shù)，相同單元塊數(shù)和相異單元塊數(shù)之間的占比算法，用SWHZ1表示；

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

BA∩B表示相同單元塊數(shù)；BA∪B表示相同單元塊數(shù)加相異單元塊數(shù)；（BA-B + BB-A）表示相異部分單元塊數(shù)。

V≥50%，認(rèn)為相似；V<50%，認(rèn)為不相似。

2） 基于連續(xù)字符串單元塊字符數(shù)，以單元塊為單位統(tǒng)計(jì)字符數(shù)，相同單元塊的字符數(shù)和相異單元塊字符數(shù)之間的占比算法，用SWHZ2表示。

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

CA∩B表示相同單元塊字符數(shù)；CA∪B表示相同單元塊字符數(shù)加相異單元塊字符數(shù)；（CA-B + CB-A）表示相異部分單元塊字符數(shù)。

V≥50%，認(rèn)為相似；V<50%，認(rèn)為不相似。

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

定義：SWHZ= SWHZ1* SWHZ1。

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

2 SWHZ句子比對(duì)相似度算法的技術(shù)實(shí)現(xiàn)

兩個(gè)句子比對(duì)相似度算法，描述如下：

[兩個(gè)句子比對(duì)相似度算法，描述如下：

//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）；// 首個(gè)漢字或西文字母

if（s1_1！∈ s2） {

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

while（s1_1.string ﹦ COMMA） || （s1_1.string ！∈ s2）） { // 逗號(hào)不作首字

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） { // 取位置集，分別計(jì)算首字在串中匹配位置長(zhǎng)度串長(zhǎng)

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） { // 在前最大串長(zhǎng)

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） { // 同理：取位置集，分別計(jì)算匹配串長(zhǎng)

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；＼&]

算法過(guò)程說(shuō)明：

[初始：

Same_set={}，Diff_set={}；

兩串比較開始：S1、S2

[

如表1所見(jiàn)。其中“結(jié)果I”是通過(guò)cosine相似度算法取值，當(dāng)出現(xiàn)在62%～90%之間模糊區(qū)時(shí)，繼續(xù)采用euclid算法取值，得到的結(jié)果，也不能將表1所列樣例區(qū)分干凈?！癝WHZ標(biāo)記”是本文算法得出的結(jié)論，“結(jié)果II”是人工標(biāo)引的結(jié)論，兩者基本一致。而“評(píng)測(cè)”是“結(jié)果I”與“結(jié)果II”的一致性標(biāo)注，有6個(gè)“相反”的結(jié)論，說(shuō)明傳統(tǒng)算法存在誤判。其中序號(hào)18的樣例，是一個(gè)典型的量變到質(zhì)變，由SWHZ2修正了SWHZ1的結(jié)論；同樣序號(hào)3的樣例，由SWHZ1修正了SWHZ2的結(jié)論；而序號(hào)2的樣例，是一個(gè)cosine相似度高，結(jié)論相反的典型樣例，被SWHZ檢測(cè)出不相似，效果明顯優(yōu)于傳統(tǒng)算法。

4 結(jié)論

在文本句子間比較相似度這一特定應(yīng)用場(chǎng)景下，筆者所提出的SWHZ相似度算法，主要是針對(duì)已有傳統(tǒng)基于詞頻統(tǒng)計(jì)的方法存在不足，取值范圍會(huì)在某個(gè)最大臨界點(diǎn)和最小臨界點(diǎn)之間出現(xiàn)判斷上的模糊區(qū)域，使得相似度算法應(yīng)用受到質(zhì)疑。SWHZ相似度算法可以用來(lái)消除傳統(tǒng)相似度取值置信區(qū)間中的模糊區(qū)域，使之得到一個(gè)非此即彼的二元邏輯值：像或是不像。本文還推薦該方法并建議與傳統(tǒng)cosine相似度簡(jiǎn)約算法相結(jié)合，作為cosine的補(bǔ)充算法。僅當(dāng)cosine相似度取值在62%～90%區(qū)間時(shí)使用，用于進(jìn)一步判斷相似性。只有在判斷符合相似的結(jié)論下，才宜用cosine相似度值作為相似程度的解釋，否則應(yīng)該衰減cosine取值到低于62%，或者用低于25%的SWHZ實(shí)際值取代。這樣使得綜合修正后的cosine相似度的有效取值，可以擴(kuò)展范圍到62%～100%之間。筆者需要特別強(qiáng)調(diào)的是該算法未證明直接適用于文本句子間比較以外的擴(kuò)展用途。例如：直接文章比較、直接段落比較，以及用于基因序列比較等復(fù)雜應(yīng)用場(chǎng)景。既不接受植入其它修正方案，也不推薦應(yīng)用于本文特定場(chǎng)景以外，盲目擴(kuò)大適用范圍，從而導(dǎo)致侵犯其他專利權(quán)人的合法權(quán)益。

參考文獻(xiàn)：

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

[2] Navarro G，Raffinot M.柔性字符串匹配[M].中科院計(jì)算所網(wǎng)絡(luò)信息安全研究組，譯.北京：電子工業(yè)出版社，2007.

[3] 最長(zhǎng)公共子序列[EB/OL].http：//baike.baidu.com/view/2020307.htm.

[4] 一種獲取字符串最長(zhǎng)公共子串的方法[P].發(fā)明專利號(hào)CN201110152462.1.

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