馮志偉 周建 于洋

摘 要：最小編輯距離是比較語言中不同符號串之間相似程度的一種方法，這種方法計算不同符號串之間轉(zhuǎn)換時的刪除、插入、替代等運算的操作數(shù)，通過動態(tài)規(guī)劃算法進行算法描述。在術(shù)語研究中，可以使用最小編輯距離對術(shù)語特征進行定量化計算。在計算語言學(xué)中，可以使用最小編輯距離發(fā)現(xiàn)潛在的拼寫錯誤，進行錯拼更正。在語音識別中，可以使用最小編輯距離計算單詞的錯誤率。在機器翻譯中，可以使用最小編輯距離進行雙語語料庫的單詞對齊。

關(guān)鍵詞： 最小編輯距離;動態(tài)規(guī)劃算法;術(shù)語對齊;字符串相似程度

中圖分類號：H083; N04? 文獻標(biāo)識碼：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]。在術(shù)語研究中，術(shù)語也就是符號串，因此可以使用最小編輯距離對術(shù)語之間的相似程度進行數(shù)學(xué)描述。

1 最小編輯距離的原理

最小編輯距離就是把一個符號串轉(zhuǎn)換為另一個符號串時所需要的最小編輯操作的次數(shù)。

例如，在進行符號串轉(zhuǎn)換時，英語的intention（意圖）和execution（執(zhí)行）這兩個符號串之間最小需要進行5個操作，它們之間的最小編輯距離就是5。

具體說明如下：把intention和execution這兩個符號串之間的最小編輯距離表示為對齊（alignment）操作。如圖1，I與空符號對齊，N與E對齊，T與X對齊，E與E對齊，空符號與C對齊，N與U 對齊，T與T對齊，I與I對齊，O與O 對齊，N與N對齊。在對齊的符號串下方的標(biāo)記，說明從上面的符號串轉(zhuǎn)換為下面的符號串要做的操作，符號的一個序列就表示一個操作表（operation list）。最下面一行給出了從上面的符號串到下面的符號串轉(zhuǎn)換時的操作表：d表示刪除（delete），s表示替代（substitute），i表示插入（insert）。I與空符號對齊時要把I刪除，所以用d表示;N與E對齊時要用E來替代N，所以用s表示;T與X對齊時要用X來替代T，所以也用s表示;E與E對齊時，不進行任何操作;空符號與C對齊時要插入C，所以用i表示;N與U 對齊時要用U來替代N，所以用s表示;T與T對齊，I與I對齊，O與O 對齊，N與N對齊，都不進行任何操作。這樣便得到intention和execution對齊時的操作表dssis，也就是“刪除-替代-替代-插入-替代”。

也可以把intention和execution的對齊過程看作是從intention到execution轉(zhuǎn)換過程，即：

第1步：刪除 intention中的第一個字母i，得到ntention;

第2步：用e替代ntention中的第一個字母n，得到etention;

第3步：用x替代etention中的第二個字母t，得到exention;

第4步： 在exention中的第四個字母n和第五個字母t之間插入字母u，得到exenution;

第5步：用c替代exenution中的第四個字母n，得到execution。

轉(zhuǎn)換過程如圖2所示。從而得到從intention轉(zhuǎn)換為execution時的操作表也是dssis。

可以賦給每個操作一個代價值（cost）或權(quán)值（weight）。1966年，Levenshtein（列文斯坦）建議，在上面的刪除、替代和插入3種方法中，每一個操作的代價值都為1，而用同一個字母來替代它自己時代價值為0（例如，用字母T來替代字母T的代價值為0）[3]。兩個序列之間的列文斯坦距離（Levenshtein distance）是最簡單的加權(quán)因子，這個加權(quán)因子也就是最小編輯距離。所以，根據(jù)intention和execution對齊時的操作表dssis，這兩個單詞之間的列文斯坦距離為1+1+1+1+1=5，這意味著，這兩個單詞之間的最小編輯距離為5。

