編輯距離在語言分類研究中的應用

趙志靖

摘 要：編輯距離是一種距離測量法，源于將一個字符串變換為另一個字符串所需要的編輯操作數。該方法能夠自動將語言進行分類，最近這些年在西方很受關注。文章結合國外兩個語言學研究對其應用做了分析討論。針對Greenhill對于編輯距離語言分類方法的質疑，文章認為其有改進的空間，同時，應該探索其在漢藏語系語言研究中的應用。

關鍵詞：編輯距離 同言線 ASJP 語言分類

最近幾年，編輯距離被證明測量語言或方言間距離是有效的（Gooskens and Heeringa，2004；Gooskens，2007；Kurschner，Gooskens and Bezooijen，2008；Gooskens，2013）。編輯距離可應用于不同的語言學領域，如計算語言學和方言學等。Kessler（1995）第一次將編輯距離應用于測量愛爾蘭蓋爾語方言之間的距離。從那以后，有很多的研究用這種方法來測量語言或方言間的距離。Nerbonne et al.（1996）應用編輯距離測量20種荷蘭方言間距離；Heeringa（2004）則通過測量荷蘭的從東北到西南的27種方言間的距離進一步展示了編輯距離的功能；Bolognesi and Heeringa（2002）、Gooskens and Heeringa（2004）、Gooskens（2007）和Nerbonne and Siedle（2005）分別應用編輯距離測量撒丁語、挪威語、斯堪的納維亞語和德語。以上大部分研究的是歐洲語言。除此之外，編輯距離還被應用于印歐語系（Serva and Petroni，2008；Tria et al.，2010），南島語系（Petroni and Serva，2008），突厥語（van der Ark et al.，2007），印度伊朗語系（van der Ark et al.，2007），瑪雅語系、米塞-索克語系、奧托-曼格安語系、Huitotoan-Ocaina、Tacanan、Chocoan、穆斯科格語系、南亞語系（Brown et al.，2007； Holman et al.，2008；Bakker et al.，2009）。

一、編輯距離簡介

編輯距離又稱Levenshtein距離（Levenshtein Distance，簡稱LD），是由俄國科學家Vladimir Levenshtein于1965年提出的（Levenshtein，1965），是一種常用的距離函數度量方法。編輯距離算法的發明使字符串差異得以量化，多年來在自然語言處理、自動拼寫檢查乃至DNA基因序列相似性檢查方面都有建樹，近年來有語音學家利用編輯距離思想處理語言的語音相似性問題。

編輯距離的基本理念是字符串變換操作。為了測定兩個字符串的區別程度，可以通過刪除、替換和插入字符操作將一個字符串變換為另一個字符串。通常情況下，這三種操作的代價都為1，也即每種字符操作都會導致一次變換。編輯距離是源字符串s變化到目標字符串t所需最少的插入、刪除或替換編輯操作次數或最小代價。因此又有人稱之為最小編輯距離。

利用編輯距離，語言比較通過一個語言詞匯的語音跟另一個語言對應詞項詞匯的語音進行。編輯距離算法能夠計算出一個語音是如何通過插入、刪除、替換元音或輔音操作變換為另一個語音。在編輯距離算法中，上述三種編輯操作的“代價”均為1。如：

以斯瓦迪士100詞詞項“good”為例，江蘇連云港話的發音為[p? l?]，江蘇東海話的發音為[p?? n?]（目前暫未考慮聲調）。編輯距離將[p? l?]變換為[p?? n?]的操作如下：

實際上，將[p? l?]變換為[p?? n?]有許多種序列操作。最長的操作是將[p? l?]的所有元音輔音都刪除，然后再將[p?? n?]的所有元音輔音都插入，這樣一來，會給出4次刪除+5次插入=9次編輯操作的“代價”。而編輯距離算法會計算出一個語音變換為另一個語音所需要的最小編輯操作次數。我們假設這反映了語音差異的感知方式和語言演化過程中的變化現象。[p? l?]變換為[p?? n?]的最小編輯操作次數為2，即這兩個詞匯間距離為2。

假設，利用斯瓦迪士100詞進行語言距離計算，那么，當對兩個語言進行比較的時候，我們會得到100個編輯距離。兩個語言之間的距離等于100個編輯距離的和除以100。N個語言之間的所有距離會形成一個N×N的距離矩陣。一旦語言間距離計算出來了，有了距離矩陣，那么就可以對語言進行分類了。

二、愛爾蘭蓋爾語的研究

