王華敏，黃夢醒，馮文龍，馮思玲

(海南大學，海南 ?？?570228)

1 引言

目前存在許多基于字符相似度匹配的算法，比如edit distance，affine gap distance，Simth-Waterman distance，Jaro distance metric和Q-gram distance[1]或者在此基礎(chǔ)上改進的算法，在處理拉丁文字的字符串匹配時，都能起到良好的效果。它們最先的設(shè)計目地也是為了處理拉丁文字遇到的字符匹配問題，因此在面對漢字的時候，效果往往差強人意。

針對漢字相似度匹配問題，在主流算法的啟發(fā)下，許多研究者意識到可以將漢字先進行統(tǒng)一編碼，編碼時體現(xiàn)漢字特征的差異性，然后再將傳統(tǒng)的拉丁字符匹配算法應用于漢字編碼，可以大大提高準確率。

字形上，王東[2]等人把漢字表示為漢字結(jié)構(gòu)、字首部件、和字尾部件三元組。祁俊輝[3]等人提出了基于特征向量和筆順編碼的字形相似算法，充分利用漢字結(jié)構(gòu)、輪廓、筆畫、書寫順序等特征來識別漢字。缺點在于組建漢字特征向量庫后期還需要投入大量的工作，不過組建筆順編碼數(shù)據(jù)庫值得借鑒。

發(fā)音上，已經(jīng)有處理拉丁文字的Soundex算法，但是漢字種類繁多，且受方言影響，此算法無法滿足要求。

音形結(jié)合上，俞榮華[4]等人在處理多語言文本的相似重復記錄時，利用漢字的拼音序、筆劃序、部首序?qū)h字進行排序處理，缺點是這種方法對漢字的特征差異描述還較為粗略。陳鳴[5]等人歸納出音形碼，但拼音碼沒有體現(xiàn)出拼音發(fā)音的漸進變化，因此存在一個字對與之相近的發(fā)音字，與不相近發(fā)音字求出來的距離是一樣的，而字形部分采用四角編碼，只能粗略描述漢字的字形。周昊[6]等人在陳鳴的基礎(chǔ)上改進了音形碼的編碼方式，將音形碼按照發(fā)音以及字形的漸進變化編碼，最后檢測的結(jié)果更符合實際。但是其字形描述仍然采用四角編碼，仍然無法將字形細致的描述，從而體現(xiàn)差異性。

基于語義的方法主要是利用釋義詞典或者一些大規(guī)模的本體[7]對詞匯進行語義上的相似度計算[8]，可以將完全不一樣的文字，但表述相同語義的詞語相似度正確計算出來。其缺點是被檢測詞語必須完全準確，不能存在錯別字。

本文針對中文檢測算法音碼對漢字拼音描述不全，對漢字字形描述不夠精確，僅僅做意思檢測又太片面等缺點做出補充與改進，提出結(jié)合改進音形碼與Hownet的算法。該算法基于中文的音形義特征，較為全面的檢測相似度，大大提高了準確度。

具體工作：①改進音碼，重新考慮了拼音可能存在聲母缺失的情況。②改進形碼，將四角號碼改為筆順編碼，更加詳細描述漢字的結(jié)構(gòu)。③改進中文字符串相似度距離計算方法，在加權(quán)編輯距離的基礎(chǔ)上，考慮漢字可能存在字序改變而意思不變的情況。④設(shè)計了結(jié)合音形義的中文字符串相似度檢測算法。

2 相關(guān)工作

2.1 音碼

漢字拼音由聲母、韻母和聲調(diào)組成，其次，有些拼音中間還有一個韻母，如，“chuang”中的‘u’，因此還將考慮添加一位韻母補碼，最終生成的音碼應該包含聲母碼、韻母碼、音調(diào)碼、韻母補碼四個部分。

