編輯距離，也稱為編輯距離，是評估兩個字串之間相似性的基本指標。它計算將一個字串轉換為另一個字串所需的最少操作數。這些操作包括：
這個概念是許多現代應用的核心，例如拼字檢查、模糊搜尋和 DNA 序列比較。
長度分別為 ( n ) 和 ( m ) 的兩個字串 ( A ) 和 ( B ) 之間的編輯距離可以使用動態規劃方法來計算。我們定義一個大小為((n 1) 乘以(m 1)) 的矩陣( D )，其中每個條目( D[i][j] ) 表示將( A ) 的前( i ) 個字元轉換為的最小成本( B ) 的前( j ) 個字元。
遞推關係如下：
這是一個計算 Levenshtein 距離的簡單 Python 實作：
def levenshtein_distance(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
for j in range(m + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif a[i - 1] == b[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[n][m]
# Example usage
print(levenshtein_distance("kitten", "sitting")) # Output: 3
拼字檢查器使用編輯距離來建議拼字錯誤的修正。例如，如果您輸入 helo，它可能會建議您好或英雄。
在搜尋引擎中，即使使用者出現拼字錯誤或拼字錯誤，Levenshtein 也能幫助回傳結果。
在生物資訊學中，這個距離有助於測量兩個 DNA 序列之間的相似性，其中每個操作代表一個潛在的突變。
偵測身分詐欺的系統可以將使用者輸入與現有記錄進行比較，以解決微小的文字差異。
經典演算法使用完整矩陣，這可能會佔用大量記憶體。幸運的是，它可以優化為僅使用兩行內存，因為每個( D[i][j] ) 只取決於( D[i-1][j] ), ( D[i][j-1 ] ), 和( D[i-1][j-1] ).
def optimized_levenshtein(a, b):
n, m = len(a), len(b)
prev = list(range(m + 1))
curr = [0] * (m + 1)
for i in range(1, n + 1):
curr[0] = i
for j in range(1, m + 1):
insert = curr[j - 1] + 1
delete = prev[j] + 1
substitute = prev[j - 1] + (0 if a[i - 1] == b[j - 1] else 1)
curr[j] = min(insert, delete, substitute)
prev, curr = curr, prev
return prev[m]
# Example usage
print(optimized_levenshtein("kitten", "sitting")) # Output: 3
編輯距離是一個強大的、多功能的工具，廣泛應用於各個領域。雖然易於掌握，但其最佳化和複雜的應用凸顯了它在現代系統中的價值。
為了進一步探索，請考慮諸如 Damerau-Levenshtein 距離之類的變體，它可以解釋換位。您現在已經準備好將此工具整合到您的專案中，或以您的深刻理解給您的同行留下深刻的印象！
以上是編輯距離：測量文字相似度的終極指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！
