邵　清，葉　琨

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

?

基于編輯距離和相似度改進的漢字字符串匹配

邵清，葉琨

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

為解決中文字符串匹配精度較低的問題，提出了一種基于編輯距離和相似度改進的漢字字符串近似匹配算法，針對漢字字符串特點，使用漢字拼音和五筆編碼計算；通過改進動態(tài)規(guī)劃算法，能夠有效提高編輯距離的計算準確度以及執(zhí)行效率；再引入考慮交換問題的歸一化算法，以語義編輯距離與長句長度的比值作為歸一化結(jié)果，以此來提高近似匹配算法的準確度。實驗結(jié)果表明，改進后算法計算的相似度質(zhì)量要優(yōu)于改進前的算法結(jié)果，且對提高算法效率和查全率、查準率和時間性能等指標均有明顯改善，證明該算法的可行性和有效性。

編輯距離；相似度；歸一化；中文字符串；近似匹配

隨著信息技術(shù)的廣泛應(yīng)用，作為基礎(chǔ)性研究的字符串匹配面對越來越多的挑戰(zhàn)[1]。從20世紀70年代開始，字符串匹配問題的研究[2]就得到許多學(xué)者的關(guān)注，并且研究成果已廣泛應(yīng)用于生物、醫(yī)學(xué)、犯罪取證等領(lǐng)域。目前，計算字符串相似度的算法有多種，其中編輯距離算法作為常用的字符串相似度求解算法，具有應(yīng)用廣泛、查找有效和時間復(fù)雜度較低等優(yōu)勢。文獻[3]將整條記錄看作一個字符串，計算兩個字符串的編輯距離，從而判斷兩條記錄的相似匹配程度，但是由于字符串長短不一，可能存在冗余屬性對；文獻[4]提出了基于漢語拼音改進的編輯距離算法，把漢語拼音按照音調(diào)、聲母和韻母3方面分類，分別計算編輯距離，但在計算時使用的傳統(tǒng)動態(tài)規(guī)劃算法沒有考慮形近字會造成相似度較大的情況，所以，該算法并不具有較高的執(zhí)行效率。文獻[5～6]將字符串分解成中文字符和英文字符兩部分，計算各自的編輯距離，提高了處理效率。不足之處在于，中文的編輯需要依賴輸入法，是由多個字母按鍵組合而成，因此，假定任意兩個中文字符串的差別為同一個值并不代表中文字符串間的實際距離，在求解編輯距離時，沒有考慮可能存在的交換問題，可能導(dǎo)致錯誤結(jié)論。

針對以上文獻的不足之處，本文提出的算法，主要針對編輯距離改進和漢字字符串相似度匹配進行，首先在預(yù)處理階段對數(shù)據(jù)進行標準化處理，消除數(shù)據(jù)中的冗余屬性對；其次改進動態(tài)規(guī)劃算法，能夠有效提高編輯距離的計算準確度以及執(zhí)行效率；接著考慮可能存在的交換問題，對編輯距離進行歸一化處理。該算法綜合考慮了漢字字符串的特點，適用于漢字字符串，既能提高字符串近似匹配的精度，還能提高算法的執(zhí)行效率。

基于字符串近似匹配算法的研究已較為成熟，但已有的解決方案中，字符串的近似匹配主要針對英文字符串，這些方法在漢字字符串匹配上難以取得同樣好的效果[7]。因此需要對經(jīng)典算法進行改進，設(shè)計出能有效識別漢字字符串的算法。本文將從以下幾個角度展開研究：

