基于改進編輯距離的中文字符精細化匹配研究

相似度的計算作為一種通用字符串近似匹配的測量方法，中文字符串相似度的計算在中文檢索、中文信息過濾、中文orc識別、中文叢書等領(lǐng)域得到了廣泛應(yīng)用?，F(xiàn)有的計算字符串相似度的方法按照計算所依據(jù)的特征的不同,可以劃分為三種:基于字面相似的方法、基于統(tǒng)計關(guān)聯(lián)的方法、基于語義相似的方法。文獻將三種方法融合后提出了一種基于多層特征的計算模型;文獻和文獻專門針對中文信息過濾中存在的網(wǎng)頁中惡意夾雜關(guān)鍵詞、變形關(guān)鍵詞等情況,在匹配算法上進行了改進。然而,根據(jù)已有資料的分析,目前在這些計算字符串相似度的算法、近似匹配的算法中,都存在一個假設(shè):中文字符串匹配的最小單元為單個漢字,換句話說,目前大多數(shù)方法并沒有考慮漢字自身特征的差異對中文字符串相似度的影響。從形式化角度分析,若以T、P代表中文字符串,Ti、Pj表示單個中文字符,1≤i≤m,1≤j≤n,那么兩個中文字符串的近似匹配如圖1所示。由圖1可以看出,中文字符串的近似匹配建立在單個中文字符即漢字比較的基礎(chǔ)上。然而,漢字間的比較結(jié)果通常只有匹配與不匹配兩種情況,以0、1或False、True的形式表示。例如,比較“公園”、“公元”與“公務(wù)”三個詞,用傳統(tǒng)的編輯距離方法,它們之間的相似度都是0.5。然而根據(jù)直觀感受,顯然“公園”與“公元”的相似程度要遠遠大于“公園”與“公務(wù)”的相似度,其原因在于,“園”與“元”的相似度大于“園”與“務(wù)”之間的相似度。當前,研究者已經(jīng)提出了利用漢字可以分解的特征來解決這個問題,其中文獻中提出的基于拼音索引的中文模糊匹配算法采用了漢字、拼音和拼音改良的編輯距離,文獻給出了一種相似匹配算法并應(yīng)用于拼音相似度的計算,文獻提出了利用漢字機內(nèi)編碼進行相似度計算,文獻和文獻則針對字形特征對漢字進行了相似度計算,但大多數(shù)研究僅限于漢字的單一特征分析,忽略了漢字的全特征分析。雖然文獻專門針對因編輯行為引起的字符串相似重復(fù)的情況,給出了一種基于拼音編碼和五筆編碼的編輯距離與基于字符的編輯距離融合的計算方法,但沒有給出具體的依據(jù)以及漢字特征分析的系統(tǒng)證明與描述?；谶@些考慮,本文將從漢字的基本特征入手,對其進行聚類分析,給出“相似”的合理證明,在此基礎(chǔ)上,對已有的算法進行改進,試圖給出一個不限應(yīng)用領(lǐng)域的計算中文字符串相似度的普適方法。2字段特征分析2.1同音同鍵映射英文中已有根據(jù)語音的相似性來計算字符串相似度的語音匹配算法,最廣為人知的語音算法是Soundex算法,它首先提出了按照發(fā)音而不是按照字母表的方式對單詞進行分組。Soundex算法的運作方式是把某個字母表中的每個字母映射成代表它的語音組的一個數(shù)字代碼。在這個方案里,像d和t這樣的字母在同一個組中,因為它們發(fā)音相近,而元音則一概忽略。通過對整體單詞應(yīng)用這種映射,就產(chǎn)生了單詞的語音“鍵”(Key)。發(fā)音相近的單詞通常會有相同的鍵。如Smith和Smyth的Soundex都是S530。相似的對象組織到一起構(gòu)成的類可以稱之為簇。簇內(nèi)對象相似度大,簇間對象相似度小。因此,可以把一個鍵看作一個類簇,即存在一個鍵對應(yīng)的所有單詞屬于同一個類簇,它們之間語音非常相似,因此,英文單詞可以根據(jù)語音的相近而具有“成簇性”。2.2由語音“成簇性”到“形、義”根據(jù)Soundex算法的啟示,可以直觀地推測:同樣具有語音特征的中文也具有“成簇性”。同音字、近音字就是自然存在的語音類簇,如圖2所示:圖2中包含6組同音字,根據(jù)“cai”、“can”、“ca”、“dun”、“du”、“dui”的發(fā)音聚成6個類簇。進一步分析,可以觀察到不僅同音字具有“成簇性”,發(fā)音相近的漢字也具有語音“成簇性”,比如“cai”、“ca”、“can”三個發(fā)音之間本身就很相近,所以簇2、簇3、簇4也可以聚類為更大的簇1。同理,簇5、簇6、簇7可聚類為簇2。依此類推,其他發(fā)音相似的漢字也具有聚簇性。音、形、義被歸納為漢字的三大特征。漢字之間可以因其“音”的相同或相似而相似,也可以因為“形”的相近而相似,也可因“義”的相近而相似。為更好地證明此結(jié)論的正確性,分別以語音特征和字形特征作為基礎(chǔ),對漢字進行聚類分析。由于目前對“義”還沒有一個明確的度量標準,這里暫不考慮這種情況。具體實現(xiàn)則分別以“表音”的拼音編碼和“表形”的五筆字型編碼為聚類對象,以編碼之間的編輯距離作為聚類依據(jù),通過計算編碼之間的編輯距離確定漢字的相似度,根據(jù)相似度的大小實現(xiàn)聚類。(1)結(jié)果不自然針對408個拼音編碼,分別以50-200個類簇為指標進行聚類分析,在得到的實驗結(jié)果中,以聚類特征明顯為原則,根據(jù)實際情況選擇合適的類簇數(shù)量,可以找出當聚類為52個簇時,結(jié)果較為自然。選取其中的5組聚類結(jié)果,如下所示:(1)[miao,jiao,diao,biao,tiao,qiao,xiao,piao,liao,niao](2)[gai,wai,bai,lai,mai,ai,tai,sai,nai,dai,cai,kai,pai,zai](3)[hui,gui,rui,sui,cui,dui,kui,tui](5)[chong,cheng,chang]從聚簇結(jié)果可以清楚地看出,拼音相似的編碼基本分布在相同的簇中,這說明拼音編碼具有語音“成簇性”特征。(2)漢字“成簇性”與“形”對于五筆編碼,同樣以上述方式進行聚類分析,以50-500個類簇為指標,分別計算,較為自然的聚類結(jié)果是聚為360個類簇,從中抽取5組數(shù)據(jù)作為代表,如下所示:(1)[lfou(黑),lfoj(黯),klfo(嘿)](2)[vldy(姻),oldy(煙),kldn(嗯),kldy(咽)](4)[ptfq(憲),pfqb(完),pfqc(寇),pfqf(冠),pfq(完)](5)[fnrt(場),rnrt(揚),enrt(腸),fnr(聲),snrt(楊),qnrc(飯),inro(燙),inrt(湯)]從實驗結(jié)果可以看出,形近字分布在同一個類簇中,幾組數(shù)據(jù)均基本符合“成簇”的特征。因此,說明“形”似的漢字也具有聚類特征。從上述兩個實驗可以看出,正是由于漢字“成簇性”的存在,在組成字符串的過程中,不可避免組合錯誤的產(chǎn)生。比如音的“成簇”會導(dǎo)致同音字、近音字替換,形的“成簇”會引起形似字替換,義的成簇則會導(dǎo)致近義詞混淆的情況。明確漢字的“成簇性”特征,是中文字符串精細化匹配的前提。3基于改善編輯距離的相似性的模型設(shè)計3.1基于大陸法的相似度修正算法字符串之間相似度的計算方法已經(jīng)有幾十種,本文采用其中最常用、最簡單的基于編輯距離的計算方法,以及在英文姓名匹配中廣泛使用的Jaro-Winkler距離模型。這兩種計算方法的結(jié)合可以覆蓋字符的插入、刪除、替換以及交換等基本錯誤。通過在大量實驗數(shù)據(jù)的基礎(chǔ)上對權(quán)值進行修正,以獲得對字符串間相似度更為精確的結(jié)果。本文使用以下符號描述中文字符串匹配算法:S={S1,S2,…,Si,…,Sm},i∈[1,m],S中含有m個漢字(包括重復(fù)字符),Si為單個漢字;T={T1,T2,…,Tj,…,Tn},j∈[1,n],T中含有n個漢字(包括重復(fù)字符),Tj為單個漢字。edit(S,T):S和T之間的編輯距離。Jaro-Winkler(S,T):S和T之間的Jaro-Winkler距離。3.2漢字圖像相似度的擴展根據(jù)分析知漢字具有“成簇性”,若要更加精細化地反映中文字符串的相似度,需要將其考慮在內(nèi)。因此,在計算中文字符串的相似度時,需要將漢字的相似度體現(xiàn)出來。首先需要計算漢字的相似度,在此基礎(chǔ)上計算漢字組成的中文字符串的相似度。由此,提出中文字符串的二階相似度計算模型。定義1:給定中文字符串S、T,二階相似度為融入漢字Si∈S、Tj∈T相似度后得出的S與T之間的相似程度。漢字Si和Tj之間的相似度為一階相似度,記為Sim(Si,Tj),S和T的相似度為二階相似度,記為Similar(S,T)。二階相似度是一般字符串相似度的擴展。一階相似度即漢字相似度。漢字的相似度建立在其特征相似的基礎(chǔ)上。概括地說,漢字具有音、形、義特征,漢字進入計算機,這些特征最直接地反映在各種編碼方案上。目前專家學者們提出的漢字編碼方案有近千個,已被采用的編碼方案達數(shù)十種之多,這些漢字編碼方案大致可以分為4種:(1)形碼:根據(jù)漢字的字形來進行編碼,如筆形編碼法和五筆字型編碼法;(2)音碼:根據(jù)漢字的讀音來進行編碼,一般以漢語拼音方案為根據(jù);(3)形音碼:這種方法立足于字形分解,把字分解為部件或筆畫,部件和筆畫統(tǒng)稱為字元,各個字元又通過它們的讀音來幫助記憶;(4)音形碼:以音為主,以形為輔的編碼,利用字形來區(qū)分同音字。定義2:反映漢字某一方面的特征的編碼方案稱為漢字的特征項。例如,五筆編碼規(guī)則反映漢字字形的特征,可以作為特征項;拼音規(guī)則反映漢字讀音特征,也是特征項。定義3:描述漢字c的特征項的字符串,稱為c對應(yīng)的一個Key。記為Keyfeature(c),其中feature表示特征項。設(shè)拼音編碼方案用py表示,五筆編碼方案用wb表示,則Keypy(c)可表示c的拼音編碼,Keywb(c)可表示c對應(yīng)的五筆編碼。于是,漢字c1和漢字c2的相似度可用Sim(Keyfeature(c1),Keyfeature(c2))表示。即:目前應(yīng)用較為普遍的漢字編碼方案都是以英文字符或數(shù)字的形式表示的,因此Keyfeature(c)代表的字符串只包含英文字母和數(shù)字,并且為短模式字符串。所以,Sim(Keyfeature(c1),Keyfeature(c2))也就是兩個短模式英文字符串的相似度。因此,Sim(c1,c2)可轉(zhuǎn)換為英文字符串匹配問題。英文字符串相似度計算的方法有很多,可采用簡單的編輯距離或Jaro-Winkler距離進行計算。(2)改進的編輯距離矩陣的計算二階相似度的計算采用加權(quán)編輯距離,這種模型適用于編輯操作具有不同代價的字符串匹配,在計算Mi,j時,每次增加編輯操作相應(yīng)的代價,而不是簡單地加1。這也符合本文所討論的情況。在考慮漢字“成簇性”的前提下,漢字之間具有相似度,所以在中文字符串匹配中,替換操作的代價不能僅憑0、1表示。為了體現(xiàn)原始字符與替換字符之間的相似度,令替換操作的代價為兩個漢字的相似度。設(shè)x與y為中文字符串中的單個漢字,則各編輯操作的代價為:其中:δ(x,ε)為刪除操作的代價;δ(ε,y)為插入操作的代價;δ(x,y)為替換操作的代價;Sim(x,y)為漢字x與y的相似度。由此,改進后的編輯距離矩陣M′計算過程為:將式(3)與式(1)合并為:設(shè)Edit′(S,T)為改進后的編輯距離,則當i=m,j=n時,Edit′(S,T)=M′i,j。由此得出,中文字符串的二階相似度為:4實驗與分析4.1算法結(jié)果對比選取200對中文字符串作為源數(shù)據(jù)進行實驗,涵蓋音似、形似等情況。分別以傳統(tǒng)的字符串相似度計算方法和本文提出的方法為模型,輸入數(shù)據(jù)進行計算,對計算結(jié)果進行分析比較。具體采用方法如下:(1)ED:基于編輯距離模型;(2)JW:基于Jaro-Winkler距離模型。(2)階相似度計算模型(1)EE+PY:以拼音編碼方案為特征項,基于EE的中文字符串二階相似度計算模型。其中,EE表示一階相似度與二階相似度采用編輯距離計算。(2)EE+WB:以五筆編碼方案為特征項,基于EE的中文字符串二階相似度計算模型。(3)JE+PY:以拼音編碼方案為特征項,基于JE的中文字符串二階相似度計算模型。其中,JE表示一階相似度采用Jaro-Winkler距離計算,二階相似度采用編輯距離計算。(4)JE+WB:以五筆編碼方案為特征項,基于JE的中文字符串二階相似度計算模型。4.2相似度計算模型的評價由于對相似度計算方法的優(yōu)劣評判還沒有一個較為通用的標準,因此本文采用了人工判別的方法對相似度計算的幾種模型進行評價。具體方法為:當相似度小于閾值0.6時,為不相似;0.6-0.7為基本相似;0.7-0.8為比較相似;0.8-0.9為相似;0.9-1.0為非常相似。4.3改進的相似度模型選取20組數(shù)據(jù)為樣本顯示,相似度計算結(jié)果如表1所示:將以上結(jié)果以散點圖的形式表示,橫軸表示實驗數(shù)據(jù)組序號,縱軸表示相似度,如圖3、圖4、圖5所示:對實驗結(jié)果的具體分析如下:(1)基于二階相似度模型的中文字符串比較結(jié)果明顯優(yōu)于傳統(tǒng)的一階相似度模型。從圖3中可以看出,ED計算結(jié)果值偏低,不能充分反映出字符串間的相似程度,JW則偏高,過度強調(diào)了相似性,而對差異度表示不明顯。而且ED和JW中的值相對固定,不能充分表現(xiàn)每一組字符串的具體差異,究其原因,是由于忽略了漢字成簇性的特征。(2)對音而言,從圖4對比結(jié)果中可以看出,EE+PY的效果優(yōu)于JE+PY的效果。尤其是對近音字的處理上,EE+PY所反映的相似程度效果相對較好,更加貼近人的自然判斷,這可以歸因為拼音中幾乎不存在交換字符的現(xiàn)象,所以JE的修正作用難以體現(xiàn)。(3)對形而言,從圖5可以分析得出,JE+WB的效果優(yōu)于EE+WB的效果,反映結(jié)果較為自然。即JE+WB用于形近詞的相似度計算時,優(yōu)勢較為明顯。這也與JE的換位字符修正作用有關(guān)。(4)對于上述樣本中唯一一組音、形均不相關(guān)的字符串“虛心”與“步履”,各二階相似度模型的結(jié)果值均小于0.6,為不相似。由此可以推斷出,改進后的模型更加側(cè)重于體現(xiàn)字符串之間的相似程度,對不相關(guān)字符串的反映無明顯差異。(5)根據(jù)表中數(shù)據(jù)分析,二階相似度模型中一階相似度計算方法的選擇與特征項的選擇有直接關(guān)系。綜合分析,EE+PY在音方面表現(xiàn)較好,而JE+WB在形上表現(xiàn)較好,這可以歸結(jié)為樣本空間和一階相似度模型的原因。拼音的樣本空間較小,僅有400多個,且很少存在字符位置交換的情況,JE的修正作用不容易體現(xiàn)出來,而五筆編碼的樣本空間為200