基于編輯距離的無序詞表的對齊和定位

趙志靖

摘要：語言調(diào)查采集到的數(shù)據(jù)存在相當程度的差異，需要進行二次加工。本文基于編輯距離算法實現(xiàn)從語言和方言詞匯大數(shù)據(jù)中的詞匯相似匹配及數(shù)據(jù)的對齊和定位。通過對達讓語數(shù)據(jù)進行的三次實驗發(fā)現(xiàn)，在做距離計算時，以詞算而不是以詞加括號內(nèi)注釋的整體去算的方式在保證抽取詞匯召回率的基礎(chǔ)上準確率會顯著提升。實驗結(jié)果表明，基于編輯距離的數(shù)據(jù)抽取方法是可行的，具有較好的檢索效果。

關(guān)鍵詞：編輯距離；相似度

中圖分類號：TP391 文獻標識碼：A

Abstract： The data of languages collected from field research have considerable differences，they need for secondary process.This paper implements the match and extraction of vocabulary similarity from the big data of language and dialect vocabulary based on levenshtein distance algorithm.Through the three experiments made by using the data of Darang， the research finds that the way of counting words rather than words and comments in brackets as a whole increases the precision rate dramatically on the basis of ensuring extraction vocabulary recall rate when the levenshtein distances are computed. The experimental results show that it is feasible to extract data based on levenshtein distance， the aboved method has better retrieval effect.

Keywords： Levenshtein Distance；similarity

引言

中國語言研究中，經(jīng)歷了60余年大規(guī)模數(shù)據(jù)的采集，形成約數(shù)千種語言和方言詞匯大數(shù)據(jù)。不過這些數(shù)據(jù)因調(diào)查理念、調(diào)查目的、調(diào)查方式、調(diào)查領(lǐng)域、調(diào)查詞表等不同而存在不同程度的差異，需要進行二次加工處理，這批寶貴資源對語言工程和語言文化建設(shè)具有重要價值。本文目標提出對采集的語言數(shù)據(jù)二次加工，建設(shè)統(tǒng)一格式詞表，便于后續(xù)的語言科學研究。也就是說語言調(diào)查采集到的數(shù)據(jù)是無序的，且數(shù)量不等，本文擬建設(shè)統(tǒng)一格式詞表，該詞表包括1 329個詞匯，并且這些詞匯是按照順序排列的，然后又從數(shù)千種語言詞匯大數(shù)據(jù)中，每種語言都抽取意義相同1 329個詞匯，如果沒有找到，則以空表示，這就涉及到數(shù)據(jù)的定位，由于這1 329個詞匯是按照順序排列的，所以還涉及到數(shù)據(jù)的對齊，最后將每種語言按順序排好的1 329個詞匯保存為獨立的Excel文件，供語言分析研究使用。本文的難點在于如何從數(shù)千種語言詞匯數(shù)據(jù)中盡可能準確地找到這1 329個詞匯。

1 中國語言和方言數(shù)據(jù)現(xiàn)狀

半個多世紀以來，我國開展過數(shù)次規(guī)模不等的語言和方言調(diào)查。1956年，根據(jù)國務院指示開展了漢語和民族語言普查，共普查了1 849個縣市的漢語方言，并組成7個民族調(diào)查隊，調(diào)查了主要民族地區(qū)的語言。這次語言普查，對于推廣普通話和漢語規(guī)范化，對于少數(shù)民族文字的改革與創(chuàng)制，對于民族身份的認定等都起了重要作用。1999年，教育部、國家語委等11部（委）聯(lián)合開展了中國語言文字使用情況調(diào)查，調(diào)查采用入戶問卷的調(diào)查方式，涉及全國1 063個縣（市、區(qū)），直接被調(diào)查對象47萬多人。這次調(diào)查獲得了我國語言文字使用的一些基本數(shù)據(jù)，為當今的語言決策提供了重要支撐。除了這2次大的語言調(diào)查之外，我國學者還持續(xù)進行了漢語方言、民族語言、海外華語的調(diào)查研究，取得了許多重要成果。