(1)數(shù)據(jù)標準化。這個階段是模糊匹配過程中一個關(guān)鍵階段。由于模糊匹配的前提之一是數(shù)據(jù)源中的數(shù)據(jù)具有完全相同的模式[8]。但實際上，對于不同的數(shù)據(jù)源，由于開發(fā)人員的習(xí)慣、建立數(shù)據(jù)源的初衷等差異，使得這個前提基于不存在，因此需要在預(yù)處理階段對數(shù)據(jù)進行標準化處理[9]；(2)中文字符串識別。實體識別是找到那些指向相同實體的數(shù)據(jù)對象[10]。當把實體識別應(yīng)用到具體數(shù)據(jù)時，最關(guān)鍵的操作是實體數(shù)據(jù)對象的匹配。實體數(shù)據(jù)對象匹配是指判斷兩個數(shù)據(jù)對象是否指向同一真實世界的實體，如當兩家商店合并以后，需要合并所有百貨資料，可是有些百貨可能分別存在于原來的兩個數(shù)據(jù)源中，且它們還可能有不同的數(shù)據(jù)表現(xiàn)形式[11]。傳統(tǒng)的字符串精確匹配算法無法跟上信息和技術(shù)的迅速發(fā)展，國外學(xué)者開始對近似匹配算法展開研究，已取得了較大進展。隨著近年來網(wǎng)絡(luò)的迅速普及以及中文檢索等要求的提高[12]，我國逐步展開對中文字符串近似匹配的研究。已有的識別算法中，主要考慮英文字符串的相似性比較[13]，但是因為中文字符串的特點與英文比較有較大差異，適用于英文字符串的算法可能不適用于中文，因此尋找中文字符串合適的近似匹配算法的需求迫在眉睫。本文將致力于探究中文字符串適用的近似匹配算法；(3)編輯距離改進。計算字符串相似度的現(xiàn)有算法中，以基于編輯距離的計算方法為主。雖然編輯距離算法在數(shù)據(jù)清理、拼寫錯誤檢測方面具有一定的優(yōu)勢[14]，在刪除錯誤方面也具有較高的精度，但仍存在一些問題。本文將針對編輯距離進行改進，以提高算法準確度；(4)相似度改進。本文主要從相似度的改進這個方面來提高算法效率。因為相似度算法的效率往往會直接影響到整個模糊匹配的算法結(jié)果和效率，故相似度的計算是關(guān)鍵。

1　基于編輯距離和相似度改進的匹配算法

1.1數(shù)據(jù)預(yù)處理

該處理主要包含4個步驟：(1)使對象具有唯一性，本文算法需要將對象的唯一標識插入屬性結(jié)點表，并通過這一標識來檢索對象；(2)將屬性名統(tǒng)一，本文算法需要通過相應(yīng)屬性上的屬性結(jié)點表來定位實體對象；(3)消除冗余的屬性對。冗余的屬性對對實體的描述價值可以由其中之一替代，為了提高效率，需要消除冗余的屬性對；(4)使所有對象結(jié)點處于同一層上。

經(jīng)過以上幾步預(yù)處理，數(shù)據(jù)中的對象具備了標識唯一性和屬性統(tǒng)一性，消除了冗余屬性對，且屬性都處于同一層。

1.2中文字符串識別

根據(jù)漢字音、形的特點，本文算法將利用漢字可分解的特征，采用拼音編碼和五筆字型編碼，將漢字通過算法得到對應(yīng)的編碼，漢字字符編碼示例如表1所示。

表1　漢字字符編碼示例表

如表1所示，通過比較漢字的編碼就可以獲得單個漢字字符間的相似度，記為[15]，然后結(jié)合單個漢字字符相似度的和以及編輯距離的值得出兩個字符串的相似度。

1.3編輯距離計算

編輯距離[16]是指從源字符串S到目標字符串T的最小編輯操作次數(shù)，目的是計算S與T的相似度。主要的編輯操作包括對字符串的字符進行插入、替換等。即把字符串x與字符串y之間的互相轉(zhuǎn)換所需的最少操作次數(shù)記為編輯距離ed(x,y)。

例如：將“今天是個好天氣”轉(zhuǎn)換成“今天天氣好”，至少需4次編輯操作：刪除字符“是”；刪除字符“個”；刪除字符“好”；在字符“氣”后插入字符“好”。所以，“今天是個好天氣”轉(zhuǎn)換成“今天天氣好”的編輯距離為4，此過程如圖1所示。由圖1可知，編輯距離ed(x,y)=4。

圖1　編輯距離求解過程

