Does Levenshtein distance understand meaning?

No. It compares sequences through permitted edits.

Can it compare sequences of different lengths?

Yes. Insertions and deletions handle length differences.

Is swapping two neighboring letters one edit?

Not in the standard operation set. A transposition-aware variant uses a different rule.

AI Glossary / Mathematics and optimization / Intermediate

Levenshtein Distance

Definition

Levenshtein distance is the minimum number of single-symbol insertions, deletions, and substitutions needed to transform one sequence into another, when each operation costs one. Matching a symbol to itself costs zero. It measures differences in sequence form, such as spelling, rather than similarity of meaning.

What it means

A small distance means that few allowed edits can change one sequence into the other. The sequences can have different lengths, unlike the usual setting for Hamming distance. The result depends on what counts as a symbol: characters, words, or another explicitly chosen sequence unit.
The standard unit-cost version is symmetric and forms a metric on sequences over a fixed alphabet. Weighted edit-distance variants can assign different costs, and their properties depend on those choices. The name is sometimes used with alternative cost conventions, so the convention should accompany an example or implementation comparison.
For text applications, preprocessing also matters. Case conversion, punctuation removal, and Unicode normalization can change the sequences before distance is calculated. These steps can be useful, but they are part of the matching policy rather than hidden properties of the distance.

How it works

A standard dynamic-programming method builds a table of distances between prefixes. Let D(i,j) be the distance between the first i symbols of one sequence and the first j symbols of the other. Set D(i,0)=i and D(0,j)=j because an empty sequence requires only deletions or insertions.
For each remaining cell, choose the least cost among deleting a symbol, inserting a symbol, or matching/substituting the next pair. The recurrence is D(i,j)=min[D(i−1,j)+1, D(i,j−1)+1, D(i−1,j−1)+c], where c is zero for a match and one otherwise.
The final cell gives the distance. Keeping predecessor information can also recover an edit sequence, and several optimal sequences may exist. The basic table takes time proportional to the product of the sequence lengths; storing only the needed rows can reduce memory when only the distance is required.

Three practical examples

A spelling assistant can generate candidate corrections whose written forms are close to an input word.
A data-cleaning workflow can flag similar product names for review without assuming that every close pair identifies the same product.
A speech-recognition evaluation can count word-level insertions, deletions, and substitutions against a reference transcript, with the tokenization policy stated.

Think of it this way

Think of a copy editor working under a rule that each inserted, removed, or replaced symbol costs one token. The editor seeks the cheapest transformation. The analogy captures edit cost, but it does not imply that the cheapest edit preserves meaning or that every human typing mistake has the same likelihood.

Worked example

Consider an original comparison between the character strings cat and cut. Include the empty prefix before each string. With target columns empty, c, cu, and cut, the initial table row is (0,1,2,3). The row for source prefix c is (1,0,1,2). The row for ca is (2,1,1,2), and the row for cat is (3,2,2,1).
The final value is 1, achieved by substituting u for a. A zero-cost transformation is impossible because the strings differ, so this one-edit sequence is optimal.
Now compare cart with charts. Insert h after c to obtain chart, then append s to obtain charts. This uses two edits. The lengths differ by two, and each allowed operation changes length by at most one, so at least two edits are necessary. The distance is therefore exactly 2 without needing the full table.
Finally, compare ab with ba. A person may describe this as one swap, but an adjacent transposition is not an allowed one-step operation in standard Levenshtein distance. Two substitutions suffice, and one insertion or deletion cannot preserve the two-character length while making the required change. Its distance is 2. A distance definition that explicitly permits transpositions can give a different answer, which is why edit-operation rules must be named.

Illustrative case study

In a fictional catalog-maintenance team, an analyst uses character edit distance to flag near-duplicate product names. The short codes AB and BA are close, but they refer to distinct items. Two long descriptive names differ only by a suffix that indicates a different package size.
The team keeps distance as a candidate-generation signal and checks identifiers and attributes before merging anything. It records the case and punctuation policy so reviewers can reproduce the comparisons. This scenario illustrates an assisted review workflow, not an automatic guarantee of duplicate detection or a measured company result.

Common misconceptions and mistakes

Do not treat a small edit distance as proof of semantic similarity or entity identity. Different words can be one edit apart while meaning very different things. Conversely, synonyms can have very different spellings.
Do not count a transposition as one standard Levenshtein edit. Do not silently mix unit-cost substitution with a substitution cost of two. A raw distance is not automatically a percentage, and any normalized score needs its denominator and edge cases defined. Also, a visible character can consist of multiple code points, so a technical character representation may differ from a reader's perception.

Business use

For business use, choose sequence units and preprocessing that fit the task. Test matching thresholds on realistic examples, especially short identifiers, repeated names, abbreviations, and values whose small differences are operationally meaningful. Evaluate false matches as well as missed matches.
Distance-based candidate generation can reduce a large review problem, but the final decision may need context or additional fields. Where identifiers encode critical distinctions, an apparently minor spelling difference may be the most important part of the record. Keep the original text available so reviewers can understand what the comparison normalized or removed.

Check your understanding

What is the unit-cost Levenshtein distance between an empty string and book?

Answer: 4, because all four characters must be inserted. The reverse transformation requires four deletions.

Related terms

Edit distance
Dynamic programming
Hamming distance
Tokenization
Word error rate
string matching
Damerau-Levenshtein distance
Unicode normalization
fuzzy matching

Learn next

Next, fill a prefix-distance table for two short strings and trace one optimal edit path. Then compare character-level and word-level distances on the same sentence pair to see how the chosen sequence unit changes the question.

Sources

Primary teaching reference: Daniel Jurafsky and James H. Martin, Speech and Language Processing, Words and Tokens, minimum edit distance section: https://web.stanford.edu/~jurafsky/slp3/2.pdf . This article explicitly uses unit-cost substitutions; the source also demonstrates an alternative substitution cost of two.

Previous: Levenshtein coding Next: Leverage