在推廣普通話的同時，社會的語言資源保護意識逐漸加強，方言文化保護受到社會各界的關(guān)注。國家語委積極推進中國語言資源有聲數(shù)據(jù)庫建設(shè)，江蘇庫數(shù)據(jù)調(diào)查工作完成并通過國家驗收，成為全國首個建成并開通的省級語言資源庫，上海、北京、遼寧、廣西等省區(qū)市有聲數(shù)據(jù)庫建設(shè)工作取得成效，山東、河北、福建等省有聲數(shù)據(jù)庫建設(shè)工作啟動?！爸腥A經(jīng)典資源庫”啟動了首期建設(shè)工作[1]。

但是語言生活異常豐富復雜且與時而變，半個多世紀以來所進行的各種語言調(diào)查，或因調(diào)查理念、調(diào)查目的、調(diào)查方式（包括調(diào)查技術(shù)）、調(diào)查領(lǐng)域等限制，采集到的數(shù)據(jù)存在相當程度的差異，需要進行大規(guī)模統(tǒng)籌建設(shè)。用現(xiàn)代信息技術(shù)大規(guī)模處理中國語言數(shù)據(jù)，建成中國語言資源數(shù)據(jù)庫，對我國語言生活規(guī)劃和語言科學研究將產(chǎn)生極其重要的影響。

2 基于編輯距離的數(shù)據(jù)對齊和定位技術(shù)

2.1 編輯距離

編輯距離算法是俄羅斯的Vladimir Levenshtein在1965年最先提出來的[2]。Levenshtein提出的編輯距離算法允許使用插入、刪除和替換3種編輯操作方式，用這3種編輯操作方式計算得到的編輯距離叫Levenshtein Distance。[3]

編輯距離用于衡量2個序列的相似度，即兩者之間有多近似或有多大區(qū)別。在自然語言處理中被衡量的序列就是單詞或字符串。2個單詞之間的編輯距離越小，其相似度就越高。如果設(shè)2個字符串分別為源字符串s和目標字符串t，從字符串s到t的編輯距離是指：只使用刪除、插入或替換3種操作，需要最少多少步可以將s變成t，即“將源字符串s變換為目標字符串t所需要的最少的刪除、插入或替換操作的次數(shù)”[4]。舉例如下。

1）如果s=“computer”，t=“computer”，那么編輯距離D（s，t）=0，因為s與t完全相同，不需要變換。

2）如果s=“sport”，t=“sort”，那么編輯距離D（s，t）=1，因為將s變換為t只需一次編輯操作（刪除字母“p”）。

3）如果s=“sensible”，t=“sensitive”，其編輯距離D（s，t）=3，因為將s變成t至少需要三步（第一步插入“t”，第二步把“b”替換成“i”，第三步把“l(fā)”替換成“v”）。

編輯距離D（s，t）的計算方法如下所述。假設(shè)Dij=D（s1…si，t1…tj），0≤i≤m，0≤j≤n，m和n分別表示源字符串s和目標字符串t的長度，Dij表示從s1…si到t1…tj的編輯距離，那么（m+1）×（n+1）階矩陣Dij可通過公式（1）計算得到。

公式（1）包含刪除、插入和替換三種操作。該算法是從兩個字符串的左邊開始比較，記錄已經(jīng)比較過的編輯距離，然后進一步得到下一個字符位置時的編輯距離。矩陣Dij能夠通過從D00逐行逐列計算獲取，最終Dmn表示D（s，t）的值，即源字符串s和目標字符串t的編輯距離。

編輯距離算法最初用于拼寫檢查，計算將錯誤的拼寫形式轉(zhuǎn)換成正確的拼寫形式最少需要多少次操作[5]。現(xiàn)在，編輯距離算法不僅用于拼寫檢查，還在如剽竊檢測、重名或近似名查詢、重復內(nèi)容檢查、生物學上的DNA分析、計算機輔助翻譯需要的相似譯文文本查找、數(shù)據(jù)清洗等領(lǐng)域中得到了很好的應用[6-7]。

2.2 統(tǒng)一格式詞表數(shù)據(jù)對齊和定位的實現(xiàn)過程

統(tǒng)一格式詞表是指從數(shù)千種語言詞匯大數(shù)據(jù)中，每種語言都抽取意義相同的詞匯（本文是1 329個詞匯），然后將所有語言的1329詞匯按統(tǒng)一順序和格式排列，供語言分析研究使用。統(tǒng)一格式詞表數(shù)據(jù)和語言詞匯數(shù)據(jù)保存在Excel中。數(shù)據(jù)的對齊和定位算法流程如圖1所示。

