陳正銘，霍　英（韶關(guān)學(xué)院 信息科學(xué)與工程學(xué)院，廣東 韶關(guān)512005）

編輯距離算法在中文文本相似度計(jì)算中的優(yōu)化與實(shí)現(xiàn)

陳正銘，霍英
（韶關(guān)學(xué)院 信息科學(xué)與工程學(xué)院，廣東 韶關(guān)512005）

摘要：通過分析編輯距離算法的不足，采用數(shù)據(jù)結(jié)構(gòu)的方法優(yōu)化該算法的空間和時(shí)間復(fù)雜度，采用中文分詞、同義詞和基于短句的方法優(yōu)化該算法的準(zhǔn)確率，克服了編輯距離算法在中文文本相似度計(jì)算時(shí)效率低、準(zhǔn)確率低、內(nèi)存消耗高的缺點(diǎn).通過實(shí)驗(yàn)分析，結(jié)果表明優(yōu)化后的算法取得了更高的準(zhǔn)確率和更好的時(shí)空效率.

關(guān)鍵詞：編輯距離算法；相似度計(jì)算；算法優(yōu)化；中文分詞

在文本信息處理中，基于編輯距離的文本相似度計(jì)算算法在文本分類、知識挖掘、網(wǎng)頁去重、問答系統(tǒng)等諸多領(lǐng)域有著極為廣泛的應(yīng)用，是一個(gè)基礎(chǔ)而關(guān)鍵的技術(shù).目前傳統(tǒng)編輯距離算法以字符為單位計(jì)算各個(gè)字符之間的插入、刪除、替換的編輯距離，時(shí)空效率較低，對中文文本的相似度計(jì)算準(zhǔn)確度低.故需對傳統(tǒng)的編輯距離算法進(jìn)行優(yōu)化，文獻(xiàn)［1］提出一種準(zhǔn)確性較高的計(jì)算字母型字符串相似度的算法，其利用最長公共子串對編輯距離算法進(jìn)行了改進(jìn)，修正了字符串相似度度量公式及優(yōu)化了 Levenshtein矩陣的計(jì)算過程，在不改變空間復(fù)雜度的情況下提高了準(zhǔn)確性；文獻(xiàn)［2］針對中西文混合字符串，從輸入法的角度提出了采用拼音編碼和五筆編碼，并將漢字作為西文字符的等價(jià)單位計(jì)算編輯距離的方法，該方法在提高相似重復(fù)記錄查全率的同時(shí)獲得較高的查準(zhǔn)率，但因?yàn)樗惴〝U(kuò)大了碼長，時(shí)間效率比傳統(tǒng)編輯距離算法還要低一些；文獻(xiàn)［3］則引入計(jì)算前后非相鄰字符間的交換操作來改進(jìn)編輯距離算法，實(shí)現(xiàn)了編輯操作的最小化，某種程度上也提高了算法的準(zhǔn)確度；文獻(xiàn)［4］則通過計(jì)算詞匯之間的語義距離，并對不同編輯操作賦予不同的權(quán)重來實(shí)現(xiàn)了相似句子檢測，算法復(fù)雜，時(shí)空效率較低.已知針對中文文本相似度計(jì)算的編輯距離的方法存在的較多問題是：優(yōu)化了準(zhǔn)確度卻犧牲了算法效率，優(yōu)化了字母字符準(zhǔn)確度又無法兼顧中文文本的準(zhǔn)確度.對此本文通過分析研究，提出了一種基于編輯距離改進(jìn)的和中文分詞等技術(shù)相融合的計(jì)算文本相似度的算法，該算法具有較高的準(zhǔn)確率和兼顧了時(shí)空效率.

1　傳統(tǒng)編輯距離算法

編輯距離又稱Levenshtein距離 （也叫做Edit Distance），是由俄國科學(xué)家V1adimir Levenshtein于1965年在文獻(xiàn)［5］中提出的，是一種常用的距離函數(shù)度量方法，在文本相似度檢測領(lǐng)域得到了廣泛的應(yīng)用.

表1　編輯距離算法的計(jì)算步驟

文本相似度計(jì)算［6］：編輯距離越大，相似度越小.假設(shè)源字符串S與目標(biāo)字符串T長度的最大值為Lmax，編輯距離為LD，相似度為S，則：

假設(shè)m,n分別表示源字符串S和目標(biāo)字符串T的長度，則編輯距離算法的空間復(fù)雜度為O（m*n），時(shí)間復(fù)雜度為O（m*n）.

