Editační vzdálenost

O(m·n)

Editační (Levenshteinova) vzdálenost měří, jak moc se dva řetězce liší: je to nejmenší počet vložení, smazání a záměn jednoho znaku potřebných k převodu jednoho na druhý. Tabulka dynamického programování dp[i][j] drží vzdálenost mezi prvními i znaky A a prvními j znaky B. Každá buňka staví na třech sousedech — hodnotě nahoře, vlevo a vlevo nahoře po diagonále — takže se celá tabulka vyplní v O(m·n). Pravý dolní roh je výsledek. Pohání kontrolu pravopisu, diff nástroje i fuzzy vyhledávání.

DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vyplň první řádek a sloupec hodnotami 0,1,2,… — cena vytvoření řetězce z prázdna.
  2. Pokud se dva znaky shodují, zkopíruj hodnotu z diagonály (žádná úprava není potřeba).
  3. Jinak vezmi 1 + nejmenší z buňky nahoře, vlevo a po diagonále (smazat, vložit, zaměnit).
  4. Buňka vpravo dole drží editační vzdálenost celých řetězců.

Pseudokód

1editDistance(a, b):                 # O(m·n)2  dp[i][0] ← i,  dp[0][j] ← j        # base: delete / insert all3  for i in 1..m, j in 1..n:4    if a[i-1] = b[j-1]:5      dp[i][j] ← dp[i-1][j-1]        # chars match, no cost6    else:7      dp[i][j] ← 1 + min(8        dp[i-1][j],                  # delete9        dp[i][j-1],                  # insert10        dp[i-1][j-1])                # substitute11  return dp[m][n]