编辑距离在语言分类研究中的应用

赵志靖

摘 要：编辑距离是一种距离测量法，源于将一个字符串变换为另一个字符串所需要的编辑操作数。该方法能够自动将语言进行分类，最近这些年在西方很受关注。文章结合国外两个语言学研究对其应用做了分析讨论。针对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.