盡管編輯距離算法簡單易于實(shí)現(xiàn)，在文本相似度檢測方面具有一定的優(yōu)勢，但仍然存在一些問題，比如算法忽略了字符串長度對編輯距離產(chǎn)生的影響，當(dāng)字符串長度過大時(shí)，所耗內(nèi)存也較大；單純以字為單位計(jì)算各個(gè)字符之間的編輯距離，計(jì)算出來的距離只是文字表面的距離，并沒有充分考慮詞語的概念，使得計(jì)算結(jié)果的準(zhǔn)確率不高，特別是對中文的相似度計(jì)算得不到滿意的結(jié)果.

2　編輯距離算法的優(yōu)化

2.1空間效率優(yōu)化

傳統(tǒng)編輯距離算法使用二維數(shù)組存儲計(jì)算過程的各階段編輯距離值，但實(shí)際上在每一次循環(huán)中只有一行的數(shù)據(jù)參與了計(jì)算，計(jì)算過的數(shù)據(jù)行往后都不再參與計(jì)算，因此可對算法進(jìn)行調(diào)整，將二維數(shù)組改為兩個(gè)一維數(shù)組（見表2）.經(jīng)驗(yàn)證，計(jì)算速度和結(jié)果與傳統(tǒng)編輯距離算法幾乎相同，但空間復(fù)雜度降為：O（min（m,n））.

表2　優(yōu)化空間后的編輯距離算法的計(jì)算步驟

2.2時(shí)間效率優(yōu)化

傳統(tǒng)編輯距離算法時(shí)間復(fù)雜度為O（m*n），考慮其動態(tài)規(guī)劃思路無法通過改造算法結(jié)構(gòu)實(shí)現(xiàn)時(shí)間復(fù)雜度的降維，但可通過減少m與n的值，實(shí)現(xiàn)一定的優(yōu)化.仔細(xì)分析傳統(tǒng)編輯距離算法計(jì)算過程，發(fā)現(xiàn)兩個(gè)字符串對應(yīng)位置上的字符相同時(shí)，如果把這兩個(gè)相對應(yīng)的相同的字符刪除后，編輯距離計(jì)算結(jié)果不變.但刪除相對應(yīng)位置相同的字符后將會減少參與計(jì)算的兩字符串的長度，從而使得計(jì)算的時(shí)間減少，同時(shí)也減少了計(jì)算所占用的空間.經(jīng)驗(yàn)證，計(jì)算時(shí)間比傳統(tǒng)編輯距離算法減少，時(shí)間復(fù)雜度降為O（m'*n'）（m'＜=m，n'＜=n）.

表3　優(yōu)化時(shí)間后的編輯距離算法的計(jì)算步驟

2.3準(zhǔn)確度優(yōu)化

以下準(zhǔn)確度的優(yōu)化研究為僅以中文文本為研究模型的研究內(nèi)容.

2.3.1基于中文分詞的編輯距離算法

傳統(tǒng)編輯距離算法以字為單位計(jì)算字符串之間的編輯距離，計(jì)算出相似度結(jié)果可能與實(shí)際情況出入較大，而且字符串的長度對計(jì)算時(shí)間也有很大的影響，針對這些情況，考慮先對字符串進(jìn)行中文分詞（本研究采用的是開源的盤古中文分詞模塊［7］），然后再進(jìn)行計(jì)算，從而使計(jì)算結(jié)果更符合字符串詞語相似度計(jì)算的要求，計(jì)算速度和相似度的準(zhǔn)確率都得以提高（見表4）.

表4　基于中文分詞的編輯距離計(jì)算例子

2.3.2基于同義詞處理的編輯距離算法

上述基于分詞的編輯距離算法雖然以詞為單位計(jì)算字符串之間的編輯距離，計(jì)算速度與結(jié)果已經(jīng)比傳統(tǒng)編輯距離算法精確不少，但還是與實(shí)際情況有一定出入，尤其如上例所示，“愛”與“喜歡”這兩詞為同義詞，實(shí)際一個(gè)意思，針對這些情況，考慮進(jìn)行編輯距離計(jì)算過程時(shí)，步驟“如果詞條s［i］=t ［j］，則編輯代價(jià)cost為0；如果詞條s［i］!=t［j］，則編輯代價(jià)cost為1；”利用同義詞庫變更為：“如果詞條s［i］同義于 t［j］，則編輯代價(jià)cost為0；如果詞條s［i］非同義于 t［j］，則編輯代價(jià)cost為1；”，從而使計(jì)算結(jié)果更符合字符串詞語相似度計(jì)算的要求（見表5）.

表5　基于同義詞處理的編輯距離計(jì)算例子

