邵 清,葉 琨
(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)
?
基于編輯距離和相似度改進(jìn)的漢字字符串匹配
邵清,葉琨
(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)
為解決中文字符串匹配精度較低的問(wèn)題,提出了一種基于編輯距離和相似度改進(jìn)的漢字字符串近似匹配算法,針對(duì)漢字字符串特點(diǎn),使用漢字拼音和五筆編碼計(jì)算;通過(guò)改進(jìn)動(dòng)態(tài)規(guī)劃算法,能夠有效提高編輯距離的計(jì)算準(zhǔn)確度以及執(zhí)行效率;再引入考慮交換問(wèn)題的歸一化算法,以語(yǔ)義編輯距離與長(zhǎng)句長(zhǎng)度的比值作為歸一化結(jié)果,以此來(lái)提高近似匹配算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后算法計(jì)算的相似度質(zhì)量要優(yōu)于改進(jìn)前的算法結(jié)果,且對(duì)提高算法效率和查全率、查準(zhǔn)率和時(shí)間性能等指標(biāo)均有明顯改善,證明該算法的可行性和有效性。
編輯距離;相似度;歸一化;中文字符串;近似匹配
隨著信息技術(shù)的廣泛應(yīng)用,作為基礎(chǔ)性研究的字符串匹配面對(duì)越來(lái)越多的挑戰(zhàn)[1]。從20世紀(jì)70年代開(kāi)始,字符串匹配問(wèn)題的研究[2]就得到許多學(xué)者的關(guān)注,并且研究成果已廣泛應(yīng)用于生物、醫(yī)學(xué)、犯罪取證等領(lǐng)域。目前,計(jì)算字符串相似度的算法有多種,其中編輯距離算法作為常用的字符串相似度求解算法,具有應(yīng)用廣泛、查找有效和時(shí)間復(fù)雜度較低等優(yōu)勢(shì)。文獻(xiàn)[3]將整條記錄看作一個(gè)字符串,計(jì)算兩個(gè)字符串的編輯距離,從而判斷兩條記錄的相似匹配程度,但是由于字符串長(zhǎng)短不一,可能存在冗余屬性對(duì);文獻(xiàn)[4]提出了基于漢語(yǔ)拼音改進(jìn)的編輯距離算法,把漢語(yǔ)拼音按照音調(diào)、聲母和韻母3方面分類(lèi),分別計(jì)算編輯距離,但在計(jì)算時(shí)使用的傳統(tǒng)動(dòng)態(tài)規(guī)劃算法沒(méi)有考慮形近字會(huì)造成相似度較大的情況,所以,該算法并不具有較高的執(zhí)行效率。文獻(xiàn)[5~6]將字符串分解成中文字符和英文字符兩部分,計(jì)算各自的編輯距離,提高了處理效率。不足之處在于,中文的編輯需要依賴輸入法,是由多個(gè)字母按鍵組合而成,因此,假定任意兩個(gè)中文字符串的差別為同一個(gè)值并不代表中文字符串間的實(shí)際距離,在求解編輯距離時(shí),沒(méi)有考慮可能存在的交換問(wèn)題,可能導(dǎo)致錯(cuò)誤結(jié)論。
針對(duì)以上文獻(xiàn)的不足之處,本文提出的算法,主要針對(duì)編輯距離改進(jìn)和漢字字符串相似度匹配進(jìn)行,首先在預(yù)處理階段對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理,消除數(shù)據(jù)中的冗余屬性對(duì);其次改進(jìn)動(dòng)態(tài)規(guī)劃算法,能夠有效提高編輯距離的計(jì)算準(zhǔn)確度以及執(zhí)行效率;接著考慮可能存在的交換問(wèn)題,對(duì)編輯距離進(jìn)行歸一化處理。該算法綜合考慮了漢字字符串的特點(diǎn),適用于漢字字符串,既能提高字符串近似匹配的精度,還能提高算法的執(zhí)行效率。
基于字符串近似匹配算法的研究已較為成熟,但已有的解決方案中,字符串的近似匹配主要針對(duì)英文字符串,這些方法在漢字字符串匹配上難以取得同樣好的效果[7]。因此需要對(duì)經(jīng)典算法進(jìn)行改進(jìn),設(shè)計(jì)出能有效識(shí)別漢字字符串的算法。本文將從以下幾個(gè)角度展開(kāi)研究:
(1)數(shù)據(jù)標(biāo)準(zhǔn)化。這個(gè)階段是模糊匹配過(guò)程中一個(gè)關(guān)鍵階段。由于模糊匹配的前提之一是數(shù)據(jù)源中的數(shù)據(jù)具有完全相同的模式[8]。但實(shí)際上,對(duì)于不同的數(shù)據(jù)源,由于開(kāi)發(fā)人員的習(xí)慣、建立數(shù)據(jù)源的初衷等差異,使得這個(gè)前提基于不存在,因此需要在預(yù)處理階段對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理[9];(2)中文字符串識(shí)別。實(shí)體識(shí)別是找到那些指向相同實(shí)體的數(shù)據(jù)對(duì)象[10]。當(dāng)把實(shí)體識(shí)別應(yīng)用到具體數(shù)據(jù)時(shí),最關(guān)鍵的操作是實(shí)體數(shù)據(jù)對(duì)象的匹配。實(shí)體數(shù)據(jù)對(duì)象匹配是指判斷兩個(gè)數(shù)據(jù)對(duì)象是否指向同一真實(shí)世界的實(shí)體,如當(dāng)兩家商店合并以后,需要合并所有百貨資料,可是有些百貨可能分別存在于原來(lái)的兩個(gè)數(shù)據(jù)源中,且它們還可能有不同的數(shù)據(jù)表現(xiàn)形式[11]。傳統(tǒng)的字符串精確匹配算法無(wú)法跟上信息和技術(shù)的迅速發(fā)展,國(guó)外學(xué)者開(kāi)始對(duì)近似匹配算法展開(kāi)研究,已取得了較大進(jìn)展。隨著近年來(lái)網(wǎng)絡(luò)的迅速普及以及中文檢索等要求的提高[12],我國(guó)逐步展開(kāi)對(duì)中文字符串近似匹配的研究。已有的識(shí)別算法中,主要考慮英文字符串的相似性比較[13],但是因?yàn)橹形淖址奶攸c(diǎn)與英文比較有較大差異,適用于英文字符串的算法可能不適用于中文,因此尋找中文字符串合適的近似匹配算法的需求迫在眉睫。本文將致力于探究中文字符串適用的近似匹配算法;(3)編輯距離改進(jìn)。計(jì)算字符串相似度的現(xiàn)有算法中,以基于編輯距離的計(jì)算方法為主。雖然編輯距離算法在數(shù)據(jù)清理、拼寫(xiě)錯(cuò)誤檢測(cè)方面具有一定的優(yōu)勢(shì)[14],在刪除錯(cuò)誤方面也具有較高的精度,但仍存在一些問(wèn)題。本文將針對(duì)編輯距離進(jìn)行改進(jìn),以提高算法準(zhǔn)確度;(4)相似度改進(jìn)。本文主要從相似度的改進(jìn)這個(gè)方面來(lái)提高算法效率。因?yàn)橄嗨贫人惴ǖ男释鶗?huì)直接影響到整個(gè)模糊匹配的算法結(jié)果和效率,故相似度的計(jì)算是關(guān)鍵。
1.1數(shù)據(jù)預(yù)處理
該處理主要包含4個(gè)步驟:(1)使對(duì)象具有唯一性,本文算法需要將對(duì)象的唯一標(biāo)識(shí)插入屬性結(jié)點(diǎn)表,并通過(guò)這一標(biāo)識(shí)來(lái)檢索對(duì)象;(2)將屬性名統(tǒng)一,本文算法需要通過(guò)相應(yīng)屬性上的屬性結(jié)點(diǎn)表來(lái)定位實(shí)體對(duì)象;(3)消除冗余的屬性對(duì)。冗余的屬性對(duì)對(duì)實(shí)體的描述價(jià)值可以由其中之一替代,為了提高效率,需要消除冗余的屬性對(duì);(4)使所有對(duì)象結(jié)點(diǎn)處于同一層上。
經(jīng)過(guò)以上幾步預(yù)處理,數(shù)據(jù)中的對(duì)象具備了標(biāo)識(shí)唯一性和屬性統(tǒng)一性,消除了冗余屬性對(duì),且屬性都處于同一層。
1.2中文字符串識(shí)別
根據(jù)漢字音、形的特點(diǎn),本文算法將利用漢字可分解的特征,采用拼音編碼和五筆字型編碼,將漢字通過(guò)算法得到對(duì)應(yīng)的編碼,漢字字符編碼示例如表1所示。
表1 漢字字符編碼示例表
如表1所示,通過(guò)比較漢字的編碼就可以獲得單個(gè)漢字字符間的相似度,記為[15],然后結(jié)合單個(gè)漢字字符相似度的和以及編輯距離的值得出兩個(gè)字符串的相似度。
1.3編輯距離計(jì)算
編輯距離[16]是指從源字符串S到目標(biāo)字符串T的最小編輯操作次數(shù),目的是計(jì)算S與T的相似度。主要的編輯操作包括對(duì)字符串的字符進(jìn)行插入、替換等。即把字符串x與字符串y之間的互相轉(zhuǎn)換所需的最少操作次數(shù)記為編輯距離ed(x,y)。
例如:將“今天是個(gè)好天氣”轉(zhuǎn)換成“今天天氣好”,至少需4次編輯操作:刪除字符“是”;刪除字符“個(gè)”;刪除字符“好”;在字符“氣”后插入字符“好”。所以,“今天是個(gè)好天氣”轉(zhuǎn)換成“今天天氣好”的編輯距離為4,此過(guò)程如圖1所示。由圖1可知,編輯距離ed(x,y)=4。
圖1 編輯距離求解過(guò)程
求兩個(gè)字符串之間編輯距離最為普遍的方法是動(dòng)態(tài)規(guī)劃算法[17]。算法中包含刪除、插入、替換3種操作。該算法從字符串的左邊第一位字符開(kāi)始,依次進(jìn)行比較,然后記錄已經(jīng)比較過(guò)的編輯距離的數(shù)值,最后得到下一個(gè)字符位置時(shí)的編輯距離。多數(shù)情況下,該算法可以有效計(jì)算字符串間的相似度。但是執(zhí)行效率不高,如在使用上式計(jì)算中文的某些表達(dá)方式時(shí), 可能得出錯(cuò)誤的結(jié)果。例如兩個(gè)字符串:“老師你好”和“你好老師”,利用上式計(jì)算得出,這兩個(gè)字符串的編輯距離為4,相似度為0。而實(shí)際上,這兩個(gè)字符串表達(dá)的意思相同。所以,在這種情況下,傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法將不再適用,需要進(jìn)一步改進(jìn)。
本文提出的改進(jìn)算法通過(guò)考慮在刪除、插入、替換等操作中的操作代價(jià),對(duì)傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法進(jìn)行優(yōu)化,改進(jìn)后的動(dòng)態(tài)規(guī)劃算法,主要步驟如下:
(1)構(gòu)造|x|+1行,|y|+1列的矩陣D[|x|+1,|y|+1],其中,字符串x和y的長(zhǎng)度分別用|x|和|y|來(lái)表示;
(2)矩陣元素D[i,j]就表示ed(x1i,y1j),即為上文提到的編輯距離。同理可知,矩陣右下角元素D[|x|+1,|y|+1]的含義就是ed(x,y);
(3)矩陣D的值通過(guò)如下公式計(jì)算,其中所需要的最少操作次數(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)表示操作代價(jià),且當(dāng)xi≠yi時(shí),cost(x,y)=0。
實(shí)驗(yàn)表明,雖然改進(jìn)算法在提高結(jié)果準(zhǔn)確度的同時(shí),也增加了時(shí)間復(fù)雜度,但是在能提高效率的前提下,增加時(shí)間復(fù)雜度的代價(jià)也是可以被接受的。
1.4相似度計(jì)算
(3)
通常情況下,編輯距離與相似度成反比。所以,不能簡(jiǎn)單地用編輯距離來(lái)反映相似度。例如,憑感覺(jué),兩個(gè)長(zhǎng)度為2、編輯距離為1的字符串的相似度,要低于長(zhǎng)度為9、編輯距離為2的相似度,實(shí)則不然。因此,為了得出準(zhǔn)確的相似度,對(duì)編輯距離進(jìn)行歸一化[20]處理是必要的。常用的歸一化方法如下
(4)
兩個(gè)中文字符串P=“上海理工大學(xué)光電學(xué)院”和Q=“光電信息”以詞語(yǔ)作為編輯單元計(jì)算編輯距離,有k=8,m=10,n=4。
按照式(6)的歸一化,有
計(jì)算得到結(jié)果是負(fù)數(shù),與常理不符。這是因?yàn)樵撍惴〞r(shí)空復(fù)雜度較高,而且忽略了交換問(wèn)題帶來(lái)的影響,本文以語(yǔ)義編輯距離與長(zhǎng)句長(zhǎng)度的比值作為歸一化結(jié)果,更加簡(jiǎn)單實(shí)用,得到計(jì)算字符串P與Q相似度的公式如下
(5)
式 (7) 中,在插入和刪除代價(jià)均≤1的情況下,有0≤k≤l,所以0≤similar(P,Q)≤1。由此可得出,similar(P,Q)的值越大,表示P與Q越相似。
1.5匹配算法的實(shí)現(xiàn)
以下是匹配算法的主要流程:
(1)輸入兩個(gè)字符串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開(kāi)始逐字掃描,步長(zhǎng)以1遞增,直至最后一個(gè)字符;得出λ(i);
(5)使用改進(jìn)的動(dòng)態(tài)規(guī)劃算法計(jì)算編輯距離根據(jù)行列對(duì)應(yīng)值找出所有不匹配的字符;
(6) 計(jì)算兩個(gè)字符串的相似度。
匹配算法流程如圖2所示。
在安裝有Delphi2007的Windows7測(cè)試環(huán)境下,實(shí)現(xiàn)基于編輯距離和相似度改進(jìn)的漢字字符串匹配,并把實(shí)驗(yàn)結(jié)果與傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法和傳統(tǒng)的相似度計(jì)算方法進(jìn)行比較,選取不同的幾對(duì)中文詞語(yǔ)進(jìn)行實(shí)驗(yàn),一共8組詞語(yǔ),詞長(zhǎng)范圍為2~3,包含形近字和音近字。實(shí)驗(yàn)結(jié)果如表2所示。
表2 編輯距離和相似度比較表
上述實(shí)驗(yàn)字符串中,既包含了同音、近音詞的情況,也有形近字和同義詞的情況。從相似度的計(jì)算結(jié)果看,改進(jìn)后算法計(jì)算的相似度質(zhì)量要優(yōu)于舊算法的結(jié)果,也證明了該改進(jìn)算法的可行性和有效性。
實(shí)驗(yàn)結(jié)果也表明,改進(jìn)后的算法,在算法效率、查全率、查準(zhǔn)率和時(shí)間性能等指標(biāo)上均有明顯改善。
圖3 各數(shù)據(jù)規(guī)模下的查準(zhǔn)率
查準(zhǔn)率=查出的相似的數(shù)據(jù)個(gè)數(shù)/算法檢索到的數(shù)據(jù)格式。
由圖3的實(shí)驗(yàn)結(jié)果可看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查準(zhǔn)率則由72.7%提升到81.5%。
圖4 各數(shù)據(jù)規(guī)模下的查全率
查全率=查到的相似的數(shù)據(jù)個(gè)數(shù)/系統(tǒng)中實(shí)際相似的數(shù)據(jù)個(gè)數(shù)。
由圖4的實(shí)驗(yàn)結(jié)果可以看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查全率由65.6%提升到69.2%。
圖5 各數(shù)據(jù)規(guī)模下的平均耗時(shí)
由圖5的實(shí)驗(yàn)結(jié)果可看出,改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,平均耗時(shí)由351ms降低到290ms。
從實(shí)驗(yàn)獲得的結(jié)果來(lái)看,可以得出結(jié)論:改進(jìn)后的算法在數(shù)據(jù)規(guī)模一致的前提下,查全率、查準(zhǔn)率和時(shí)間性能均有提高,證明了改進(jìn)算法的可行性和有效性。
本文針對(duì)傳統(tǒng)近似匹配算法中,編輯距離計(jì)算時(shí)僅考慮英文字符串,并在計(jì)算相似度時(shí)未考慮交換的歸一化等問(wèn)題,提出了一種基于改進(jìn)編輯距離和相似度的漢字字符串的近似匹配算法,通過(guò)改進(jìn)的編輯距離算法提高識(shí)別準(zhǔn)確度,使近似匹配算法更有實(shí)際應(yīng)用的意義;同時(shí)在實(shí)驗(yàn)中給出相似度比較的實(shí)驗(yàn)結(jié)果,用3個(gè)評(píng)價(jià)指標(biāo)驗(yàn)證算法的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)算法相比,改進(jìn)后的算法在查準(zhǔn)率、查全率和平均耗時(shí)方面都具有明顯優(yōu)勢(shì),提高了推薦算法的性能。
字符串近似匹配在語(yǔ)言識(shí)別、文件檢索、模式識(shí)別等許多領(lǐng)域應(yīng)用廣泛,但由于語(yǔ)言中大量同義詞、多義詞的存在,導(dǎo)致了在詞形上存在對(duì)應(yīng)關(guān)系的不同實(shí)體不等于語(yǔ)義上也存在對(duì)應(yīng)關(guān)系,因此,僅根據(jù)字符串模糊匹配的方法所獲得的匹配結(jié)果是不夠理想的,還應(yīng)綜合考慮這些實(shí)體的其他相關(guān)屬性,這也將是下一步的研究方向。
[1]劉顯敏,李建中.實(shí)體識(shí)別問(wèn)題的相關(guān)研究[J].智能計(jì)算機(jī)與應(yīng)用,2013,3(2):1-5,10.
[2]強(qiáng)寶華.異構(gòu)數(shù)據(jù)庫(kù)語(yǔ)義集成技術(shù)研究[D]. 重慶:重慶大學(xué), 2005.
[3]LiangJin,ChenLi,MehrotraS.Efficientrecordlinkageinlargedatasets[C].Korea:Proceedingofthe8thInternationalConferenceonDatabaseSystemforAdvancedApplication,2003.
[4]俞榮華,田增平,周傲英.一種檢測(cè)多語(yǔ)言文本相似重復(fù)記錄的綜合方法[J].計(jì)算機(jī)科學(xué), 2002,29(1):118-121.
[5]曹犟,鄔曉鈞,夏云慶,等. 基于拼音索引的中文模糊匹配算法[J]. 清華大學(xué)學(xué)報(bào):自然科學(xué)版,2009,49(S1):1328-1332.
[6]杜艾永,李立順,朱愿,等.基于漢字機(jī)內(nèi)編碼的中文相似重復(fù)記錄消除研究[J].電腦知識(shí)與技術(shù),2009,5(29):8314-8316.
[7]李鈍,曹元大,萬(wàn)月亮.信息安全中的變形關(guān)鍵詞的識(shí)別[J].計(jì)算機(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]周建芳,徐海銀,盧正鼎.信息集成中的實(shí)體識(shí)別解決方案[J].小型微型計(jì)算機(jī)系統(tǒng),2009, 30(9):1774-1780.
[12]車(chē)萬(wàn)翔,劉挺,秦兵,等.基于改進(jìn)編輯距離的中文相似句子檢索[J]. 高技術(shù)通訊,2004(7):15-19.
[13]范立新.改進(jìn)的中文近似字符串匹配算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,2(1):22-24.
[14]趙作鵬,尹志民,王潛平,等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用, 2009,23(12):96-98.
[15]王靜婷.基于漢字聚類(lèi)特征的中文字符串相似度計(jì)算研究[J].現(xiàn)代圖書(shū)情報(bào)技術(shù),2011(2):48-53.
[16]LevenshteinVI.Binarycodescapableofcorrectingdeletions,insertionsandreversals[J].ProblemsofInformationTransmission, 1965,1(1): 8-17.
[17]于志恒.基于筆形相似的文本校對(duì)算法及其接口原型系統(tǒng)的研究[D]. 沈陽(yáng):東北師范大學(xué),2007.
[18]刁興春,譚明超,曹建軍.一種融合多種編輯距離的字符串相似度計(jì)算方法[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4523-4525.
[19]ChristenP,ChurchesT,HeglandM.Febrl-Aparallelopensourcedatalinkagesystem[M].Berlin:SpringerHeidelberg, 2004.
[20]張仰森.中文校對(duì)系統(tǒng)中糾錯(cuò)知識(shí)庫(kù)的構(gòu)造及糾錯(cuò)建議的產(chǎn)生算法[J].中文信息學(xué)報(bào), 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
國(guó)家自然科學(xué)基金資助項(xiàng)目(61170277);上海市教委科研創(chuàng)新基金資助項(xià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