萊文斯坦距離(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 是字串比對、模糊搜尋不可或缺的演算法。歡迎留言討論你的應用經驗!