設(shè)計音碼時，想要充分體現(xiàn)拼音發(fā)音的差異性，需要了解哪些拼音特性會影響到需要表達的漢字，然后針對性的進行設(shè)計。我國省市眾多，不同的地方有著不一樣的方言，尤其南方的語言變化更多，南方人的發(fā)音更容易帶有方言特色，較為容易混淆。如，‘l’和‘n’，常常會有人將‘劉’和‘?！煜?，因此算法設(shè)計上可認為是發(fā)音相似；又如，‘a(chǎn)ng’和‘a(chǎn)n’，容易將‘床’和‘傳’混淆等。根據(jù)這些特性，得出容易混淆的發(fā)音具有更高的相似度。陳鳴[5]等人在設(shè)計音碼時，根據(jù)這個特征將拼音的四個部分對應轉(zhuǎn)為數(shù)字或者字母，其中容易混淆的聲母或者韻母轉(zhuǎn)化為同一個數(shù)字或者字母。

而周昊[6]等人在陳鳴的基礎(chǔ)上改進音碼的編碼方式，采用格雷碼表示聲母和韻母，然后計算其漢明距離體現(xiàn)相似度，其結(jié)果能充分體現(xiàn)出拼音發(fā)音習慣的差異。

要用格雷碼完全表示聲母和韻母，一共需要5+5+5個二進制位，即聲母碼、韻母碼、韻母補碼。而音調(diào)只有四聲，因此，一聲 (00)，二聲 (01)，三聲(10)，四聲 (11)。最后一共可以用17個二進制位表示音碼。

2.2 形碼

用來表達一個漢字的字形特征需要知道漢字的結(jié)構(gòu)，筆畫以及按字形的編碼，因此字形部分需要包括這三個部分[6]。由此，陳鳴等人對應設(shè)計了結(jié)構(gòu)碼，筆畫碼以及應用四角號碼對漢字字形進行編碼。其中四角號碼根據(jù)漢字四個角按順序?qū)h字編碼，分別是左上角、右上角 、左下角 、右下角，具體的取角規(guī)則可參考徐祖友[9]。

考慮到結(jié)構(gòu)與結(jié)構(gòu)之間，有些存在相似性，可以在計算時加入考慮，周昊[6]等人根據(jù)這個特點改進了形碼，設(shè)計了針對結(jié)構(gòu)漸進變化的編碼方式，使得相似結(jié)構(gòu)間漢明距離相近。

2.3 HowNet

漢語博大精深，一個中文詞語通?？赡苡卸嘀匾馑迹粋€意思通常也可以用不同的詞語去描述，而由此產(chǎn)生的相似度問題是基于音形設(shè)計的算法無法解決的。因此，一些研究人員花費數(shù)十年的時間從各種詞典和語言知識庫篩選詞義，并用這些詞義對詞語進行注釋，以構(gòu)建基于詞義的語言知識，HowNet[10]就是此類最著名的知識庫之一[11]。而自從HowNet發(fā)布以來，引起了廣泛的關(guān)注，吸引了各種相關(guān)研究，如葛斌[12]等人，劉群[13]等人對基于知網(wǎng)的詞匯語義相似度計算方法進行研究。其中劉群等人的詞語相似度檢測算法，是最具影響力的研究之一。

HowNet考慮到每個詞語的多義性，為其注釋了不同的含義，每個含義用中英文表達。如，對于“蘋果”這個詞的注釋，它包括“電腦”、“電話”、“水果”、“樹”這四種含義，每個含義下面又有相應的解釋。

HowNet從提出至今不斷完善，最新版本取名OpenHowNet，包含了HowNet的核心數(shù)據(jù)，并提供免費下載，此外還提供了OpenHowNet API，包含了詞語的相似度計算接口，其算法基于[14]提出。本文詞語語義相似度計算使用的便是OpenHowNet API。

3 音形碼的改進

3.1 漢字音碼的改進

在音形碼的基礎(chǔ)上，通過實驗研究，發(fā)現(xiàn)有些拼音是沒有聲母的，如‘額’的拼音“e”，而它與“de”，“l(fā)e”都有較高的相似度，所以缺少時，可以用一個相對與“00000”、“11111”有差不多漢明距離的編碼。同理，聲母和韻母中間不存在補碼的，也取與兩端差不多距離的編碼。改進后的拼音編碼見表1、表2。

表1 拼音聲母編碼

表2 拼音韻母編碼

聲母碼、韻母碼、韻母補碼一共占有15個二進制位，音調(diào)只有四聲，一聲 (00)，二聲 (01)，三聲(10)，四聲 (11)。最后一共可以用5+5+5+2個二進制位表示音碼。

