Is edit distance always a whole number?

Unit-cost Levenshtein distance is, but weighted costs can produce other values.

Does distance zero mean identical original text?

It means identical compared sequences under the selected rules; preprocessing may already have removed distinctions from the originals.

Can there be several cheapest edit sequences?

Yes. The minimum cost can be unique as a number even when several different edit paths achieve it.

AI Glossary / Mathematics and optimization / Beginner

Edit distance

Definition

Edit distance measures the minimum cost of changing one sequence into another using a specified set of edit operations. For text, the common Levenshtein version allows insertion, deletion and substitution of individual characters, usually at a cost of one each. Smaller distances indicate greater similarity under those rules. Different allowed operations or costs produce different edit-distance measures.

What it means

The word minimum is essential. You can often invent many sequences of edits that transform the same pair of strings, but edit distance asks for the cheapest valid one. It measures similarity of sequence form, not similarity of meaning. Two near-identical product codes may refer to different items, while two very different words may be synonyms. The unit also matters: character-based, word-based and token-based comparisons need not give the same result. State the representation before interpreting the number.

How it works

A standard dynamic-programming method compares prefixes of the two strings. Let D(i, j) be the minimum cost of converting the first i characters of the source into the first j characters of the target. Initialize D(i, 0) = i and D(0, j) = j for unit costs. Each new cell is the minimum of deleting a source character, inserting a target character, or matching/substituting the final characters. A match adds zero and a substitution adds one. Filling the table yields the final distance. Recovering an edit sequence requires retaining or reconstructing an optimal path through the table.

Three practical examples

A search box can retrieve candidate spellings that are a few character edits from the user's query.
A data-cleaning tool can flag similar customer-name strings for review alongside other identifiers.
A text-recognition evaluation can count character insertions, deletions and substitutions relative to a reference transcription, using a documented preprocessing and scoring policy.

Think of it this way

Think of a copy editor correcting a line using a menu of permitted changes, each with a price. Edit distance is the cheapest bill for reaching the target line. The analogy captures the optimization problem, but it does not capture meaning, factual correctness or editorial judgment. A cheap change can reverse the meaning of a sentence, and an expensive set of changes can preserve it perfectly.

Worked example

Compare the source string 'plane' with the target 'plans' using unit-cost Levenshtein distance. Replacing the final 'e' with 's' gives the target in one substitution. The strings are different, so zero operations cannot work; therefore the exact distance is 1. Next compare 'plane' with 'planet'. Inserting 't' at the end gives distance 1, and the length difference proves at least one insertion or deletion is necessary. Finally compare 'form' with 'from'. Two substitutions suffice: change the second character from 'o' to 'r' and the third from 'r' to 'o'. One insertion or deletion would change the length, and one substitution cannot correct both differing positions, so the Levenshtein distance is exactly 2. If the chosen variant permits an adjacent transposition at unit cost, swapping 'o' and 'r' gives distance 1 instead. The same strings therefore have different valid distances under different operation sets. For the first pair, one optional normalized score is 1 − d/max(lengths) = 1 − 1/5 = 0.8. That score is a chosen convention, not a universal definition of edit distance or an 80% probability of a match.

Illustrative case study

In a fictional catalog-cleaning project, Maple Parts flags item descriptions with low edit distance. Reviewers discover both harmless spelling differences and distinct codes differing by a single character. They use edit distance to generate candidates, then compare authoritative item identifiers before merging records. The case illustrates a useful screening role and a clear boundary: string proximity alone does not establish that two records represent the same product.

Common misconceptions and mistakes

Do not confuse edit distance with Hamming distance, which counts positionwise mismatches in equal-length sequences and does not model insertions or deletions in the same way. Do not assume all implementations include transpositions. Case folding, punctuation removal and Unicode normalization can change what counts as a character difference. A displayed symbol can contain more than one code point, so character handling must be explicit for multilingual text. Equal distances can also conceal different error types, and a low value does not establish semantic equivalence or identity.

Business use

Specify the sequence unit, allowed operations, costs and preprocessing before selecting thresholds. Test examples from the actual languages and naming conventions involved. Use additional evidence when matching entities, particularly where one mistaken merge could affect many records. Evaluate both missed matches and false matches on reviewed examples. For large candidate collections, use an appropriate retrieval or filtering stage rather than assuming every pair must be compared. Preserve enough detail to explain why a candidate was suggested, including the original strings and, where useful, an optimal edit sequence.

Check your understanding

Why is the distance from 'form' to 'from' not automatically 1?

Answer: Standard unit-cost Levenshtein distance does not include a transposition operation. Under its insertion, deletion and substitution rules, the minimum is 2; a transposition-aware variant can give 1.

Related terms

Learn next

build the small prefix table for 'plane' and 'plans', then trace an optimal path. Repeat the comparison after changing substitution cost to two. Finally test a pair that differs only in case and explain how preprocessing affects the result.

Sources

Sources: Manning, Raghavan and Schütze, Introduction to Information Retrieval, Edit distance, https://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html ; Google, Machine Learning Glossary, edit distance, https://developers.google.com/machine-learning/glossary#edit-distance . The plane/plans/planet and form/from comparisons, normalized-score illustration and fictional catalog case are original.

Previous: Edgelist Next: Edmonds-Karp