求兩個字符串之間編輯距離最為普遍的方法是動態(tài)規(guī)劃算法[17]。算法中包含刪除、插入、替換3種操作。該算法從字符串的左邊第一位字符開始，依次進行比較，然后記錄已經(jīng)比較過的編輯距離的數(shù)值，最后得到下一個字符位置時的編輯距離。多數(shù)情況下，該算法可以有效計算字符串間的相似度。但是執(zhí)行效率不高，如在使用上式計算中文的某些表達方式時, 可能得出錯誤的結(jié)果。例如兩個字符串：“老師你好”和“你好老師”，利用上式計算得出，這兩個字符串的編輯距離為4，相似度為0。而實際上，這兩個字符串表達的意思相同。所以，在這種情況下，傳統(tǒng)的動態(tài)規(guī)劃算法將不再適用，需要進一步改進。

本文提出的改進算法通過考慮在刪除、插入、替換等操作中的操作代價，對傳統(tǒng)的動態(tài)規(guī)劃算法進行優(yōu)化，改進后的動態(tài)規(guī)劃算法，主要步驟如下：

(1)構(gòu)造|x|+1行，|y|+1列的矩陣D[|x|+1,|y|+1]，其中，字符串x和y的長度分別用|x|和|y|來表示；

(2)矩陣元素D[i,j]就表示ed(x1i,y1j)，即為上文提到的編輯距離。同理可知，矩陣右下角元素D[|x|+1,|y|+1]的含義就是ed(x,y)；

(3)矩陣D的值通過如下公式計算，其中所需要的最少操作次數(shù)

Di,0=Di-1,0+1

D0,j=D0,j-1+1

如果xi=yi，

Di,j=Di=1,j-1

(1)

如果xi≠yi，則

Di,j=min(Di-1,j-1+cost(x,y),Di-1,j+1,Di,j-1+1)+1

(2)

其中，cost(x,y)表示操作代價，且當xi≠yi時，cost(x,y)=0。

實驗表明，雖然改進算法在提高結(jié)果準確度的同時，也增加了時間復(fù)雜度，但是在能提高效率的前提下，增加時間復(fù)雜度的代價也是可以被接受的。

1.4相似度計算

(3)

通常情況下，編輯距離與相似度成反比。所以，不能簡單地用編輯距離來反映相似度。例如，憑感覺，兩個長度為2、編輯距離為1的字符串的相似度，要低于長度為9、編輯距離為2的相似度，實則不然。因此，為了得出準確的相似度，對編輯距離進行歸一化[20]處理是必要的。常用的歸一化方法如下

(4)

兩個中文字符串P=“上海理工大學(xué)光電學(xué)院”和Q=“光電信息”以詞語作為編輯單元計算編輯距離，有k=8,m=10,n=4。

按照式(6)的歸一化，有

計算得到結(jié)果是負數(shù)，與常理不符。這是因為該算法時空復(fù)雜度較高，而且忽略了交換問題帶來的影響，本文以語義編輯距離與長句長度的比值作為歸一化結(jié)果，更加簡單實用，得到計算字符串P與Q相似度的公式如下

(5)

式 (7) 中，在插入和刪除代價均≤1的情況下，有0≤k≤l，所以0≤similar(P,Q)≤1。由此可得出，similar(P,Q)的值越大，表示P與Q越相似。

1.5匹配算法的實現(xiàn)

以下是匹配算法的主要流程：

(1)輸入兩個字符串P、Q；

(2)判斷P、Q是否等值，若相等跳轉(zhuǎn)到步驟(4)，否則跳轉(zhuǎn)到步驟(3)；

(3)得到n=length(P)和m=length(Q)，首先判斷n與m的值，若n=0，則ed(P,Q)=m；若m=0則ed(P,Q)=n；若n=m，則跳轉(zhuǎn)到步驟(4)；否則跳轉(zhuǎn)到步驟(5)；

圖2　匹配算法流程圖

(4)令i=1，并從位置i開始逐字掃描，步長以1遞增，直至最后一個字符；得出λ(i)；

(5)使用改進的動態(tài)規(guī)劃算法計算編輯距離根據(jù)行列對應(yīng)值找出所有不匹配的字符；

(6) 計算兩個字符串的相似度。

匹配算法流程如圖2所示。

