Levenshtein Edit Distance Calculator

Understanding the Levenshtein edit distance calculator — concept and principle

The Levenshtein distance between two strings is the smallest number of single-character insertions, deletions and substitutions needed to turn one into the other. It is the basis of spell checkers, fuzzy search, "did you mean" suggestions, record matching and DNA sequence comparison. This calculator gives the distance and a simple similarity percentage.

How it is calculated

Let D[i][j] be the distance between the first i characters of A and the first j characters of B.

• D[i][0] = i and D[0][j] = j (delete or insert everything).
• D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + cost), where cost is 0 if the i-th character of A equals the j-th character of B and 1 otherwise.
• The distance is D[len A][len B].
• Similarity = (1 − distance ÷ max(len A, len B)) × 100%.

The principle

Any edit sequence ends with one of three moves on the last characters: delete A's last character, insert B's last character, or match/substitute the two. Whichever is last, the rest must be an optimal edit of shorter prefixes. So the best answer for the full strings can be built from the answers for prefixes, which is the idea of dynamic programming (Wagner–Fischer algorithm). The table has (m + 1)(n + 1) cells, giving O(mn) time; this calculator keeps only two rows, so memory is O(n).

Worked example

1. Inputs: A = "kitten" (6 letters), B = "sitting" (7 letters).
2. Substitute k → s: "sitten".
3. Substitute e → i: "sittin".
4. Insert g at the end: "sitting".
5. No shorter sequence exists, and the table confirms the distance is 3.
6. Similarity: (1 − 3 ÷ 7) × 100 ≈ 57.14%.

How to read the result

Distance 0 means identical strings, and the distance can never exceed the length of the longer string. For typo matching, a distance of 1 or 2 on words of normal length usually indicates the same word. The similarity percentage is a convenience score, not a standard measure; for short strings a single edit changes it a lot.

Common mistakes

• Expecting a transposition such as "ab" → "ba" to count as 1; plain Levenshtein counts it as 2 (Damerau–Levenshtein counts 1).
• Forgetting case and spacing: "Seoul" and "seoul" differ by one substitution.
• Comparing Hangul text whose syllables are stored in decomposed form against composed text, which inflates the distance.

Frequently asked questions

What is a good similarity threshold?

It depends on the data; many fuzzy-search systems allow 1 edit for short words and 2 for longer ones rather than using a fixed percentage.

Is edit distance the same as Hamming distance?

Hamming distance counts only substitutions and requires equal lengths; Levenshtein also allows insertions and deletions.

Can it be computed faster than O(mn)?

If you only need to know whether the distance is at most k, banded algorithms run in about O(k · n).

Sources: V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals", Soviet Physics Doklady 10(8), 1966 · R. A. Wagner, M. J. Fischer, "The string-to-string correction problem", Journal of the ACM 21(1), 1974