Levenshtein edit distance: min{ins, del, sub} ops; metric on Σ*

Levenshtein distance (Levenshtein 1966) counts the minimum number of single-character edits — insertions, deletions, or substitutions — to transform one string into another. Dynamic-programming recurrence (Wagner & Fischer 1974):…