編輯距離（Levenshtein Distance）
什麼是編輯距離？
編輯距離（Levenshtein Distance） 計算將一個字串轉換成另一個所需的最少編輯次數（插入、刪除、取代）。
| 操作 | 成本 | 範例 | |------|------|------| | 插入 | 1 | "cat"→"cats"（加 's'） | | 刪除 | 1 | "cats"→"cat"（刪 's'） | | 取代 | 1 | "cat"→"cut"（'a'→'u'） | | 相符 | 0 | "cat"→"cat"（相同字母） |
實作
def edit_distance(s1, s2):
"""回傳將 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 # 變成空字串需刪除 i 次
for j in range(n + 1):
dp[0][j] = 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(f"kitten→sitting: {edit_distance('kitten', 'sitting')} 步")
print(f" k→s(1), e→i(1), 插入g(1) = 3")
print(f"Vibe→Vibes: {edit_distance('Vibe', 'Vibes')} 步")
print(f"Sunday→Saturday: {edit_distance('Sunday', 'Saturday')} 步")
實際應用：拼寫檢查
def spell_check(word, dictionary):
scored = [(w, edit_distance(word, w)) for w in dictionary]
scored.sort(key=lambda x: x[1])
return scored[:5]
dictionary = ["coding", "vibe", "tutor", "python", "algorithm",
"react", "nextjs", "docker", "kubernetes", "typescript"]
misspelled = "codng"
suggestions = spell_check(misspelled, dictionary)
print(f"\n拼寫建議: '{misspelled}' →")
for word, dist in suggestions:
print(f" {word} (距離: {dist})")
應用場景
| 領域 | 用途 | |------|------| | 拼寫檢查器 | 為錯字建議正確拼寫 | | DNA 定序 | 計算基因突變距離 | | 抄襲檢測 | 偵測經修改的抄襲 | | 語音識別 | 匹配轉錄文字與已知短語 | | 模糊搜尋 | 即使有錯字也能找到匹配 |
總結
| 面向 | 詳情 | |------|------| | 狀態定義 | dp[i][j] = s1[:i] 轉換為 s2[:j] 的最小編輯數 | | 遞迴關係 | 相符: 0+dp[i-1][j-1] | 不符: 1+min(刪除, 插入, 取代) | | 初始條件 | dp[i][0]=i, dp[0][j]=j | | 時間 | O(m×n) | | 空間 | O(m×n) → 可優化到 O(min(m,n)) | | 變體 | Damerau-Levenshtein（增加互換）、Hamming（僅等長字串） |
為什麼你需要學會編輯距離？
這不是理論，這是實戰工具
編輯距離不是那種「寫完作業就再也用不到」的演算法。它在真實世界中隨處可見：
| 場景 | 怎麼用編輯距離？ | |:----:|----------------| | ✏️ 拼寫檢查 | 當你輸入「recieve」，系統計算它與「receive」的距離為 1（'ei'→'ie'互換），自動修正 | | 🧬 DNA 序列比對 | 計算兩個基因序列的相似度，判斷兩物種的演化關係 | | 🔍 抄襲偵測 | 將兩篇文章轉換為字串序列，編輯距離越小代表越相似 | | 📝 自動評分 | OCR 辨識結果與標準答案的編輯距離 = 錯誤字數，直接算出分數 | | 🎵 音樂檢索 | 哼一段旋律，系統比對旋律序列的編輯距離找到最接近的歌曲 | | 🌐 Google 搜尋 | 「您的意思是：xxx」——就是編輯距離的經典應用 |
為什麼 DP 是唯一解？
你可能想問：為什麼不用暴力法？
暴力法：嘗試所有可能的編輯序列
字串長度 n=10 → 約 3^10 ≈ 59,049 種可能
字串長度 n=20 → 約 3^20 ≈ 35 億種（已經跑不動了）
字串長度 n=100 → 3^100 ≈ 5×10^47（宇宙滅亡都算不完）
DP 解法：O(m×n) = 100×100 = 10,000 次運算
快了 5×10^43 倍！
這就是動態規劃的威力——把指數級暴力搜尋變成多項式時間可解。
空間優化實戰
def edit_distance_optimized(s1, s2):
"""只用兩列的空間優化版本"""
m, n = len(s1), len(s2)
if m < n:
s1, s2 = s2, s1
m, n = n, m
prev = list(range(n + 1))
curr = [0] * (n + 1)
for i in range(1, m + 1):
curr[0] = i
for j in range(1, n + 1):
cost = 0 if s1[i-1] == s2[j-1] else 1
curr[j] = min(
prev[j] + 1, # 刪除
curr[j-1] + 1, # 插入
prev[j-1] + cost # 取代
)
prev, curr = curr, prev
return prev[n]
# 比較效能
import time
s1 = "kitten" * 100 # 600 字元
s2 = "sitting" * 100 # 700 字元
start = time.time()
result = edit_distance_optimized(s1, s2)
time_taken = time.time() - start
print(f"編輯距離: {result}")
print(f"O(min(m,n)) 空間: {time_taken:.4f}秒")
print(f"字串長度: {len(s1)}×{len(s2)} = {len(s1)*len(s2)} 次運算")
下一步：編輯距離的進階應用
學完經典的 Levenshtein Distance 後，你可以進一步探索：
| 應用 | 說明 | 變化 | |:----:|------|------| | Damerau-Levenshtein | 增加「相鄰字元互換」操作 | 更貼近真實打字錯誤 | | 加權編輯距離 | 不同操作給予不同成本 | 取代成本 2、插入成本 1 | | 最長共同子序列 (LCS) | 編輯距離的變形，只允許插入刪除 | DNA 比對常用 | | 語音相似度比對 | 結合 Soundex + 編輯距離 | 姓名模糊比對 |
下一章 拼寫檢查 API 將把本章的編輯距離包裝成完整的 FastAPI 服務，讓你的前端應用可以直接呼叫拼寫檢查功能距離** | 不同操作給予不同成本 | 取代成本 2、插入成本 1 |\n| 最長共同子序列 (LCS) | 編輯距離的變形，只允許插入刪除 | DNA 比對常用 |\n| 語音相似度比對 | 結合 Soundex + 編輯距離 | 姓名模糊比對 |\n\n下一章 拼寫檢查 API 將把本章的編輯距離包裝成完整的 FastAPI 服務，讓你的前端應用可以直接呼叫拼寫檢查功能！"}]}