因此，基于音碼的漢字相似度計算公式為

(1)

其中，h(a，b)為漢字a，b的音碼漢明距離，len(a)為a的音碼長度，即17。

改進后的音碼可以補充拼音缺少韻母和聲母的情況，提高音碼相似度檢測的準確率。

3.2 漢字形碼的改進

陳鳴[5]等人的形碼是基于結(jié)構(gòu)碼，筆畫碼以及應用了四角號碼表示?？紤]到四角號碼是根據(jù)字的左上角、右上角 、左下角 、右下角取碼，存在無法細致描述字形的情況，因此本文采用筆順編碼代替。

根據(jù)漢字編碼規(guī)則，任何漢字的結(jié)構(gòu)都可以分成橫、豎、撇、捺、折，即五筆結(jié)構(gòu)。按照這個思路，可以將每個漢字的書寫筆畫對應相應的五筆編碼，然后根據(jù)筆畫出現(xiàn)的順序，依次記下編碼，即得到筆順編碼，其中筆畫數(shù)即筆順編碼的字符長度。而筆順編碼是比較成熟的漢字表示方式，比較容易得到。按照編碼規(guī)則對任意漢字生成的編碼字符串，簡稱漢字筆順編碼。漢字筆畫編碼規(guī)則見表3。

表3 漢字筆畫編碼規(guī)則

如，‘優(yōu)’由撇、豎、橫、撇、豎彎鉤、點組成，根據(jù)對照表，對照生成筆順編碼“321354”。

筆順編碼反映了漢字的組成，相同的的編碼說明有相同的筆畫順序組成，在一定程度上可以反映漢字的相似程度，再加上漢字的結(jié)構(gòu)，這樣從組成因素和組成方式大致描述了漢字字形，由這兩部分編碼計算出來的相似度，可以描述出漢字的直觀形狀。

最終本文采用陳鳴的結(jié)構(gòu)碼，筆畫碼，而用筆順編碼代替四角號碼。改進后的形碼可以比較細致的區(qū)分字形差異。

4 中文字符串相似度檢測算法

4.1 改進形碼的漢字相似度檢測算法

生成包含結(jié)構(gòu)碼、筆畫碼、筆順編碼后的形碼后，漢字字形相似度便可以基于此形碼考慮。

漢字的直觀形狀受到結(jié)構(gòu)的影響，本文結(jié)構(gòu)碼采用周昊[6]等人在陳鳴基礎(chǔ)上提出的結(jié)構(gòu)碼，其優(yōu)勢在于體現(xiàn)漢字結(jié)構(gòu)的漸進變化。

筆畫在一定程度可以反饋漢字的復雜程度，筆畫越多通常字形越復雜，筆畫數(shù)差異越大則可以體現(xiàn)字形相似度越小。

不同漢字的筆順編碼并不是等長的，所以其相似度可以根據(jù)編碼的最長公共子串來度量，最長公共子串便是兩個相似的字形筆畫組成部分，相似筆畫越多，即最長公共子串占比越多，字形越相似。相似筆畫所在的位置也是影響字形相似度的一大因素。如，‘時’的筆順編碼為“2511124”，而‘如’的筆順編碼為“531251”，可知兩個字的筆順編碼最長公共子串為“251”，根據(jù)人們看漢字字形相似的習慣，字形的相似很大程度受到相似結(jié)構(gòu)位置的影響，由編碼“251”可知，他們相似的結(jié)構(gòu)分別為少最后一筆的‘日’以及‘口’。按照習慣，完全不會將這兩個字聯(lián)系在一起。因此需要考慮最長公共子串在筆順編碼里的位置差，差值越小，相似度越高。

綜合考慮漢字筆順編碼最長公共子串占比、漢字筆順編碼最長公共子串位置差、漢字筆畫、漢字結(jié)構(gòu)碼四個因素，設(shè)計基于改進形碼的漢字相似度檢測算法。

算法1：改進的的單個漢字字形相似度計算

輸入：漢字a、b

輸出：漢字a、b的字形相似度Simxing(a，b)。

Step1：生成a、b對應的筆順編碼，字形結(jié)構(gòu)碼，筆畫數(shù)。

