Edit Distance Calculator
The Levenshtein edit distance between two strings — the fewest single-character insertions, deletions and substitutions to turn one into the other — with the normalised similarity, the operation counts and the alignment.
Edit distance is computed by dynamic programming: a grid where each cell holds the cheapest way to match a prefix of one string with a prefix of the other.
How the edit distance calculator works
Edit distance is computed by dynamic programming: a grid where each cell holds the cheapest way to match a prefix of one string with a prefix of the other. The bottom-right cell is the answer, and walking back through the grid recovers which edits were made.
It is the workhorse of spell-checking, fuzzy matching, deduplication and word error rate. Normalised by the longer string it becomes a similarity from 0 to 1, which is what a matching threshold is set against.
Formula: d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + [aᵢ ≠ bⱼ]); similarity = 1 − d / max(|a|, |b|)
Worked examples
| Inputs | Edit distance | Note |
|---|---|---|
| kitten to sitting | 3 | the textbook 3 |
| A typo | 2 | two edits |
| Unrelated | 5 | five |
FAQFrequently asked questions
What is Levenshtein distance?
The minimum number of single-character insertions, deletions or substitutions that turn one string into another. "kitten" to "sitting" is three.
What is it used for?
Spell-checking, fuzzy search, record matching and deduplication, DNA sequence comparison, and word error rate for speech — anything that needs "how different are these".
How is similarity defined?
One minus the distance divided by the longer string's length. It runs from 0 to 1; a threshold of about 0.8 is a common fuzzy-match cut-off.
Is it the same as Damerau–Levenshtein?
Damerau adds transposition of adjacent characters as a single edit, so "ab" to "ba" costs one instead of two. This page is plain Levenshtein.
Why the 400-character limit?
The algorithm builds a grid of both lengths multiplied, which is fine for words and short lines. For documents use a diff tool or a token-level distance.
Where these figures come from
- Vaswani et al. (2017) — Attention Is All You Need — the transformer architecture the memory arithmetic follows
- Kaplan et al. (2020) — Scaling Laws for Neural Language Models — the compute relationship used for training estimates
- Hoffmann et al. (2022) — Training Compute-Optimal Large Language Models — the tokens-per-parameter guidance ("Chinchilla")
- IEEE 754 — Standard for Floating-Point Arithmetic — the numeric formats behind bytes per parameter
- AI Safety Institute — the UK government AI body
Last checked: September 2026. The relationships here are architectural, not vendor-specific: bytes per parameter follow the numeric format, KV-cache size follows the transformer definition, and token-per-word ratios come from published tokeniser behaviour.