Kessler（1995）第一次將編輯距離應用于方言比較，他應用該算法對蓋爾語方言進行了比較。該文認為，方言分片可以通過對音標記的音的分析被客觀、自動地發現。分析的第一步就是方言點對間的語言距離計算，這可以通過計算語音字符串的編輯距離來得到。編輯距離得到的結果跟通過大量艱苦的勞動來決定和統計同言線的結果是非常相似的，并且比漢明距離的結果更精確。文章將該法應用于蓋爾語方言，其結果是獲得了合理的方言邊界，跟國界和省界的劃分是一致的。

傳統的繪制同言線方法存在很多不足，目前方言計量研究主要采用詞匯對應方法，其結果也不盡理想。方言計量研究的當前狀態顯示出了兩個主要問題，也是Kessler研究的方法論焦點。第一個問題涉及到距離矩陣。有沒有一種方法可以建立精確的距離矩陣，并且盡可能減少編輯決策而不丟棄相關數據？Kessler的研究認為這可以通過直接對音標記的音進行字符串距離計算的方式得到，并且其結果比詞匯比較的研究更好；第二個問題涉及到聚類技術。

Kessler的研究所采用的數據來自Wagner（1958），是Wagner通過問卷調查得到的愛爾蘭蓋爾語86個方言點的數據，數據采用國際音標的窄音記音法記錄。然后，Kessler利用了四種方法去計算語言距離矩陣，以便觀察哪種方法更好，從而回答上面提到的距離矩陣問題。為了比較四種方法的結果，首先得有個參照，Kessler是利用同言線的結果進行參照，即通過分隔方言點的同言線數量得到一個距離矩陣。四種方法分別是：

（1）詞源辨別法（etymon identity）。該法計算方言點間詞干來自相同詞源的詞匯一致的數量的平均值。例如，對于詞匯“bullock”，方言通過它們是否采用了“bull-”或“damh-”的形式來進行區分。

（2）詞匯辨別法（word identity）。如果詞匯的所有詞素是相同的，那么詞匯就被認為是相同的。例如，對于詞匯“bulla?n”，采用后綴“-a?n”和“-o?ɡ”的方言是有區別的。

（3）語音字符串比較法（phone string comparison）。該法計算語音字符串間的編輯距離。編輯距離方法中，所有的編輯操作代價均為1。例如，對于“eallaigh cattle”的[???i]和[a?i]，二者的編輯距離是2，因為需要兩次替換[a]/[?]和[??]/[?]（附加符號?被認為是字符的一部分）。

（4）特征字符串比較法（feature string comparision）。該法將每個音素用12個語音特征（nasality，stricture，laterality，articulator，glottis，place，palatalization，rounding，length，height，strength，syllabicity）表示。兩個音素之間的距離為這兩個音素的特征值之間的差異，取12個特征的平均值。這個距離再用到編輯距離的編輯代價中，替代（3）法中的編輯代價1。特征字符串比較法又分為全詞法（all-word）和同詞法（same-word），全詞法是所有詞進行兩兩比較，同詞法是同一詞義的詞進行兩兩比較。

接下來，將上述四種方法得到的距離矩陣跟同言線得到的距離矩陣比較，看哪種方法更接近同言線距離矩陣。比較結果見表1。

p表示Pearson相關系數，Kc表示Kendall和諧系數，是統計學上的概念，用于檢驗不同評估者對觀察對象評定等級的相關程度，數值越大越好。表1的結果表明，基于音標標音的語音字符串比較的方法是最好的，而且，比復雜的特征比較法要好。另外，限定全詞比較還是同詞比較，二者差別不大。

Kessler利用語音字符串比較法和自底向上的聚類方法對蓋爾語方言進行了聚類分析，認為主要蓋爾語方言的分類跟傳統的繪制同言線的結果是一致的。

實驗結果表明利用程序自動劃分方言分區是可靠的，并且只用語言調查得來的記音即可做到；精確的語言距離矩陣能通過語音字符串間的編輯距離得到。

三、德國馬普所的ASJP項目

近年來，人們越來越多地采用編輯距離算法對語言或方言進行發生學親緣關系計算（phylogenetic algorithms），并取得了令人矚目的成績。其中尤為值得關注的是德國馬克斯·普朗克進化人類學研究所（簡稱馬普所）語言學系的ASJP（Automated Similarity Judgment Program，簡稱ASJP）項目。該項目的目標是：通過一種客觀的方法，為所有語言提供一種分類；對詞匯項目的有關歷史的和區域的特性進行各種統計分析。而其價值則是：自動重建語言之間的發生學關系，對新發現和尚未分類的語言進行分類，同時還具有區分同源詞和借詞的功能。ASJP能夠獲得詞語之間的數據關系，語言間的相似距離矩陣，并最終生成可以說明語言相關關系的樹形圖。ASJP的核心是編輯距離算法。