首先，從1329詞匯表F1中取詞W1，然后從語言詞匯大數(shù)據(jù)F2中依次取詞W2，計算W1與W2之間的編輯距離。實際操作中，所謂的W1和W2可能還需要做細化處理，因為1329詞匯數(shù)據(jù)和語言詞匯數(shù)據(jù)保存在Excel中，數(shù)據(jù)是以類似一條記錄的形式保存的，不是以單個詞的形式保存的。比如，1329詞匯表Excel文件中“雹子，冰雹”這條記錄，在程序處理過程中，會將“雹子”和“冰雹”分別取出去做編輯距離計算，而不是以“雹子，冰雹”整體去做編輯距離計算。語言詞匯數(shù)據(jù)Excel文件中的記錄也是這樣處理的。如此經(jīng)過編輯距離計算之后，研究擇取其中的最小值進入下一步的處理中。將1329詞匯表中的每個詞匯，采用編輯距離算法，和語言詞匯表的所有數(shù)據(jù)進行相似匹配，并計算編輯距離，將距離最小的和等于最小距離的值作為匹配結(jié)果保存到matchWords數(shù)組中。如果matchWords的長度為1，則說明只有一條匹配結(jié)果，然后將該結(jié)果輸出保存；如果matchWords的長度為大于1，則說明匹配到相似數(shù)據(jù)較多，需要進一步處理。

由于應用中詞匯的長度相差較大時，詞匯長度對最終的計算結(jié)果影響較大，因此，有必要對編輯距離值進行歸一化操作。本文基于取比較詞匯的最大長度做歸一化。也就是說，matchLen和最小距離值minMatchLen都是歸一化后的值。

本文的算法中，將最小距離minMatchLen閾值設(shè)置為0.6，因為經(jīng)過對輸出結(jié)果的勘察，我們發(fā)現(xiàn)，最小距離值超過0.6的匹配結(jié)果，其正確率基本為0。也就是說，具體只對小于0.6的結(jié)果做進一步處理，超過0.6就認為沒找到，自動輸出“Not found！”。超過0.6的檢索結(jié)果舉例如表1所示。實驗舉例用詞匯來自達讓語，見本文第四部分，下同，不再贅述。

2.3 詞匯的自動抽取及后加工

如前所述，matchWords的長度為1，自動抽取并輸出匹配結(jié)果；如果matchWords的長度大于1，詞匯比較距離超過0.6的自動輸出“Not found！”，詞匯比較距離小于0.6的則需要進行后加工，即人工判斷，后期篩選。即雖然抽取詞匯的過程是自動的，但是篩選出盡可能正確的詞匯仍需要人工判斷。在此，以“洞，窟窿”、“巖石”舉例做如下說明，具體如表2、表3所示。

表2和表3中加粗斜體的為篩選結(jié)果。由表可知，表2可篩選出正確的匹配詞；表3篩選不出匹配詞，程序自動輸出“Not found！”。同時表2說明，最小距離值為0并不一定只有一個候選詞，仍需進一步篩選。

本文用輸入對話框的動態(tài)列表菜單來顯示候選詞匯，如果候選詞匯數(shù)目比較大會影響美觀，所以本文選用下拉列表框，其高度固定，寬度根據(jù)內(nèi)容自動擴展，點擊列表框右邊的倒立小三角可顯示帶滾動條的下拉列表，內(nèi)容可多可少。如果有多個候選詞，就會按匹配到的先后順序進行排列并顯示給用戶。程序運行過程中，列表選擇輸入對話框是自動彈出的，用戶只需在正確詞上面單擊鼠標右鍵，然后點下“OK”按鈕即可；如果候選詞列表中沒有找到正確的匹配詞，則點下“Cancel”按鈕，程序自動輸出“Not found！”。這就完成了詞匯篩選的過程。圖2和圖3是詞匯篩選界面功能實例圖。

圖2是程序在檢索“洞，窟窿”時，由于有多個匹配結(jié)果，所以程序運行過程中跳出對話框進行篩選；圖3顯示，“窟窿（衣服上的窟窿）”應該是正確的匹配結(jié)果，而不是其他項。鼠標選擇正確項之后按“OK”按鈕，由此正確的匹配結(jié)果就得到了保存。

3 實驗設(shè)計與數(shù)據(jù)分析

3.1 實驗語料

本文所用實驗語料是田野調(diào)查采集的達讓語數(shù)據(jù)，共有數(shù)據(jù)記錄2660條，其片段截取如圖4所示。

