萊文斯坦距離（Levenshtein Distance）教學與 Python 實作

1. 什麼是萊文斯坦距離？

萊文斯坦距離（Levenshtein Distance）又稱編輯距離，是衡量兩個字串之間差異的指標。它表示將一個字串轉換成另一個字串，最少需要幾次「插入、刪除、替換」操作。

2. 應用場景

  • 拼字檢查、模糊搜尋、推薦系統
  • DNA 序列比對、自然語言處理
  • 使用者輸入自動校正

3. 原理說明

  • 插入（Insert）：將一個字元插入字串
  • 刪除（Delete）：刪除一個字元
  • 替換（Substitute）：將一個字元替換成另一個

4. 動態規劃演算法

Levenshtein Distance 通常用動態規劃（Dynamic Programming）計算，時間複雜度 O(mn)。

5. Python 實作範例

def levenshtein(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

# 範例
print(levenshtein('kitten', 'sitting'))  # 輸出 3

6. 進階應用：字串相似度

可將距離轉換為相似度分數：

def similarity(s1, s2):
    dist = levenshtein(s1, s2)
    return 1 - dist / max(len(s1), len(s2))

print(similarity('apple', 'aple'))  # 越接近 1 越相似

7. 套件推薦

  • python-Levenshtein：高效能 C 擴充套件
  • fuzzywuzzy：封裝多種字串比對方法

8. 注意事項

  • 長字串計算較慢，可考慮優化或近似演算法
  • 可擴充支援「加權編輯距離」

Levenshtein Distance 是字串比對、模糊搜尋不可或缺的演算法。歡迎留言討論你的應用經驗！