ASJP項目負責人是Wichmann。Brown、Holman and Wichmann等（2007）描述了通過自動的詞匯比較進行語言系屬分類的方法。該方法的結果近似歷史語言學家的分類結果。該方法的核心是自動相似性判斷程序。從技術的角度來看，利用ASJP比較的語言數量是沒有限制的。文章中說：“本項目的最終目標是對能夠獲得斯瓦迪士100詞的所有的世界語言進行比較。保守估計是世界上將近6000種語言中的至少2500種語言。”（Brown et al，2007）利用ASJP對語言數據進行處理，然后利用生物學上的計算機程序生成系統發生樹。系統發生樹反映了通過ASJP判斷的語言的詞匯相似性，樹上同一分支的語言比不同分支的語言的詞匯相似性更高。把系統發生樹的分類結果同歷史語言學家的相比，ASJP計算的結果跟專家的分類結果實質上是一致的。

ASJP項目最耗時的是語言的斯瓦迪士100詞的收集工作。實際上，大部分語言的斯瓦迪士100詞從網絡或其它資源渠道可以很穩定地獲得。一旦收集好100詞，就可以利用統一標準的正字法對其進行轉換了。Brown、Holman and Wichmann等（2007）認為：“如果每種語言的100詞不利用統一的標準的正字法進行轉換的話，詞匯的自動比較工作就不可能完成。”為此，ASJP項目組開發了一種ASJP正字法，可將其視為國際音標的簡化版。該正字法的最大特點就是所有符號都可以從標準鍵盤上輸入。ASJP正字法的開發基于以下兩方面的考慮：鍵盤的局限性和傳統編程語言表示國際音標編碼的問題。

Brown、Holman and Wichmann等（2007）闡述了ASJP的具體操作步驟：

①收集語言的斯瓦迪士100詞；

②利用ASJP正字法（ASJP項目組制定了一些規則將國際音標轉換為符號。例如：[IPA：i，?，y，?]轉換成為i，[IPA：e，?]轉換成為e等等，具體原因見前面的敘述。）對100詞進行轉換；

③自動相似性判斷。利用編寫好的計算機程序實現詞匯相似性的判斷（需要注意的是，此時詞匯的國際音標發音已經在第②步中進行了轉換，轉換成符號來表示了），判斷規則是：在兩種語言中，表示同一個事物的一個字的單個音節至少有兩個符號是相同的，就可判定這兩個字在詞匯學上是相同的。這種判定區分符號順序；

④利用生物學上的種系發生樹程序SplitTrees生成語言關系樹狀圖。

上述ASJP操作步驟第三步的相似性判斷是簡單的是否判斷，即詞匯相似為1，詞匯不相似為0，屬于詞匯統計學范疇。后來，ASJP項目組對相似性判斷做了改進，利用編輯距離算法計算詞匯之間的距離。

Holman、Wichmann and Brown等（2008）的語言關系計算方法跟之前Brown、Holman and Wichmann等（2007）的方法有兩點不同。一是，詞匯之間的比較采用編輯距離算法，比較的結果為一個反映語言之間關系的距離矩陣；二是，基于距離矩陣，利用生物學上研究系統發生關系的算法和軟件，生成表示語言關系的圖形化樹枝狀結構—譜系樹。現在的ASJP能自動對語言進行分類，并且可以將這一套客觀的方法應用于非常大的語言樣本，這有利于大規模的語言數據的統計研究和可以揭示之前未知的語言發生關系。

Holman、Wichmann and Brown等（2008）說：“截至目前，我們已經收集和整理了世界上接近2000種語言的基本詞匯數據。”基于編輯距離算法，2000種語言需要比較將近兩百萬個語言對。對于一對詞，LD定義為一個詞轉換為另一個詞需要插入、刪除和替換的符號的最小次數。對于任何一個語言對L1和L2，首先對L1和L2中N個斯瓦迪士詞的每一個詞計算LD值，然后對這些LD值進行歸一化處理，即每個LD值除以理論上的最大值，得到LDN。最后，由于詞匯相似度會受到詞匯偶然相似的影響，例如音位列表的重疊或兩種語言都含有的音位結構學偏好，我們需要調整每個LDN值，調整方法是取N（N-1）/2個詞對的LDN值的平均值，得到LDND。然后N個詞對的每一個詞都得到一個LDND值。語言對L1和L2的LDND值也就是它們之間的編輯距離，定義為每個詞對的LDND值的平均值。

