吳宏洲

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

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

中圖分類號：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

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

1 實驗背景

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

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

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

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

1.1.1 余弦相似度

定義：

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

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

1.2.1 編輯距離Levenshtein相似性算法

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

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

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

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

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

例如：字符串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

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

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

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

1） 基于連續(xù)文字串單元塊，以單元塊為單位統(tǒng)計塊數(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%，認為相似；V<50%，認為不相似。

2） 基于連續(xù)字符串單元塊字符數(shù)，以單元塊為單位統(tǒng)計字符數(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%，認為相似；V<50%，認為不相似。

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

定義：SWHZ= SWHZ1* SWHZ1。

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

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

兩個句子比對相似度算法，描述如下：

[兩個句子比對相似度算法，描述如下：

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

4 結(jié)論

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

參考文獻：

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

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

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

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

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