Step2：考慮筆順編碼公共子串。由于公式計算需要，要先判斷a、b漢字哪個筆順編碼較短和較長，d=Min(len a，len b)，s=Max(len a，len b)，計算最長公共子串長度為Lcs＿len，則公共子串占比

(2)

Step3：考慮漢字筆畫。計算漢字筆畫差c=|len a-len b|，計算筆畫差對相似度的貢獻比

(3)

Step4：考慮筆順編碼最長公共子串的位置差。先得出最長公共子串在各自的位置。得到a的筆順編碼最長公共子串位置為a＿p，b的為b＿p，其中a＿p和b＿p分別為子串第一位在筆順編碼中的位置，計算差值p=|a＿p-b＿p|，最后得到位置對相似度的貢獻比

(4)

Step5：考慮漢字結(jié)構(gòu)。計算結(jié)構(gòu)碼的漢明距離ham，然后根據(jù)漢明距離計算結(jié)構(gòu)因素

(5)

Step6：考慮到相似度不超過1，且分別需要考慮筆順編碼最長公共子串、漢字筆畫數(shù)、筆順編碼最長公共子串所處的位置差異、漢字結(jié)構(gòu)差異。設(shè)置貢獻參數(shù)：α，β，i，j。本文分別設(shè)置為0.6，0.2，0.1，0.1，得到相似度計算公式

(6)

4.2 漢字音碼或形碼單個特征的中文字符串相似度檢測算法

文獻[15]提出將中文相似度計算分為一階相似度計算和二階相似度計算，即漢字相似度計算和中文字符串相似度計算。其中二階相似度計算采用加權(quán)編輯距離，這種計算方式替換、刪除的操作代價不單純用0，1表示，而是利用單個漢字對比后的相似度表示。由于中文詞語存在改變字的順序而意思不變的情況，如，“互相-相互”，“察覺-覺察”等，按照此方法，沒法識別這些詞其實是同一個詞，所以不能單純按照字序分別比對詞語中漢字的相似度。

基于加權(quán)編輯距離，將詞語中的每個漢字轉(zhuǎn)換編碼后，分別比對，找出相互能夠匹配的最高精度詞語，然后計算其位置代價。如果詞語中的每個漢字都能找到自己精確匹配的漢字，則不計算位置代價。如，“不好-好壞”，顯然兩個字符串都有共同的漢字‘好’，首先將各自最高精度的字符相互匹配，則得到“不好-壞好”，然后再用加權(quán)編輯進行計算相似度，最后考慮位置替換代價。但是如果單純按照順序比對，則無法將這兩個字符串聯(lián)系在一起。而“互相-相互”，則各自能完全匹配，這時則不計位置代價，可以得到其相似度為1。

算法2：改進的基于漢字音或形單個特征的中文字符串加權(quán)編輯距離相似度算法

輸入：中文字符串s1、s2。

輸出：s1、s2的音或形相似度Sim(s1，s2)。

Step1：min＿s=Min(s1，s2)，max＿s=Max(s1，s2)，將min＿s和max＿s中的所有漢字轉(zhuǎn)為音碼或者形碼。

Step2：將min＿s中的所有漢字與max＿s中的所有漢字遍歷進行相似度計算，min＿s中每個字對應max＿s中的相似度最近的一個字，將max＿s重新排序。如：“教師-你教的師”，則變成“教師-教師你的”；“相互-互相”，計算后得到“相互-相互”。

Step3：然后比較min＿s與max＿s的長度，如果等長且完全匹配，即每個漢字匹配組相似度都為1，則執(zhí)行Step 4，不考慮位置因素，否則Step 5，把位置因素考慮進去。

Step 4：

(7)

返回相似度，算法結(jié)束。其中sum＿sim為對應位置每組漢字的相似度和。

Step5：考慮位置因素。由于匹配時，max＿s的字符位置發(fā)生交換，則計算出交換前后的位置差，然后計算絕對值，設(shè)各個差值絕對值和為sum＿position，則位置影響因素。

(8)

Step6：將發(fā)生位置交換的max＿s與min＿s用加權(quán)編輯距離算法求編輯距離，即lds(max＿s，min＿s)。

(9)

Step7：得到字符串相似度

