Calculer edit distance (Levenshtein)
Éditer distance measures le minimum nombre de insertions, deletions, et substitutions en transformer one chaîne en another. Utilisé en spell checking et fuzzy matching.
- 1
Levenshtein distance is the minimum number of single-character edits (insert, delete, substitute) to transform string A into string B. "kitten" → "sitting" has distance 3 (k→s, e→i, +g). It is computed with dynamic programming: a matrix where cell[i][j] = min(insert, delete, substitute) based on previous cells. Time and space: O(m×n).
- 2 Diff de texte →
Comparer deux texts to see their differences. While text-diff shows line-level changes, edit distance operates at character level. Use text-diff for documents and edit distance for short strings (words, names)
- 3 Compteur de mots →
For word-level edit distance, tokenize both texts into word arrays and compute the distance on the arrays. This measures word-level changes (insertion, deletion, substitution of words) rather than character-level changes.
Questions fréquentes
- What is the difference between Levenshtein and Damerau-Levenshtein?
- Levenshtein allows insert, delete, substitute. Damerau-Levenshtein also allows transposition of adjacent characters (ab → ba in one operation). Damerau is more appropriate for typing errors (adjacent key swaps). Both are O(m×n) time and space.
- How is edit distance used in practice?
- Spell checking (find dictionary words with small distance to the misspelling), fuzzy string matching (find records that are similar but not exact), DNA sequence alignment, and deduplication (merge records with small distance). For large-scale fuzzy search, use a BK-tree or Levenshtein automaton for efficiency.