2　實驗結(jié)果與分析

在安裝有Delphi2007的Windows7測試環(huán)境下，實現(xiàn)基于編輯距離和相似度改進的漢字字符串匹配，并把實驗結(jié)果與傳統(tǒng)的動態(tài)規(guī)劃算法和傳統(tǒng)的相似度計算方法進行比較，選取不同的幾對中文詞語進行實驗，一共8組詞語，詞長范圍為2～3，包含形近字和音近字。實驗結(jié)果如表2所示。

表2　編輯距離和相似度比較表

上述實驗字符串中，既包含了同音、近音詞的情況，也有形近字和同義詞的情況。從相似度的計算結(jié)果看，改進后算法計算的相似度質(zhì)量要優(yōu)于舊算法的結(jié)果，也證明了該改進算法的可行性和有效性。

實驗結(jié)果也表明，改進后的算法，在算法效率、查全率、查準率和時間性能等指標上均有明顯改善。

圖3　各數(shù)據(jù)規(guī)模下的查準率

查準率=查出的相似的數(shù)據(jù)個數(shù)/算法檢索到的數(shù)據(jù)格式。

由圖3的實驗結(jié)果可看出，改進后的算法在數(shù)據(jù)規(guī)模一致的前提下，查準率則由72.7%提升到81.5%。

圖4　各數(shù)據(jù)規(guī)模下的查全率

查全率=查到的相似的數(shù)據(jù)個數(shù)/系統(tǒng)中實際相似的數(shù)據(jù)個數(shù)。

由圖4的實驗結(jié)果可以看出，改進后的算法在數(shù)據(jù)規(guī)模一致的前提下，查全率由65.6%提升到69.2%。

圖5　各數(shù)據(jù)規(guī)模下的平均耗時

由圖5的實驗結(jié)果可看出，改進后的算法在數(shù)據(jù)規(guī)模一致的前提下，平均耗時由351ms降低到290ms。

從實驗獲得的結(jié)果來看，可以得出結(jié)論：改進后的算法在數(shù)據(jù)規(guī)模一致的前提下，查全率、查準率和時間性能均有提高，證明了改進算法的可行性和有效性。

3　結(jié)束語

本文針對傳統(tǒng)近似匹配算法中，編輯距離計算時僅考慮英文字符串，并在計算相似度時未考慮交換的歸一化等問題，提出了一種基于改進編輯距離和相似度的漢字字符串的近似匹配算法，通過改進的編輯距離算法提高識別準確度，使近似匹配算法更有實際應(yīng)用的意義；同時在實驗中給出相似度比較的實驗結(jié)果，用3個評價指標驗證算法的準確度。實驗結(jié)果表明，與傳統(tǒng)算法相比，改進后的算法在查準率、查全率和平均耗時方面都具有明顯優(yōu)勢，提高了推薦算法的性能。

字符串近似匹配在語言識別、文件檢索、模式識別等許多領(lǐng)域應(yīng)用廣泛，但由于語言中大量同義詞、多義詞的存在，導(dǎo)致了在詞形上存在對應(yīng)關(guān)系的不同實體不等于語義上也存在對應(yīng)關(guān)系，因此，僅根據(jù)字符串模糊匹配的方法所獲得的匹配結(jié)果是不夠理想的，還應(yīng)綜合考慮這些實體的其他相關(guān)屬性，這也將是下一步的研究方向。

[1]劉顯敏,李建中.實體識別問題的相關(guān)研究[J].智能計算機與應(yīng)用,2013,3(2):1-5,10.

[2]強寶華.異構(gòu)數(shù)據(jù)庫語義集成技術(shù)研究[D]. 重慶：重慶大學(xué), 2005.

[3]LiangJin，ChenLi，MehrotraS.Efficientrecordlinkageinlargedatasets[C].Korea:Proceedingofthe8thInternationalConferenceonDatabaseSystemforAdvancedApplication,2003.

[4]俞榮華,田增平,周傲英.一種檢測多語言文本相似重復(fù)記錄的綜合方法[J].計算機科學(xué), 2002,29(1):118-121.