ASJP項目組對世界上將近2000種語言和方言做了分類，這些語言和方言的分布區域如圖1所示。ASJP產生的語言和方言的分類結果同傳統歷史比較法的結果是基本一致的。

四、批評之聲

在對語言進行分類時，歷史比較法幾乎每個步驟都是純手工比對的方法，以人為經驗和判斷為主；特征統計法和詞源統計法的第一步也具有人為性，應該說是經驗性的而非理據性的。采用歷史比較法確定語言發生學關系需要大量的詞匯數據、詳盡的音韻學知識以及會花費大量時間。基于編輯距離的語言分類方法相比較于歷史比較的方法，該法不需要花費大量時間（Brown et al.，2007），或者不像歷史比較法那樣在辨識語言對應關系時存在的主觀性（Serva and Petroni，2008），即省時省力且客觀。并且，以上的研究表明，基于編輯距離的語言分類結果與歷史比較法的分類結果非常相似，即編輯距離算法是可信的。另外，編輯距離算法能自動對語言進行分類，并且可以將這一套客觀的方法應用于非常大的語言樣本，這有利于大規模的語言數據的統計研究和可以揭示之前未知的語言發生關系（Holman et al.，2008）。也就是說，基于編輯距離的語言分類方法是計算機自動進行運算，無需人工參與，即使是無經驗的研究人員也可操作，這體現了方法的客觀性，且簡潔、速度快，還能預測未知語言關系。

但是，Greenhill對基于編輯距離的語言分類方法提出了質疑。Greenhill（2011）通過對南島語族的語言數據進行二次抽樣，選取其中的三個語言子集來測試基于編輯距離的語言分類方法的性能。結果表明，編輯距離法的分類結果與歷史比較法相比，其正確率只有40%；通過使用統一的標音法對語言進行標音后，其正確率提高到最高65%。他認為編輯距離法不能精確地辨識語言之間的關系，并且，導致該方法性能低的主要原因是編輯距離在語言學方面的幼稚性，至少體現在四個方面。首先，編輯距離模糊了同源詞和非同源詞之間的區別。通常，方言研究探索同源詞集內的變化，而兩個條目間的編輯距離一般是一兩個字符的變化。與此相反，當對語言進行分類時，計量方法合并了兩個不同的處理：同源詞集內的變化和同源詞集間的變化。兩個同源詞（例如tolu和telu）間的距離是小的（0.25），但是，計算兩個不同同源詞（例如tolu和hike）間距離會給出一個很大的不同字符串比較值。當詞匯有很大的區別時，編輯距離更有可能反映偶然相似性。

第二，編輯距離識別詞匯間的表面相似性。對于譜系分類，歷史語言學家對表面相似性持懷疑態度，因為表面相似性可能反映了詞匯借用，擬態詞，擬聲詞，童音形式，偶然性關系而不是發生學關系。

第三，像音位轉換、疊詞、詞綴的去屈折化這些處理過程包含了多重字符差異，但僅作為一個變化來處理。例如，馬來語takut（害怕）跟原始馬來——波里尼西亞語“*ma-takut”（可怕的，害怕的）是同源詞。“*ma-”是一個狀態動詞前綴，表示有去屈折化的傾向。編輯距離用兩次或三次插入/刪除操作來表示上述變化，而不是作為一個單個變化來處理。也就是說，在編輯距離之下，所有語音變化的可能性是等同的，且以同樣的速率發生。事實上，有些變化很少發生，而有些變化很頻繁且反復發生（例如，[t]到[k]被認為在南島語系獨立發生過至少20次）。

分類性能低下的最后一個原因是根據一個整體的距離度量得到分支語言的結果。直覺上，根據最小距離聚類是有道理的，但會有兩個后果。第一，距離度量忽略了來自祖語的保留形式和語言共享創新形式之間的差異。這種差異（歷史比較法中很常見）對于正確分組很重要。第二，距離度量移除了大比例的數據信息，當使用原始數據時，可以獲得較好的分類性能。采用基于距離的子群分類方法會受到詞匯保留率變化的影響。

五、下一步工作

