Levenshtein Distance
Levenshtein Distance Metric · Also known as: edit distance, Damerau-Levenshtein distance
Levenshtein distance, also called edit distance, measures the minimum number of single-character edits (insertions, deletions, substitutions) needed to transform one string into another. Introduced by Vladimir Levenshtein in 1966, this metric is a true metric (satisfying all distance properties) and is fundamental in computational linguistics, spell checking, DNA sequence comparison, and record linkage. It ranges from 0 (identical strings) to the length of the longer string.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Levenshtein distance is ideal for comparing strings or sequences of discrete symbols where edits are meaningful operations: spell checking, name matching, DNA sequence comparison, and approximate string matching. Use it when you need a true metric and can tolerate O(n*m) computation. For long strings or many comparisons, consider approximations or specialized algorithms (e.g., BK-trees for indexing).
Strengths & limitations
- True metric: satisfies all distance axioms including triangle inequality
- Intuitive operation semantics: insertions, deletions, substitutions are meaningful edits
- Well-established and widely used in NLP, bioinformatics, and record linkage
- Variants (Damerau-Levenshtein, weighted edit distance) extend functionality
- Computationally expensive: O(n*m) time and space for strings of length n and m
- Does not account for phonetic or semantic similarity; treats all substitutions equally
- Not suitable for continuous data; requires discrete, symbol-based data
- Can be dominated by a single large mismatch rather than many small ones
Frequently asked
What is the difference between Levenshtein and Hamming distance?
Hamming distance only works on strings of equal length and counts the number of differing positions. Levenshtein distance works on strings of any length and counts the minimum edit operations (insertions, deletions, substitutions). Levenshtein is more general.
Is Levenshtein distance case-sensitive?
By default, yes. 'Cat' and 'cat' have a Levenshtein distance of 1 (one substitution). Normalize case before comparison if case-insensitivity is desired.
Can I use custom costs for different edit operations?
Yes. The weighted (or restricted) edit distance allows different costs for insertions, deletions, and substitutions. Specify these costs in the dynamic programming matrix computation for domain-specific distance calculations.
How do I optimize Levenshtein distance for long strings?
Use space-efficient implementations (only store two rows instead of the full matrix). For searching within text, use BK-trees or other index structures. Consider approximate algorithms (e.g., approximate matching with early termination) if exact distances are not needed.
Sources
- Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10, 707-710. link ↗
- Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171-176. DOI: 10.1145/363958.363994 ↗
How to cite this page
ScholarGate. (2026, June 3). Levenshtein Distance Metric. ScholarGate. https://scholargate.app/en/decision-making/levenshtein-distance
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Dynamic Time WarpingDecision-making↔ compare