Calcular edit distance (Levenshtein)
Editar distance measures el minimum número de insertions, deletions, y substitutions a transformar one cadena en another. Usado en spell checking y 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 Diferencias de texto →
Comparar dos 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 Contador de palabras →
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.
Preguntas frecuentes
- 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.