CoreSource checked

Ukkonen Edit Distance

Ukkonen Edit Distance scores how similar two strings, sets, or sequences are.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Intermediate
Family: Pattern Matching
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 1
Code example: Ready
Visualization: Ready

Overview

Ukkonen Edit Distance is a pattern matching method that compares strings or sequences with exact, approximate, indexed, or similarity-based matching. It clarifies whether the task needs exact lookup, approximate distance, indexing, or similarity scoring.

Core Concepts

sequence comparisonmatching statesimilarity scorepattern statecomparisonmatch scoring

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n m)

Space

O(m)

When to Use

Use Ukkonen Edit Distance when its matching rule matches the desired notion of equality or similarity.
Use it when preprocessing or index-building costs are justified by repeated queries.

When Not to Use

Avoid when the distance or matching rule does not match user-facing similarity.
Avoid when index construction costs exceed the benefit for one-off queries.

What It Does

Compares sequences or indexed text
Uses exact or approximate matching rules
Returns matches, distances, or alignments

Use Cases

Text search
Biosequence comparison
Deduplication and similarity search

Inputs

Text or sequence
Pattern or query
Matching parameters

Outputs

Match positions
Similarity score
Alignment or index lookup result

Key Formulas (1)

Banded edit recurrence

D_[i,j] = min(D_[i−1,j] + 1, D_[i,j−1] + 1, D_{[i−1,j−1]} + cost)

D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + cost)

Computes edit distance only within a band around the diagonal.

Pseudocode

1.Prepare the pattern, sequence, table, or index
2.Compare characters, tokens, sets, or states
3.Update scores, automaton state, or match candidates
4.Record matches, distances, alignments, or similarity scores
5.Return the best results

Canonical Example

Input: text = 'abracadabra', pattern or query = 'abra'
Output: matches or similarity score
Explanation: Ukkonen Edit Distance compares the query against the text or sequence and returns the matching result.

Implementation Notes

Normalize input text or sequence symbols before matching.
Keep index construction and query-time costs separate in benchmarks.

Common Pitfalls

Choosing the wrong similarity metric can optimize for the wrong matches.
Forgetting Unicode, tokenization, or normalization can create inconsistent results.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show the pattern advancing through the text or the dynamic table used to compare sequences.

Input:ABABABCABAB

Window:ABAB

Step 1 of 5: Prepare the pattern, sequence, table, or index

pattern-matching

Notes

Ukkonen Edit Distance operates in O(n) time and O(m) space within the Pattern Matching family. Key governing relation: D[i,j] = min(D[i-1,j] + 1, D[i,j-1] + 1, D[i-1,j-1] + cost). Often compared with Knuth-Morris-Pratt and Boyer-Moore.

Sources (2)

What each reference supports for this entry.

Ukkonen Approximate String Matching

Paper

Reference for bounded edit-distance dynamic programming and thresholded approximate matching.

Open source

Flexible Pattern Matching in Strings

Book

Pattern-matching reference covering Ukkonen Edit Distance approximate matching model, string similarity measure, or bit-parallel search strategy.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Alternative toKnuth-Morris-Pratt

Pattern Matching · Foundation

Ukkonen Edit Distance offers a different exact, approximate, or indexed matching strategy than Knuth-Morris-Pratt.

Compare with this

Relationships

View full relationship page