此外，Levenshtein還提出了另一種不同的度量方法。這種方法規(guī)定，插入或脫落操作的代價值為1，不容許替代操作[3]。不過，Levenshtein認(rèn)為，也可以把替代操作表示為一個脫落操作加上一個插入操作，這樣，替代操作的代價值應(yīng)該為2，這實際上也就等于容許了替代操作。使用這樣的度量方法，根據(jù)intention和execution對齊時的操作表dssis，這兩個單詞之間的列文斯坦距離應(yīng)該是1+2+2+1+2=8，根據(jù)這樣的度量方法，這兩個單詞之間的最小編輯距離為8?？梢哉J(rèn)為，Levenshtein取替代操作的代價值為2是合理的，因為一個替換操作，實際上相當(dāng)于“先刪除”和“后插入”兩個操作。因此這樣的度量方法是合理的，所以在本文中采用這樣的方法進行度量。

2 最小編輯距離的動態(tài)規(guī)劃算法

在自然語言的計算機自動處理中，最小編輯距離可以通過動態(tài)規(guī)劃算法（dynamic programming algorithm）來進行算法描述[3]。

用序列比較的動態(tài)規(guī)劃算法工作時，要建立一個編輯距離矩陣（edit distance matrix），目標(biāo)序列的每一個符號按照自左而右的順序記錄于矩陣的行中，源序列的每一個符號按照自下而上的順序記錄在矩陣的列中，也就是說，目標(biāo)序列的字母沿著底線自左而右排列，源序列的字母沿著側(cè)線自下而上排列。對于最小編輯距離來說，這個矩陣就是編輯距離矩陣。每一個編輯距離單元[i， j]表示目標(biāo)序列第i個字符和源序列的第j個字符之間的距離。每個單元可以作為周圍單元的簡單函數(shù)來計算。

計算每個單元的值的時候，取到達該單元時插入（ins）、替代（sub）、刪除（del）3個可能路徑中的最小路徑為其值，計算公式如下：

distance[i-1， j] + ins-cost（target i-1）

distance[i，j] = mindistance[i-1， j-1] + sub-cost（source j-1， target i-1） distance[i， j-1] + del-cost（source j-1））

圖3中的偽代碼（pseudo code）對此最小編輯距離算法做了歸納。

圖3中，各種代價值可以是固定的（例如x， ins-cost（x）=1），也可以針對個別字母做特別說明（例如，說明某些字母比另外一些字母更容易被替代）。假定相同的字母進行替代時，其代價值為0。

圖4是應(yīng)用最小編輯距離算法計算intention和execution之間距離的結(jié)果，計算時采用了Levenshtein提出的第二種度量方法：插入和刪除的代價值分別取1，替代的代價值取2，當(dāng)相同的字母進行替代時，其代價值為0。每一個單元都存在插入、脫落和替代3種可能性，最小編輯距離算法以這3種可能路徑中的最小路徑為其值。采用這樣的計算方法，從矩陣的開始點出發(fā)，每一個單元都在插入、脫落和替代3種可能性之間進行選擇，因此能夠把矩陣中所有的單元都填滿。如圖4所示。

（計算時采用了Levenshtein距離;斜體字符表示從空符號串開始的距離的初始值，矩陣中的所有的單元都填滿了。）

采用最小編輯距離算法，在圖4中，首先要刪除intention中的i，從第1列第0行開始計算。

圖4中的一種可行的計算步驟如下：

——首先刪除i，在第1列第0行，得1分，積累為1分;

——用e替換n，在第1列第2行，得2分，積累為1+2=3分;

——用x替換t，在第2列第3行，得2分，積累為3+2=5分;

——e不變，在第3列第4行，不得分，積累為5分;

——用c替換n，在第4列第5行，得2分，積累為5+2=7分;

——在c后插入u，在第5列第5行，得1分，積累為7+1=8分;

——t與t完全相同，在第6列第6行，不得分，積累為8+0=8分;

——i與i完全相同，在第7列第7行，不得分，積累為8+0=8分;

——o與o完全相同，在第8列第8行，不得分，積累為8+0=8分;

——n與n完全相同，在第9列第9行，不得分，積累為8+0=8分;

因此總積累為8分。