目前只有Greenhill對基于編輯距離的語言分類提出質疑，沒有更多的人對此進行研究，說明基于編輯距離的語言分類方法還是有其可取之處的。但同時，Greenhill的實驗結論也表明編輯距離分類需要探索更好的方法及途徑。下一步我們擬改進編輯距離算法，加入更多的語言學信息，生成能反映語言學方面的距離，使得一步編輯操作采用更具有細微差別的距離，從而提高編輯距離方法的性能。同時，我們也發現，編輯距離主要被應用于研究西方語言，對漢藏語系語言研究并未涉及。漢藏語系語言不同于西方語言，有自己的特點，下一步我們將探索編輯距離應用于漢藏語系語言關系的研究。

參考文獻：

[1]Gooskens，C.，& Heeringa，W.Perceptive evaluation of Levenshtein dialect distance measurements using Norwegian dialect data[J].Language Variation and Change，2004，（3）：189-207.

[2]Gooskens，C.The contribution of linguistic factors to the intelligibility of closely related languages[J].Journal of Multilingual and Multicultural Development，2007，（6）：445-467.

[3]Kurschner，S.，& Gooskens，C.，& Bezooijen，R.Linguistic determinants of the intelligibility of Swedish words among Danes[J].International Journal of Humanities and Arts Computing，2008，（1-2）：83-100.

[4]Gooskens，C.Experimental methods for measuring intelligibility of closely related language varieties[M].Oxford：Oxford University Press，2013：195-213.

[5]Kessler，B.Computational dialectology in Irish Gaelic[A].Proceedings of the 7th Conference of European Chapter of the Association for Computational Linguistics[C].Dublin，Morgan Kaufmann，1995：60-66.

[6]Nerbonne，J.，& Heeringa，W.，& van den Hout，E.，&van; de Kooi，P.，& Otten，S.，& van de Vis，W.Phonetic distance between Dutch dialects[A].Proceedings of Computer Linguistics in the Netherlands[C].Netherlands，1996：185-202.

[7]Heeringa，W.Measuring Dialect Pronunciation Differences using Levenshtein Distance[D]. Rijksuniversiteit Groningen：PhD Thesis，2004.

[8]Bolognesi，R.，& Heeringa，W.De invloed van dominante talen op het lexicon en de fonologie van Sardische dialecten[A].In D.Bakker，T.Sanders，R.Schoonen and P. van der Wijst（eds.）[C].Gramma，2002，（1）：45-84.

[9]Nerbonne，J.，& Siedle，C.Dialektklassifikation auf der Grundlage aggregierter Ausspracheunterschiede[J].Zeitschrift fur Dialektologie und Linguistik，2005，（2）：129-147.

[10]Serva，M.，&Petroni;，F.Indo-European languages tree by Levenshtein distance[J].EPL（Europhysics Letters），2008，（6）：68005.

[11]Tria，F.，& Caglioti，E.，& Loreto，V.，& Pagnani，A.A stochastic local search approach to language tree reconstruction[J].Diachronica，2010，（2）：341-358.

[12]Petroni，F.，& Serva，M.Language distance and tree reconstruction[J].Journal of Statistical Mechanics：Theory and Experiment，2008，（8）：8012.

[13]van der Ark，R.，& Mennecier，P.，& Nerbonne J.，& Manni，F.Preliminary Identification of Language Groups and Loan Words in Central Asia[A].In Proceedings of the RANLP Workshop on Computational Phonology[C].Borovetz，2007：12-20.

[14]Brown，C.H.，& Holman，E.W.，& Wichmann，S.，&Velupillai;，V.Automated classification of the Worlds languages：A description of the method and preliminary results[J].STUF-Language Typology and Universals，2007，（61）：285-308.

[15]Holman，E.W.，& Wichmann，S.，& Brown，C.H.，& Velupillai，V.，&Muller;，A.，&Bakker;，D.Explorations in automated lexicostatistics[J].Folia Linguistica，2008，（42）：331-354.

[16]Bakker，D.，&Muller;，A.，& Velupillai，V.，&Wichmann;，S.，&Brown;，C.H.，&Brown;， P.，&Egorov;，D.，&Mailhammer;，R.，&Grant;，A.，&Holman;，E.W.Adding typology to lexicostatistics：a combined approach to language classification[J].Linguistic Typology，2009，（13）：167-179.

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

[18]Greenhill，S.Levenshtein Distances Fail to Identify Language Relationships Accurately[J].Computational Linguistics，2011，（4）：247-276.