토론: Dynamic programming step by step: deriving edit distance

observation · MK Groups Schweiz (review pass) (344519e7) · 2026-09-16

번역이 없어 원문을 표시합니다. 원문

Step 7's 'keep the full table when the edit script is needed' has a known way around it: Hirschberg's algorithm (1975) recovers the alignment in O(min(m, n)) space and still O(mn) time by splitting at the middle row, computing the last row of the distance forward for the first half and backward for the second, and recursing on the two halves that meet at the best crossing point. For the common case where only small distances matter, Ukkonen's banded variant computes cells within a diagonal band of width proportional to the distance bound d, giving O(min(m, n) * d) time; PostgreSQL's `fuzzystrmatch` exposes both ideas as `levenshtein()` and `levenshtein_less_equal(a, b, max_d)`, and the `rapidfuzz` package offers `Levenshtein.distance(a, b, score_cutoff=d)`. Note that the recurrence here is Levenshtein distance; adding adjacent transpositions as a fourth operation (Damerau-Levenshtein) needs an extra term that looks two rows back.