3.2 實驗過程

本文第三部分的程序?qū)崿F(xiàn)說明都是基于該實驗語料。

為了使得距離值能夠切實反映詞匯之間的差異，程序在處理過程中會忽略語言數(shù)據(jù)中括號內(nèi)的內(nèi)容。也就是說，在做距離計算時，以詞算而不是以詞加括號內(nèi)注釋的整體去算。這一點通過實驗結(jié)果可以得到印證。

利用提供的達讓語數(shù)據(jù)，研究展開了三次實驗。

第一次實驗：做距離計算時，語言數(shù)據(jù)是以詞加括號內(nèi)注釋的整體去算的，且后期未做篩選加工處理。未召回的詞數(shù)目為174，檢索成功的詞數(shù)目為664。

第二次實驗：做距離計算時，語言數(shù)據(jù)中括號內(nèi)注釋部分被刪除了，且后期未做篩選加工處理。未召回的詞數(shù)目為39，檢索成功的詞數(shù)目為990。

第三次實驗：做距離計算時，語言數(shù)據(jù)中括號內(nèi)注釋部分被刪除了，且后期做了篩選加工處理。未召回的詞數(shù)目為152，檢索成功的詞數(shù)目為1092。

實驗結(jié)果用準確率P（Precision）、召回率R（Recall）來表示。3次實驗結(jié)果如表4所示。

3.3 實驗數(shù)據(jù)分析

從實驗一結(jié)果來看，語言數(shù)據(jù)如果是以詞加括號內(nèi)注釋的整體去算，會增加詞匯的長度，從而無形中加大了編輯距離的值，使得召回率和準確率降低，且均將低于其他2個實驗，尤其是準確率大大降低；從實驗二結(jié)果來看，由于將語言數(shù)據(jù)中括號內(nèi)注釋部分刪除了，召回率和準確率都提高了，尤其是準確率有了明顯提升；實驗三在實驗二的基礎(chǔ)上做了后期篩選加工處理，由于加入了篩選操作，召回率略微下降，但比實驗一的召回率仍然偏高，最重要的卻是，實驗三的準確率有了改觀與增益。這符合數(shù)據(jù)處理的正常思維。從實驗結(jié)果的整體上來看，統(tǒng)一格式詞表的數(shù)據(jù)提取用編輯距離算法可以得到研發(fā)，但抽取需要將語言數(shù)據(jù)中括號內(nèi)注釋部分刪除，使得要比較的詞匯的長度差小一些，且抽取結(jié)果也需要后期篩選處理。

4 結(jié)束語

編輯距離是計算和量化分析詞匯相似度的一種重要依據(jù)。根據(jù)編輯距離可實現(xiàn)從數(shù)千種語言詞匯大數(shù)據(jù)中檢索/抽取詞匯。但是同時也看到，本文只研究了抽取過程的自動化，由于后加工階段需要進行篩選加工處理，會增加時間復雜度，在計算時間上，編輯距離算法還需進一步優(yōu)化，或者將編輯距離算法和其他算法結(jié)合起來推進實施優(yōu)化處理。

參考文獻：

[1]李宇明.論中國語言資源有聲數(shù)據(jù)庫的建設(shè)[J].中國語文，2010，（4）：356-363.

[2]LEVENSHTEIN V I. Binary codes capable of correcting deletions， insertions and reversals[J].Doklady Akademii Nauk SSSR，1965，163（4）：845-848.

[3]MANNING C D，RAGHAVAN P，SCHUTZE H. Introduction to information retrieval[M].Cambridge： Cambridge University Press，2008：58-60.

[4]馬立東.編輯距離算法及其在英語易混詞自動抽取中的應用[J].智能計算機與應用，2013，3（1）：47-51.

[5]Allison L. Dynamic Programming Algorithm（DPA） for Edit-Distance[EB/OL].[2015-07-10].http：//www.allisons.org/ll/AlgDS/Dynamic/Edit/.

[6]米成剛，楊雅婷，周喜，等.基于字符串相似度的維吾爾語中漢語借詞識別[J].中文信息學報，2013，27（5）：173-178，190.

[7]瑪依熱·依布拉音，米吉提·阿不里米提，艾斯卡爾·艾木都拉.基于最小編輯距離的維語詞語檢錯與糾錯研究[J].中文信息學報，2008，22（3）：110-114.