不知道你是否曾好奇，像 Google 或 Bing 這類搜尋引擎，是如何辨識你輸入的錯別字？例如，當你輸入 “seperate”（錯誤拼字）時，搜尋引擎能夠自動修正為正確的 “separate”，並以正確拼字進行搜尋和呈現結果。
本文將介紹一種演算法 — Levenshtein Distance（或稱萊文斯坦距離）！透過這個演算法，我們可以了解搜尋引擎如何尋找相似的單字，而且這個演算法也被知名的 Elasticsearch 所使用，相當值得認識！
接下來，本文將從編輯距離(edit distance)的概念出發，逐步帶你深入了解 Levenshtein Distance。
本文環境
- Python 3
Edit distance / 編輯距離
針對如何找尋相似字這個問題，首先需要解決的核心問題是：如何衡量兩個字之間的相似程度（或稱為距離）。
為了解決這個問題，一種名為編輯距離的概念應運而生：
The minimum edit distance between two strings is the minimum numer of editing operations needed to convert one string into another. The editing operations can consist of insertions, deletions and substitutions.
簡單來說，假設有兩個字串 a 和 b，我們可以透過插入（insertions）、刪除（deletions）和取代（substitutions）三種操作，將字串 a 轉換為字串 b，而最小編輯距離，就是完成這個轉換所需的最少操作次數。（你也可以將每次編輯操作視為付出一次成本，而最小編輯距離就是將 a 換成 b 的最小成本。）
舉下列將 explanations 變為 explanation 為例：
explanations -> explanation # 1 deletion
上述兩個字串的編輯距離為 1，最少只要經過 1 次刪除字元的操作，就能夠將 explanations 轉變為 explanation。
反過來要將 explanation 變為 explanations 的編輯距離也是 1，即經過 1 次插入字元的操作：
explanation -> explanations # 1 insertation
如果是下列將 coarse 轉變為 course 的情況，則只要經過 1 次取代字元，因此編輯距離為 1：
coarse -> course # 1 substitution
最後再舉一個例子計算 Mannhaton 與 Manhattan (曼哈頓島)的編輯距離：
Mannhaton -> Manhattan
這個例子需要經過：
- 1 次刪除（刪除 n ）
- 1 次插入（插入 t ）
- 1 次取代（以 a 取代 o ）
因此將 Mannhaton 轉變為 Manhattan 的最小編輯距離為 3。
如果以 Python 的語法表示的話，如下所示：
>>> s = "Mannhaton"
>>> s = s[:2] + s[3:] # deletion
>>> s
'Manhaton'
>>> s = s[:5] + "t" + s[5:] # insertion
>>> s
'Manhatton'
>>> s = s[:7] + "a" + s[8:] # substitution
>>> s
'Manhattan'
以上是編輯距離的概念。
所以實際上尋找相似的單字或者字詞自動修正功能的最簡單做法，就是找出編輯距離足夠小的字詞。
Levenshtein Distance / 萊文斯坦距離
有了編輯距離的概念之後，就可以開始認識何謂 levenshtein distance（或稱萊文斯坦距離），因為 levenshtein distance 也是以刪除、插入與取代 3 種操作計算 2 個字的距離（編輯距離）。
在實際應用中，Elasticsearch 的模糊查詢(fuzzy query)也是使用 levenshtenin distance 找出相似字，讓我們的搜尋功能可以具有一些模糊的空間（或容錯），例如搜尋 “OpenAPI” 也可以搜到 “OpenAI” 的結果，因為兩個詞的 levenshtenin distance 距離為 1，兩者編輯距離相當接近，十分可能也是使用者想要搜尋的字詞。
下列是 Wikipedia 上關於 Levenshtein Distance 的數學定義，共有 4 種情況：
定義看似很難，但其實可以一步步拆解。
首先看到 lev(a, b) = |a| 與 lev(a, b) = |b| 這兩個部分。
假設有 a 與 b 兩個字串，當 a 字串長度（以 |a| 表示）為零，levenshtein distance 等於字串 b 的長度。這是因為 a 需要進行與 b 長度（以 |b| 表示）相同次數的插入操作，才能將字串 a 轉換為字串 b。反之亦然。
接著繼續看 lev(a, b) = lev(tail(a), tail(b)) 的部分，該部分是指 a 與 b 兩個字串前段相同的情況下，levenshtein distance 會由剩下的字串決定，也就是 tail(a) 與 tail(b)，由於相同的部分編輯距離為 0，因此尚未比較的字串將決定最終的 levenshtein distance。
我們舉 abce 與 abde 為例，這兩個字串開頭都是 ab ，不需進行任何編輯操作，因此 Levenshtein Distance 其實等同於：
lev("abce", "abde") = lev("ce", "de")
而 lev("ce", "de") 對應的正是 levenshtein distance 數學定義中的最後一種情況：
1 + min(
lev(tail(a), b),
lev(a, taib(b)),
lev(tail(a), tail(b)
)
繼續將 lev("ce", "de") 代入的話，其實等於下列形式：
1 + min(
lev("e", "de"), // 1
lev("ce", "e"), // 1
lev("e", "e"), // 0
)
因為 ce 的 c 不等於 de 的 d，數學定義開頭的 1 代表將 c 變成 d 的過程一定需要 1 次編輯操作。而將 c 變成 d 的之後，也會影響後續字串的比較，所以 min(...) 的部分代表後續字串的最小編輯距離，將這個最小值與開頭的 1 相加後，就是第 4 種情況的編輯距離。
min(...) 的部分乍看之下不易理解，但實際上它對應的是對 ce 中的 c 所執行的三種操作：刪除、插入和替換。具體如下：
1 + min(
lev("e", "de"), // 刪除 c，剩餘的字串變成 e 與 de 的比較
lev("ce", "e"), // 在 c 的位置插入 d，剩餘字串變成 ce 與 e 的比較
lev("e", "e"), // 替換 c 變成 d，剩餘字串變成 e 與 e 的比較
)
上述 min(...) 的部分，可以看到最後一種替換操作的編輯距離為 0，因此整體編輯距離為 1 + 0，最小編輯距離為 1，這也是 abce 與 abde 的 levenshtein distance。
看完 levenshtein distance 的數學定義之後，有程式設計基礎經驗的人，應該可以直覺想到使用遞迴(recursion)的方式實作 levenshtein distance，以下是用 Python 實作 Levenshtein Distance 的程式碼：
def lev(a, b):
if len(a) == 0:
return len(b)
if len(b) == 0:
return len(a)
if a[0] == b[0]:
return lev(a[1:], b[1:])
return 1 + min(
lev(a[1:], b),
lev(a, b[1:]),
lev(a[1:], b[1:]),
)
以下是其執行結果：
assert lev("abc", "ab") == 1
assert lev("abcd", "abde") == 2
assert lev("abce", "abde") == 1
assert lev("abcde", "abde") == 1
assert lev("python", "peithen") == 3
除了使用遞迴的方式來實作 levenshtein distance 外，其實也可以透過動態規劃（dynamic programming）來實作，以下是以動態規劃實作 levenshtein distance 的 Python 程式碼：
def lev(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# initialize
for i in range(1, m + 1):
dp[i][0] = i
for j in range(1, n + 1):
dp[0][j] = j
# dynamic programming
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i-1] == b[j-1]:
cost = 0
else:
cost = 1
dp[i][j] = min(dp[i-1][j] + 1, # 刪除
dp[i][j-1] + 1, # 插入
dp[i-1][j-1] + cost) # 替換
return dp[m][n]
舉 abc 與 adc 兩個字串為例，上述動態規劃的程式碼最終會生成一個類似下表的 m x n 大小的表格，表格中的每個格子會紀錄兩個字串在不同位置下的最小 levenshtein distance：
| empty string | a | d | c | |
|---|---|---|---|---|
| empty string | 0 | 1 | 2 | 3 |
| a | 1 | 0 | 1 | 2 |
| b | 2 | 1 | 1 | 3 |
| c | 3 | 2 | 2 | 1 |
舉第一列 empty string 為例：
| empty string | a | d | c | |
|---|---|---|---|---|
| empty string | 0 | 1 | 2 | 3 |
它所記錄的結果就是 empty string 與下列字串比較的最小 Levenshtein Distance：
lev(empty string, empty string) = 0
lev(empty string, a ) = 1
lev(empty string, ad ) = 2
lev(empty string, adc ) = 3
其他列的解讀也以此類推。
大家應該很好奇為什麼這個表格可以計算出 levenshtein distance，特別是下列關鍵片段程式碼：
if a[i-1] == b[j-1]:
cost = 0
else:
cost = 1
dp[i][j] = min(dp[i-1][j] + 1, # 刪除 / deletion
dp[i][j-1] + 1, # 插入 / insertion
dp[i-1][j-1] + cost) # 替換 / substitution
相信大家比較容易無法理解 dp[i-1][j] + 1 與 dp[i][j-1] + 1 會分別代表刪除與插入的 levenshtein distance。
我們直接舉將 ab 轉變為 c 字串為例：
| empty string | c | |
|---|---|---|
| empty string | 0 | 1 |
| a | 1 | 1 |
| b | 2 | ? |
p.s. 表格索引值從 0 開始
要算出刪除 ab 的 b 的 levenshtein distance 的話（i = 2, j = 1)，會發現正好取決於前 1 個字元的 levenshtein distance 再加上刪除操作的 1，而前一個字元的 levenshtein distance 正好處於 (i - 1, j) 的位置，對應表格 (1, 1) 的位置，該值為 1，因此刪除 b 的 levenshtein distance 會是 1 + 1 = 2。(等於先算出 a 變成 c 的 levenshtein distance，再加上刪除 b 的操作。）
再舉將 a 轉變為 ad 字串為例（只要插入 d 即可）：
| empty string | a | d | |
|---|---|---|---|
| empty string | 0 | 1 | 2 |
| a | 1 | 0 | ? |
p.s. 表格索引值從 0 開始
要算出插入 d 的 levenshtein distance 的話（i = 1, j = 2)，也會發現正好取決於前 1 個字元的 levenshtein distance 再加上插入操作的 1，而前一個字元的 levenshtein distance 正好處於 (i, j - 1) 的位置，對應表格 (1, 1) 的位置，該值為 0，因此插入 d 的 levenshtein distance 為 0 + 1 = 1。（等於先找出 a 變成 a 的 levenshtein distance，再加上插入 d 的操作。）
最後再舉 ab 與 cd 為例：
| empty string | c | d | |
|---|---|---|---|
| empty string | 0 | 1 | 2 |
| a | 1 | 1 | 2 |
| b | 2 | 2 | ? |
p.s. 表格索引值從 0 開始
要計算替換操作的 levenshtein distance 的話（i = 2, j = 2)，它必須加上兩個字串的前一個字元比較的 levenshtein distance，例如 ab 變成 cd，要將 b 替換成 d 時，就必須先看 a 與 c 的 levenshtein distance 再加 1，而前一次的比較結果恰好處於 [i-1][j-1] 位置，對應表格 (1, 1) 的位置，而因為 a 與 c 並不相等（對應程式碼中的 cost），所以 a 與 c 的 levenshtein distance 為 1，再加上將 b 變成 d 的替換操作，因此 ab 變成 cd 的 levenshtein distance 為 1 + 1 = 2。（等於先找出 a 變成 c 的 levenshtein distance，再加上替換的操作。）
以上就是關於 levenshtein distance 的介紹囉！
總結
透過本文的介紹，我們從編輯距離的基本概念出發，逐步深入了解 levenshtein distance 的數學定義與 Python 的實作（包括遞迴與動態規劃），這個演算法不僅具有理論價值，還在實際應用中發揮了重要作用，例如 Elasticsearch 搜尋引擎的模糊查詢(fuzzy query)或字詞自動修正功能，理解 levenshtein distance 的運作，將有助於在類似需求的情境下，選擇適合的演算法來解決問題。
以上！
Happy Coding!
References
Levenshtein distance - Wikipedia
