Can two correct lists differ?

Yes. Multiple transformations can reach the target, and more than one can have minimum cost.

Does an operation list explain the author's intention?

No. It explains an algorithmic transformation. A human may have rewritten a phrase as a single conceptual change even when the algorithm reports several character edits.

AI Glossary / Natural language and speech / Intermediate

Operation list

Definition

Definition: In string comparison, an operation list is an ordered description of edits that transform one sequence into another. In the source glossary's edit-distance context, the edits include insertions, deletions and substitutions. The list explains a transformation, whereas a distance value summarizes its cost.

What it means

What it means: Two strings can differ by the same number of edits but require different changes. A score of two does not tell an editor which characters to replace or a speech evaluator which words were omitted. An operation list supplies that missing detail.
The term has other meanings in computing, so this entry uses the string-alignment sense found in Speech and Language Processing. A complete representation must identify the affected characters or tokens and their positions or alignment. Bare labels such as “insert, substitute” are not enough to reproduce every transformation.

How it works

How it works: An edit-distance algorithm compares prefixes of the source and target sequences. It considers the cost of deleting a source item, inserting a target item, or matching or substituting an aligned pair. Dynamic programming retains the best costs for these smaller comparisons.
To recover an operation list, the implementation also records or reconstructs predecessor choices and follows a path through the comparison table. Reading the path in the forward direction gives the edits. Unchanged matches may be included explicitly or left implicit in an alignment. Several paths can have the same minimum cost, so a tie-breaking rule may affect which list is reported without changing the distance.

Three practical examples

Three practical examples:
1. A spelling tool explains that a proposed correction replaces one letter and adds another. The explanation helps a reviewer distinguish a plausible typo from an unrelated word with a similar score.
2. A transcription evaluator aligns reference words with recognized words, then labels substitutions, deletions and insertions. Those labels support error analysis beyond a single overall rate.
3. A text-revision viewer highlights where content changed. Its particular comparison algorithm may favor readable edits rather than the mathematically smallest list under basic character-level costs. A useful display and a minimum edit-distance result need not be identical.

Think of it this way

Think of it: A route's total distance says how far a journey is; turn-by-turn directions say how to follow it. Similarly, an edit cost and an operation list answer different questions. The analogy has limits: edit operations act on discrete symbols, and several equally cheap symbolic routes can exist without representing the same human intention.

Worked example

Worked example: Transform the source “cat” into the target “cuts”, using characters as units, insertion/deletion/substitution cost one, and matching cost zero. One alignment pairs c with c, a with u, t with t, and a gap with s. The corresponding list is: match c; substitute a with u; match t; insert s at the end.
There are two charged edits, so this list costs 2. It is minimal under the stated rules: the target is one character longer, so a one-edit solution would have to be a single insertion. But inserting one character into cat cannot remove or replace its a to produce cuts. Therefore at least two edits are necessary, and the exhibited list achieves that bound.
If substitutions instead cost two, this same list costs three. “Two edits” and “cost two” are therefore not interchangeable unless the cost convention is specified.

Illustrative case study

Illustrative case study: Fictional Cedar Captions reviews a transcription system using reference sentences. Its dashboard initially shows only an aggregate error rate. Reviewers cannot tell whether a new version mostly omits small words or confuses product names.
The team adds aligned word sequences and operation lists using a documented tokenization and scoring convention. Reviewers inspect examples alongside the audio, because the automatically selected alignment is not always the only equally good one. They can now classify the reported errors more carefully. This fictional process demonstrates diagnosis, not a measured performance improvement or a claim that an alignment reveals why the recognizer made an error.

Common misconceptions and mistakes

Common misconceptions and mistakes: An operation list is not necessarily optimal merely because it reaches the target. Its optimality depends on the allowed operations and their costs. A replacement may count as one substitution or as deletion plus insertion under another convention. Swapping adjacent characters is not a basic Levenshtein operation unless the method explicitly adds transposition. Direction matters: deleting from the source corresponds to inserting when reversing the transformation. Finally, offsets may refer to the original sequence or the progressively edited sequence; mixing those conventions can corrupt an otherwise correct edit script.

Business use

Business use: Store enough comparison information to explain automated corrections, review changes and investigate recognition failures. Document the units being compared, normalization rules, cost scheme and tie-breaking policy. For multilingual text, distinguish bytes, Unicode code points, grapheme clusters and words rather than treating them as interchangeable characters. Preserve source and target versions so a reviewer can reproduce the comparison. Where changes will be applied automatically, validate that replaying the operations produces the intended target before modifying an authoritative record.

Check your understanding

Check your understanding: A comparison tool returns three substitutions. Its configuration charges two for each substitution. Is the reported path cost three?

Answer: No. It costs six, assuming there are no other charged operations. The number of listed edits and their total cost are different quantities. Whether six is the minimum still requires comparison against other allowed paths.

Related terms

Learn next

write an alignment for two short strings, then replay the edits to verify the target. Change the substitution cost and compare alternative paths. Finally repeat at word level to see how tokenization changes the reported operations even when the original sentences are unchanged.

Alignment

Sources

Sources: Jurafsky and Martin, Speech and Language Processing, Chapter 2, Section 2.9, operation lists, edit costs and dynamic-programming alignment: https://web.stanford.edu/~jurafsky/slp3/2.pdf . The cat-to-cuts transformation, minimality argument and Cedar Captions case are original illustrations. This entry deliberately uses the source list's string-editing meaning, rather than an unrelated general list of program operations.

Previous: Open world classification Next: Operational analytical processing