為了擴充最小編輯距離算法，使它能夠進行對齊（alignment），可以把對齊看作是通過編輯距離矩陣的一條路徑（path）。圖5中使用帶陰影的小方框來顯示這條路徑。路徑中的每一個小方框表示兩個符號串中的一對字母對齊的情況。如果兩個這樣帶陰影的小方框連續(xù)地出現(xiàn)在同一個行中，那么，從源符號串到目標(biāo)符號串就會有一個插入操作;如果兩個這樣帶陰影的小方框連續(xù)地出現(xiàn)在同一個列中，那么，從源符號串到目標(biāo)符號串就會有一個刪除操作。

圖5從直覺上說明了如何計算這種對齊路徑。計算過程分為兩步，分述如下：

（1） 第一步中，在每一個方框中存儲一些指針來提升最小編輯距離算法的功能。方框中指針要說明當(dāng)前的方框是從前面的哪一個（或哪些個）方框來的方向。圖中分別標(biāo)示出了這些指針的情況。在某些方框中出現(xiàn)若干個指針，這是因為在這些方框中最小的擴充可能來自前面的若干個不同的方框。指針“←”表示“插入”操作，指針“↓”表示“刪除”操作，指針“”表示“替換”操作。

（2） 第二步中，進行追蹤（back-trace）。追蹤時從最后一個方框（處于最后一行與最后一列的方框）開始，沿著指針箭頭所指的方向往后追蹤，穿過這個動態(tài)規(guī)劃矩陣。在最后的方框與初始的方框之間的每一個完整路徑，就是一個最小編輯距離的對齊。

圖5中，在每一個方框中輸入一個值，并用箭頭標(biāo)出該方框中的值是來自與之相鄰的3個方框中的哪一個方框，一個方框最多可以有3個箭頭（“←”“↓”“”）。當(dāng)這個表填滿之后，使用追蹤的方法來計算對齊結(jié)果（也就是最小編輯路徑）。計算時，從右上角代價值為8的方框開始，順著箭頭所指的方向進行追蹤。圖5中灰黑色的方框序列表示在兩個符號串之間可能的最小代價對齊的結(jié)果。根據(jù)灰黑色方框序列中的結(jié)果，計算最小編輯距離的值。首先要刪除intention中的i，從第1列第0行開始計算，計算步驟如下：

——首先刪除i，在第1列第0行，得1分，積累為1分;

——用e替換n，在第1列第2行，得2分，積累為1+2=3分;

——用x替換t，在第2列第3行，得2分，積累為3+2=5分;

——e不變，在第3列第4行，不得分，積累為5分;

——在e后插入c，在第4列第4行，得1分，積累為5+1=6分;

——用u替換n，在第5列第5行，得2分，積累為6+2=8分;

——t與t完全相同，在第6列第6行，不得分，積累為8+0=8分;

——i與i完全相同，在第7列第7行，不得分，積累為8+0=8分;

——o與o完全相同，在第8列第8行，不得分，積累為8+0=8分;

——n與n完全相同，在第9列第9行，不得分，積累為8+0=8分;

總積累仍然為8分。

因此，intention和execution之間的最小編輯距離為8。

3 最小編輯距離與術(shù)語研究

上文描述的最小編輯距離方法對于術(shù)語研究是有啟發(fā)的。中文術(shù)語是用漢字來表示的，漢字也是一種符號，而術(shù)語就是由漢字構(gòu)成的符號串，因此，可以使用最小編輯距離從數(shù)學(xué)上來衡量中文術(shù)語之間的接近程度，對中文術(shù)語進行定量化的描述。

例如，在計算機術(shù)語中，有“磁盤存儲器（magnetic disc storage）、磁盤機（magnetic disc unit）、磁盤驅(qū)動器（magnetic disc drive）、磁頭（magnetic head）、磁頭加載區(qū)（magnetic head loading zone）”等中文術(shù)語，人們從感性層面覺得“磁盤機、磁盤驅(qū)動器、磁頭、磁頭加載區(qū)”與“磁盤存儲器”的接近程度是不同的，“磁盤機、磁盤驅(qū)動器”與“磁盤存儲器”比較接近，而“磁頭、磁頭加載區(qū)”與“磁盤存儲器”相距較遠。但是，這樣的感覺終究是主觀的，很可能因人而異。如果采用最小編輯距離，就可以對人們的主觀感受進行定量化計算，使之得到精確的描述，從而避免認(rèn)識的主觀性。

