冯志伟 周建 于洋

摘 要：最小编辑距离是比较语言中不同符号串之间相似程度的一种方法，这种方法计算不同符号串之间转换时的删除、插入、替代等运算的操作数，通过动态规划算法进行算法描述。在术语研究中，可以使用最小编辑距离对术语特征进行定量化计算。在计算语言学中，可以使用最小编辑距离发现潜在的拼写错误，进行错拼更正。在语音识别中，可以使用最小编辑距离计算单词的错误率。在机器翻译中，可以使用最小编辑距离进行双语语料库的单词对齐。

关键词： 最小编辑距离;动态规划算法;术语对齐;字符串相似程度

中图分类号：H083; N04  文献标识码：A  DOI：10.12339/j.issn.1673-8578.2022.03.001

Minimum Editing Distance in Term Research //FENG Zhiwei， ZHOU Jian， YU Yang

Abstract： Minimum editing distance is a method for comparing the degree of similarity between different symbol strings in a language. This method calculates the number of operations such as deletion， insertion， substitution in transforming between different symbol strings， and can be described algorithmically by a dynamic programming algorithm. In terminology， the minimum editing distance can be used to quantify the term features. In computational linguistics， the minimum editing distance can be used to find potential spelling errors and perform misspelling corrections. In speech recognition， minimum editing distance can be used to calculate the error rate of words. In machine translation， the minimum editing distance can be used for alignment of words in bilingual corpus.

Keywords： minimum edit distance; dynamic programming algorithm; term alignment; similarity between different symbol strings

收稿日期：2022-01-29  修回日期：2022-04-11

引言

语言研究中，常常需要比较不同符号串之间的相似程度。在自然语言处理中，不同的单词也是不同的符号串，组成这些不同符号串的字母有相同的部分，也有不同的部分，可以采用最小编辑距离（minimum edit distance）来描述这符号串之间的相似程度[1-2]。在术语研究中，术语也就是符号串，因此可以使用最小编辑距离对术语之间的相似程度进行数学描述。

1 最小编辑距离的原理

最小编辑距离就是把一个符号串转换为另一个符号串时所需要的最小编辑操作的次数。

例如，在进行符号串转换时，英语的intention（意图）和execution（执行）这两个符号串之间最小需要进行5个操作，它们之间的最小编辑距离就是5。

具体说明如下：把intention和execution这两个符号串之间的最小编辑距离表示为对齐（alignment）操作。如图1，I与空符号对齐，N与E对齐，T与X对齐，E与E对齐，空符号与C对齐，N与U 对齐，T与T对齐，I与I对齐，O与O 对齐，N与N对齐。……