句子比較相似度的算法實現?

吳宏洲

摘要：一種文本句子比較相似度算法，以連續文字串為單元塊，相同單元塊越大越多越相似，相異部分的單元塊越小越少越相似，依此計算相似度值?？捎脕硐齻鹘y相似度取值置信區間中模糊區，精確到一個非此即彼的二元邏輯值。

關鍵詞：文本句子比較；連續文字串；單元塊；相似度

中圖分類號：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的樣例，似與不似，分得清清楚楚。后來花費了一些時間，網上搜索了與字符串匹配相關的方法，沒有找到與筆者完全相似的方法，以及用于相似度計算的類似方法也很有限?，F在可以對文本句子比較相似度的方法重新進行歸納了。

文本句子比較相似度的簡約方法目前有基于詞頻的統計方法和基于連續字符串的方法。

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所列樣例區分干凈?！癝WHZ標記”是本文算法得出的結論，“結果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.