๐ค Levenshtein Distance Calculator
Calculates the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into another (the edit distance, or Levenshtein distance), and visualizes which characters changed with color-coded chips. Useful for spell-checking, string similarity scoring, or learning fuzzy-search algorithms.
How to use
- Enter the two strings you want to compare.
- The edit distance and similarity percentage are calculated automatically.
- The breakdown of the transformation (matches, substitutions, insertions, deletions) is shown as color-coded chips.
How the calculation works
The Levenshtein distance (edit distance), devised by Vladimir Levenshtein in 1965, is the minimum number of single-character insertions, deletions and substitutions needed to turn one string into another. This tool fills a dynamic-programming table with the distance between the first i characters of one string and the first j of the other: d[i][j] = d[iโ1][jโ1] if the characters match, otherwise 1 + min(d[iโ1][jโ1], d[iโ1][j], d[i][jโ1]) The bottom-right cell is the answer. The table is then traced back to show which characters were changed and how. Similarity is 1 โ distance รท length of the longer string, as a percentage. Characters are counted as code points, so an emoji counts as one.
Worked example
"kitten" โ "sitting" 1. Substitute k with s (sitten) 2. Substitute e with i (sittin) 3. Insert g at the end (sitting) Distance: 3 Similarity: 1 โ 3 รท 7 โ 57% "ๆฑไบฌ" โ "ไบฌ้ฝ": distance 2 (delete ๆฑ, insert ้ฝ)
Things to be aware of
- Used for spelling suggestions ("did you meanโฆ"), finding near-duplicate records and comparing DNA sequences.
- The work grows with the product of the two lengths, so comparing strings of thousands of characters can be slow.
- Swapping two adjacent characters (ab โ ba) counts as two edits here. The variant that counts it as one is the DamerauโLevenshtein distance.
FAQ
What is edit distance (Levenshtein distance)?
It's the minimum number of single-character insert, delete, and substitute operations needed to turn one string into another.
How is the similarity percentage calculated?
It's 1 minus (edit distance รท length of the longer string), shown as a percentage. A higher value means the two strings are more similar.
Is the comparison case-sensitive?
Yes, the current version compares strings case-sensitively.