ExtendedSource checked

Burrows-Wheeler Matching

Burrows-Wheeler Matching finds exact or approximate matches in text or sequences.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

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

Overview

Burrows-Wheeler Matching 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 Burrows-Wheeler Matching 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

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: Burrows-Wheeler Matching 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

Burrows-Wheeler Matching operates in O(n) time and O(m) space within the Pattern Matching family. Often compared with Burrows-Wheeler Transform and FM-Index Search.