[5]曹犟,鄔曉鈞,夏云慶,等. 基于拼音索引的中文模糊匹配算法[J]. 清華大學(xué)學(xué)報:自然科學(xué)版,2009,49(S1):1328-1332.

[6]杜艾永,李立順,朱愿,等.基于漢字機內(nèi)編碼的中文相似重復(fù)記錄消除研究[J].電腦知識與技術(shù),2009,5(29):8314-8316.

[7]李鈍,曹元大,萬月亮.信息安全中的變形關(guān)鍵詞的識別[J].計算機工程,2007,33(21): 155-156,159.

[8]VernicaR,CareyMJ,LiC.Efficientparallelset-similarityjoinsusingmapreduce[J].ProceedingofSIGMOD,2010,3(1):218-229.

[9]Mongeae,Elkancp.Thefieldmatchingproblem:Algorithmandapplications[EB/OL]. (2008-06-16)[2015-01-11]http://www.cecs.csulb.edu/～monge/Papers/kdd96.ps.

[10]ElmagarmidAK,IpeirotisPG,VerykiosVS.Duplicaterecorddetection:asurvey[J].IEEETransactionsonKnowledgeandDataEngineering, 2007, 19(1): 1-16.

[11]周建芳,徐海銀,盧正鼎.信息集成中的實體識別解決方案[J].小型微型計算機系統(tǒng),2009, 30(9):1774-1780.

[12]車萬翔,劉挺,秦兵,等.基于改進編輯距離的中文相似句子檢索[J]. 高技術(shù)通訊,2004(7):15-19.

[13]范立新.改進的中文近似字符串匹配算法[J].計算機工程與應(yīng)用,2006,2(1):22-24.

[14]趙作鵬,尹志民,王潛平,等.一種改進的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J].計算機應(yīng)用, 2009,23(12):96-98.

[15]王靜婷.基于漢字聚類特征的中文字符串相似度計算研究[J].現(xiàn)代圖書情報技術(shù),2011(2):48-53.

[16]LevenshteinVI.Binarycodescapableofcorrectingdeletions,insertionsandreversals[J].ProblemsofInformationTransmission, 1965,1(1): 8-17.

[17]于志恒.基于筆形相似的文本校對算法及其接口原型系統(tǒng)的研究[D]. 沈陽:東北師范大學(xué),2007.

[18]刁興春,譚明超,曹建軍.一種融合多種編輯距離的字符串相似度計算方法[J].計算機應(yīng)用研究,2010,27(12):4523-4525.

[19]ChristenP,ChurchesT,HeglandM.Febrl-Aparallelopensourcedatalinkagesystem[M].Berlin:SpringerHeidelberg, 2004.

[20]張仰森.中文校對系統(tǒng)中糾錯知識庫的構(gòu)造及糾錯建議的產(chǎn)生算法[J].中文信息學(xué)報, 2001,12(1):41-44,40.

Chinese Character String Matching Algorithm Based on Improved Edit Distance and Similarity

SHAO Qing, YE Kun

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

A Chinese character string approximate matching algorithm based on the improved edit distance and similarity is proposed for better accuracy in Chinese string matching. Firstly the pinyin code is used by considering character of Chinese string, then dynamic programming algorithm is improved to effectively improve the accuracy of calculation; next, a normalization algorithm considering switching problems is introduced. With semantic edit and long distance the ratio of the length of the sentence as the result of the normalization, the accuracy and executive efficiency of approximate matching algorithm is improved. Experimental results show that the quality of the results by the improved algorithm is better than those by traditional algorithms with significant improvement in efficiency, recall, precision, time cost and other indicators.

edit distance; similarity; normalization; Chinese character string; approximate matching

2016- 12- 26

國家自然科學(xué)基金資助項目(61170277)；上海市教委科研創(chuàng)新基金資助項目(02120557)

邵清(1970-)，女，博士，副教授。研究方向：網(wǎng)絡(luò)智能等。葉琨(1993-)，女，碩士研究生。研究方向：網(wǎng)絡(luò)智能。

10.16180/j.cnki.issn1007-7820.2016.09.003

TP391.41

A

1007-7820(2016)09-007-05