馮志偉 周建 于洋

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

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

中圖分類號(hào)：H083; N04? 文獻(xiàn)標(biāo)識(shí)碼：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

引言

語言研究中，常常需要比較不同符號(hào)串之間的相似程度。在自然語言處理中，不同的單詞也是不同的符號(hào)串，組成這些不同符號(hào)串的字母有相同的部分，也有不同的部分，可以采用最小編輯距離（minimum edit distance）來描述這符號(hào)串之間的相似程度[1-2]。在術(shù)語研究中，術(shù)語也就是符號(hào)串，因此可以使用最小編輯距離對(duì)術(shù)語之間的相似程度進(jìn)行數(shù)學(xué)描述。

1 最小編輯距離的原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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）對(duì)此最小編輯距離算法做了歸納。

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

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

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

采用最小編輯距離算法，在圖4中，首先要?jiǎng)h除intention中的i，從第1列第0行開始計(jì)算。

圖4中的一種可行的計(jì)算步驟如下：

——首先刪除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分。

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

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

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

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

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

——首先刪除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ù)語研究

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

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

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

磁盤存儲(chǔ)器

磁盤機(jī) * *

s d d

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

磁盤存儲(chǔ)器

磁盤驅(qū)動(dòng)器

s s

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

磁盤存儲(chǔ)器

磁頭 * * *

s d d d

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

磁盤存儲(chǔ)器

磁頭加載區(qū)

s s s s

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[1] 馮志偉.自然語言處理簡(jiǎn)明教程[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.

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

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

于洋（1988—），男，博士，大連海事大學(xué)外國(guó)語學(xué)院講師。主要研究方向?yàn)橛?jì)量語言學(xué)、語料庫(kù)語言學(xué)和詞源學(xué)等。通信方式：yuyang89@dlmu.edu.cn。