另同義詞詞典的構(gòu)造可利用分詞系統(tǒng)的詞典進(jìn)行擴(kuò)展，其數(shù)據(jù)結(jié)構(gòu)為：（編號，拼音，詞條，同義詞編號列表），并按編號與拼音項(xiàng)進(jìn)行索引及散列.判斷兩詞條是否同義，可根據(jù)第一詞條的值先檢索其相關(guān)記錄，然后根據(jù)同義詞編號列表檢測第二詞條是否在第一詞條的同義詞集合內(nèi)，如果在則返回同義標(biāo)志，否則返回非同義標(biāo)志.

2.3.3基于短句的編輯距離算法

為進(jìn)一步提高相似度計(jì)算的準(zhǔn)確度，可引入基于短句的編輯距離相似度算法，思路如下：先把文本按標(biāo)點(diǎn)劃分為若干短句，然后按短句為基本單位使用上述基于同義詞處理的編輯距離算法進(jìn)行計(jì)算，當(dāng)兩短句相似度為某閾值（如0.9）以上時(shí)則返回相似標(biāo)志，否則返回非相似標(biāo)志.為提高計(jì)算速度，可先對兩短句的長度進(jìn)行比較，如果長度相差超過一倍則直接返回非相似標(biāo)志.

表6　基于短句的編輯距離算法的計(jì)算步驟

3　結(jié)語

上述對編輯距離算法的優(yōu)化都未能從數(shù)量級上降低其運(yùn)算的時(shí)間復(fù)雜度，但通過數(shù)據(jù)結(jié)構(gòu)的方法，空間復(fù)雜度從O（m*n）降為了O（min（m,n）），時(shí)間復(fù)雜度也從O（m*n）降為了為O（m'*n'）（m'＜= m，n'＜=n），另外通過中文分詞、同義詞檢測與基于短句為基本計(jì)算單位的方法，極大的提高了中文文本相似度檢測的準(zhǔn)確度，也進(jìn)一步的降低了算法的時(shí)間復(fù)雜度.

參考文獻(xiàn)：

［1］姜華，韓安琪，王美佳，等.基于改進(jìn)編輯距離的字符串相似度求解算法［J］.計(jì)算機(jī)工程，2014，40（1）：222-227.

［2］刁興春，譚明超，曹建軍.一種融合多種編輯距離的字符串相似度計(jì)算方法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4523-4525.

［3］趙作鵬，尹志民，王潛平，等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2009，29（2）:424-426.

［4］車萬翔，劉挺，秦兵，等.基于改進(jìn)編輯距離的中文相似句子檢索［J］.高技術(shù)通訊，2004，14（7）:15-20.

［5］Levenshtein V I.Binary Code CaPab1e of Correcting de1etions，insertions and reversa1s［J］.Dok1ady Akademii NaukSSSR，1966，163 （4）:708-710.

［6］廖宏建，楊玉寶，唐連章.改進(jìn)的編輯距離計(jì)算及其在自動評分中的應(yīng)用［J］.廣州大學(xué)學(xué)報(bào)，2012，11（4）：79-83.

［7］開源中國社區(qū).盤古分詞首頁文檔和下載［EB/OL］.［2015-03-02］.httP://www.oschina.net/P/Pangu.

（責(zé)任編輯：歐愷）

中圖分類號：TP391.1

文獻(xiàn)標(biāo)識碼：A

文章編號：1OO7-5348（2O15）12-OOO8-O5

［收稿日期］2015-09-04

［基金項(xiàng)目］韶關(guān)市科技計(jì)劃項(xiàng)目（2013CX/K38）；韶關(guān)學(xué)院科研項(xiàng)目（一般項(xiàng)目2014-14）；廣東省自然科學(xué)基金資助項(xiàng)目（2014A030307029）；廣東省高等學(xué)?？萍紕?chuàng)新（重點(diǎn)）項(xiàng)目（2013KJCX0168）.

［作者簡介］陳正銘（1978-），男，江西南康人，韶關(guān)學(xué)院信息科學(xué)與工程學(xué)院講師，碩士；研究方向：數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)庫信息系統(tǒng).

0Ptimization and ImPlementation of the Edit Distance Algorithm in Chinese Similarity Calculation

CHEN Zheng-ming，HUO Ying
（Institute of Information Science and Engineering，Shaoguan University，Shaoguan 512005，Guangdong，China）

Abstract:By ana1yzing the 1ess of edit distance a1gorithm，using the method of data structure oPtimize sPace and time comP1exity of the a1gorithm，using the method of Chinese word，synonyms and Phrases oPtimize the accuracy of the a1gorithm，overcomes the shortcomings of a1gorithm efficiency 1ow，accurate 1ow and memory consumPtion high.By way of examP1e test and ana1ysis，the resu1ts show that the oPtimized a1gorithm is achieve a higher accuracy and better temPora1 efficiency.

Key words:edit distance a1gorithm；simi1arity ca1cu1ation；a1gorithm oPtimization；Chinese segmentation