(10)

4.3 結(jié)合改進音形碼與Hownet的中文字符串相似度檢測算法

音、形、義是漢字的三大特征[15]，也是漢字相似度考慮的主要因素。主流中文詞語相似度檢測大多分別從音形或者詞義研究漢語相似度，對于結(jié)合二者的研究相對較少，而二者皆有各自優(yōu)缺點。如，“西紅柿”與“番茄”，光考慮音形，無法確定其相似度；而“彬彬”與“杉杉”光從詞義也無法確定其相似度。針對此問題，提出結(jié)合改進音形碼與HowNet的算法，從音形義三個方面綜合考慮中文字符串的相似度。

在此算法設(shè)計中，需要考慮以下幾種情況：①相同的意思，完全不同的詞表達。設(shè)置閾值為t，如果單個特征相似度大于t，可以認為單個特征高度相似，則不考慮其他兩個特征。②當詞語存在錯別字時，詞語本身是無意義的，要判定它的相似度，必須要將其轉(zhuǎn)換成與其最為相似而有意義的詞語，再進行相似度比較。③當三個特征相似度都較低時，可以針對應用場景，分別設(shè)置各個特征的貢獻參數(shù)。

由此，設(shè)計算法3。其中，算法3出現(xiàn)的基于音碼的中文字符串相似度檢測(Simyin)和基于形碼的中文字符串相似度檢測(Simyi)算法皆是算法2。

算法3：基于音形義的中文字符串相似度檢測算法

輸入：中文字符串s1、s2。

輸出：s1、s2的相似度Simzong(s1，s2)。

Step 1：先將s1，s2進行意思檢測，看看是否都有意義，如果有，先進行賦值操作，s1＿change=s1，s2＿change=s2，num=0，然后執(zhí)行Step 3；如沒有意義，則直接執(zhí)行Step 2。

Step2：將無意義的字符串進行單個相似漢字替換，數(shù)據(jù)庫為漢字同音詞或者形近詞庫，替換后的詞語再進行意思檢測，循環(huán)到找到最接近相似度詞語為止，然后設(shè)置替換懲罰參數(shù)f，被替換字數(shù)為num。根據(jù)實驗經(jīng)驗，這里的f設(shè)置為0.1。替換后的字符串分別對應為s1＿change、s2＿change。

Step3：分別計算s1＿change、s2＿change的意思相似度

simyi(s1，s2)=simyi(s1＿change，s2＿change)-f×num

(11)

Srep4：計算s1、s2的音形相似度，根據(jù)貢獻值a、b、c求最后相似度，其中a+b+c=1。如果單個特征相似度大于t，則以此特征為準，而不考慮另外兩個特征的相似度。

Simzong=simyin×a+simxing×b+simyi×c

(12)

5 實驗結(jié)果與數(shù)據(jù)分析

5.1 實驗方案

以陳鳴[5]提出的音形碼作為基礎(chǔ)，用編輯距離計算字符串音形碼相似度作為方法1，以HowNet義原檢測作為方法2，以本文提出的基于音形義檢測算法作為方法3。各方法比較如圖1。

圖1 各方法基于特征比較

實驗方案：

方案1：選取12組典型中文字符串進行實驗，比對音形義相似的情況。最后對結(jié)果進行分析比較，如圖2。

圖2 典型中文字符串相似度計算結(jié)果比較(方案1)

方案2：分別用以上三個方法檢測近義詞大全[16]，一共730組近義詞。閾值都設(shè)為0.6，分別比較篩選出近義詞的準確率，比較結(jié)果如圖3。

圖3 近義詞識別率比較(方案2)

方案3(本文方法)：分別用以上三個方法檢測高中語文錯別字[17]，截取前85組近形(音)詞。閾值分別設(shè)為0.6、0.7、0.8、0.9，比較三種算法篩選出近義詞的準確率，比較結(jié)果如圖4。

圖4 形(音)近詞識別率比較(方案3)

