編輯距離算法在中文文本相似度計算中的優化與實現

陳正銘，霍　英（韶關學院 信息科學與工程學院，廣東 韶關512005）

編輯距離算法在中文文本相似度計算中的優化與實現

陳正銘，霍英
（韶關學院 信息科學與工程學院，廣東 韶關512005）

摘要：通過分析編輯距離算法的不足，采用數據結構的方法優化該算法的空間和時間復雜度，采用中文分詞、同義詞和基于短句的方法優化該算法的準確率，克服了編輯距離算法在中文文本相似度計算時效率低、準確率低、內存消耗高的缺點.通過實驗分析，結果表明優化后的算法取得了更高的準確率和更好的時空效率.

關鍵詞：編輯距離算法；相似度計算；算法優化；中文分詞

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

1　傳統編輯距離算法

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

表1　編輯距離算法的計算步驟

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

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

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

2　編輯距離算法的優化

2.1空間效率優化

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

表2　優化空間后的編輯距離算法的計算步驟

2.2時間效率優化

傳統編輯距離算法時間復雜度為O（m*n），考慮其動態規劃思路無法通過改造算法結構實現時間復雜度的降維，但可通過減少m與n的值，實現一定的優化.仔細分析傳統編輯距離算法計算過程，發現兩個字符串對應位置上的字符相同時，如果把這兩個相對應的相同的字符刪除后，編輯距離計算結果不變.但刪除相對應位置相同的字符后將會減少參與計算的兩字符串的長度，從而使得計算的時間減少，同時也減少了計算所占用的空間.經驗證，計算時間比傳統編輯距離算法減少，時間復雜度降為O（m'*n'）（m'＜=m，n'＜=n）.

表3　優化時間后的編輯距離算法的計算步驟

2.3準確度優化

以下準確度的優化研究為僅以中文文本為研究模型的研究內容.

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

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

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

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

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

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

另同義詞詞典的構造可利用分詞系統的詞典進行擴展，其數據結構為：（編號，拼音，詞條，同義詞編號列表），并按編號與拼音項進行索引及散列.判斷兩詞條是否同義，可根據第一詞條的值先檢索其相關記錄，然后根據同義詞編號列表檢測第二詞條是否在第一詞條的同義詞集合內，如果在則返回同義標志，否則返回非同義標志.

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

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

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

3　結語

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

參考文獻：

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

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

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

［4］車萬翔，劉挺，秦兵，等.基于改進編輯距離的中文相似句子檢索［J］.高技術通訊，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］.廣州大學學報，2012，11（4）：79-83.

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

（責任編輯：歐愷）

中圖分類號：TP391.1

文獻標識碼：A

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

［收稿日期］2015-09-04

［基金項目］韶關市科技計劃項目（2013CX/K38）；韶關學院科研項目（一般項目2014-14）；廣東省自然科學基金資助項目（2014A030307029）；廣東省高等學校科技創新（重點）項目（2013KJCX0168）.

［作者簡介］陳正銘（1978-），男，江西南康人，韶關學院信息科學與工程學院講師，碩士；研究方向：數據結構算法與數據庫信息系統.

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