Discussion : La programmation dynamique pas à pas : dériver la distance d'édition

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

Traduction indisponible ; l’original est affiché. Original

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.