上述術(shù)語的最小編輯距離分別計算如下：

磁盤存儲器

磁盤機 * *

s d d

最小編輯距離 = 2+1+1 = 4

磁盤存儲器

磁盤驅(qū)動器

s s

最小編輯距離 = 2+2 =4

磁盤存儲器

磁頭 * * *

s d d d

最小編輯距離 = 2+1+1+1 = 5

磁盤存儲器

磁頭加載區(qū)

s s s s

最小編輯距離 = 2+2+2+2 = 8

“磁盤機、磁盤驅(qū)動器”與“磁盤驅(qū)動器”的最小編輯距離為4，而“磁頭、磁頭加載區(qū)”與“磁盤存儲器”的最小編輯距離分別為5和8。最小編輯距離的計算結(jié)果與人們的主觀感覺是吻合的。這樣，主觀感受就獲得了定量化的數(shù)學(xué)描述。

由此可見，如果使用最小編輯距離來計算不同術(shù)語之間的接近程度，能夠使人們對不同術(shù)語之間的接近程度的主觀感受獲得定量的認(rèn)識。這是計算術(shù)語學(xué)（computational terminology）研究中一個值得關(guān)注的有趣問題[1]。

4 結(jié)語

最小編輯距離是比較不同符號串之間相似程度的數(shù)學(xué)方法，這種方法可以采用動態(tài)規(guī)劃算法來進行算法描述。在術(shù)語學(xué)中，最小編輯距離可以用來對術(shù)語進行定量化的計算。在計算語言學(xué)中，最小編輯距離可以用來發(fā)現(xiàn)潛在的拼寫錯誤，進行拼錯更正。如果對于最小編輯距離做一些輕微改動，還可以用來做兩個符號串之間的最小代價對齊。在語音識別中，可以使用最小編輯距離對齊來計算單詞的錯誤率。在機器翻譯中，因為雙語并行語料庫中的句子需要彼此匹配，使用最小編輯距離進行單詞對齊也是非常有用的一種方法[4]。

參考文獻

[1] 馮志偉.自然語言處理簡明教程[M]. 上海：上海外語教育出版社，2020：75.

[2] WAGNNER R A， FISCHER M J. The string-to-string correction problem[J]. Journal of the Association for Computing Machinery， 1974， 21（1）： 168-173.

[3] LEVENSHTEIN V I. Binary codes capable of correcting detections， insertions， and reversals[J]. Soviet Physics Doklady， 1966， 10（8）：707-710.

[4] JURAFSKY D， MARTIN J H. Speech and Language Processing： An Introduction in Natural Language Processing， Computational Linguistics， and Speech Recognition[M]. 2nd ed. New York： Person Education Inc.， 2009：107-111.

作者簡介：馮志偉（1939—），男，博士生導(dǎo)師，中國中文信息學(xué)會會士，中國人工智能學(xué)會理事，杭州師范大學(xué)外國語學(xué)院特聘教授，教育部語言文字應(yīng)用研究所研究員。主要研究方向為計算語言學(xué)、計量語言學(xué)、理論語言學(xué)、語料庫語言學(xué)、術(shù)語學(xué)等。出版中外文專著38部，發(fā)表中外文論文500多篇，主持編制國際標(biāo)準(zhǔn)1項和國家規(guī)范3項，參與編制國家標(biāo)準(zhǔn)14項，曾獲中國計算機學(xué)會NLPCC杰出貢獻獎、奧地利維斯特獎、香港圣弗蘭西斯科技人文獎。通信方式：zwfengde2010@163.com。

周建（1979—），男，碩士，杭州師范大學(xué)外國語學(xué)院講師。主要研究方向為專門用途英語教育（ESP）、語料庫語言學(xué)和翻譯技術(shù)等。通信方式：james@hznu.edu.cn。

于洋（1988—），男，博士，大連海事大學(xué)外國語學(xué)院講師。主要研究方向為計量語言學(xué)、語料庫語言學(xué)和詞源學(xué)等。通信方式：yuyang89@dlmu.edu.cn。