方案4：任意找一段文本(共1000字左右)[18]，隨機位置插入10個詞語，分別為：相互、西紅柿、藩茄、教師、衰豪、倉黃、徘回、悲創(chuàng)、宛轉(zhuǎn)、凜列，找出人工判別對應相似的詞語，分別為：互相、番茄、老師、哀嚎、蒼黃、徘徊、悲愴、婉轉(zhuǎn)、凜冽。用以上三個方法分別對文章進行文本檢測，閾值分別設(shè)置為0.6，0.7，0.8，分析詞語分類結(jié)果，如圖5。

圖5 詞語檢測召回率比較(方案4)

5.2 評判標準

由于中文詞語相似度評價沒有通用標準，受主觀因素影響，所以主要按照人工判別的方式去比較各種方法的優(yōu)劣。大致評價標準：相似度小于0.5時，為不相似；相似度為0.5-0.6，則說明有關(guān)聯(lián)性；相似度0.6-0.8為比較相似；相似度0.8-0.9為相似；相似度0.9-1.0為非常相似。

5.3 結(jié)果分析

經(jīng)過多次實驗，4種方案實驗結(jié)果以及結(jié)果分析如下。

對圖2(方案1)分析如下：

1)對于“相互-互相”這類詞語，字序改變，詞義不變。方法1所得相似度沒有參考價值，而方法2和方法3的算法基于語義，可以有效識別。

2)對于“西紅柿-番茄”這類詞語，描述方法不一樣，而意思一樣的詞語，方法1也沒有參考價值，而方法2、方法3則表現(xiàn)良好。

3)對于“番茄-藩茄”這類詞語，假設(shè)其中有錯別字，而HowNet語料庫中是不可能存在這種錯別字詞語的，因此返回Null，沒有參考價值。而基于音形碼的方法1和基于音形義的方法3則具有一定參考價值，其中，方法3可以識別“藩茄”可能描述的詞語為“番茄”，所以可以得出較高的相似度。

4)對于“男人-和尚”，“男人-鯉魚”，顯然，“男人”和“和尚”有較高的關(guān)聯(lián)，而方法1并不能體現(xiàn)，而方法2則把前者的相似度計算的過于高了，方法3則體現(xiàn)其具有關(guān)聯(lián)性，比較符合實際。

對圖3(方案2)分析如下：

本次實驗用三種方法從730組近義詞中進行相似度計算，從而分析識別率。其中方法1識別組數(shù)為236組，識別率為32.3%，方法2識別組數(shù)為509組，識別率為69.7%，方法3，也就是本文提出的算法，識別組數(shù)為529組，識別率為72.5%?？梢钥闯霰疚姆椒ㄏ鄬ζ渌椒ㄌ岣吡俗R別率。

對圖4(方案3)分析如下：

由于錯別字組成的詞語，HowNet詞庫并未收錄，因此方法2基本失效，而當相似度閾值設(shè)置為0.6時，方法1與方法3效果相同，但是隨著閾值的不斷增加，方法1顯然效果大大減小，其相似度分散在0.6-08之間，應用方法2在多組詞組中找相似詞組時，容易受其他詞組的影響，而方法3，即本文方法，則可以在比較高的相似度下將形(音)近字篩選出來，在干擾下篩選詞語的效果顯然會強于方法1。

對圖5(方案4)分析如下：

檢測隱藏在文本中的詞語，當閾值為0.6時，方法1召回率為70%。方法2召回率為30%。本文方法召回率為100%；當閾值為0.7時，方法1召回率為50%。方法2召回率為30%。本文方法召回率為90%；當閾值為0.8時，方法1召回率為30%。方法2召回率為30%。本文方法召回率為70%。實驗表明，在文本中檢測相似詞，本文方法效果明顯最好。

以上結(jié)果表明，無論是從音形還是詞義檢測中文詞相似度，本文提出的算法都有更好的表現(xiàn)。

6 結(jié)論

1)通過完善拼音編碼，算法提高了中文近音詞檢測精度。

2)通過優(yōu)化字形編碼方式，算法在近形詞檢測中表現(xiàn)更好。

3)在近義詞檢測方面，算法可以允許被檢測詞出現(xiàn)錯別字的情況，識別率提高2.8%。

4)算法可滿足多種應用場景，如，結(jié)構(gòu)化數(shù)據(jù)項重復性檢測，特別是存在手工輸入錯誤的情況；另外，也可應用于存在利用別字隱藏敏感詞的文本檢測等。