String Matching and Text Indexes
String matching starts with a precise definition of “match.” Exact bytes, normalized text, case-insensitive text, prefixes, and arbitrary substrings answer different questions. An index can accelerate the chosen question while faithfully returning the wrong answer if that definition was never settled.
Begin with the query shape and update pattern. A single substring search in a short message rarely needs a persistent index. Repeated prefix lookup across a dictionary or many substring queries over a stable corpus can justify preprocessing. Include build cost, result enumeration, memory, and updates in the comparison.
TL;DR
- Define bytes, code points, normalization, case policy, and returned offsets.
- Distinguish exact lookup, prefix search, substring search, and language-aware retrieval.
- Choose preprocessing from the number and shape of repeated queries.
- Count output size and index updates in performance reasoning.
- Test overlap, empty patterns, Unicode variants, and absent matches.
Quick Example
This complete Python illustration case-folds and NFC-normalizes both inputs, then finds overlapping matches. Its positions refer to the transformed string, not the original display text.
The exact cases passed: banana contains overlapping ana at offsets 1 and 3, decomposed café matches its normalized query, and case folding expands the relevant Straße character. Empty patterns were rejected. The runtime used Unicode database 15.0.0. No language-sensitive collation, grapheme segmentation, original-offset mapping, suffix index, or performance benchmark was tested.
Core Concepts
Pattern preprocessing versus text preprocessing
KMP preprocesses the pattern to support a structured scan. The cited Princeton implementation uses a DFA with alphabet-dependent preprocessing and storage; do not generalize one implementation’s costs to every KMP variant. KMP source and complexity comments
Prefix and suffix structures
A trie follows key prefixes; a suffix array orders the suffixes of a text to support lexicographic queries. These structures serve different query shapes and have implementation-dependent storage and construction costs. Trie interface · Suffix-array interface
Text normalization
Python’s unicodedata documents canonical and compatibility normalization and the database version used by the runtime. Normalization and case folding are separate policy decisions; neither is a complete language-aware search definition. Unicode database API
Match the data structure to the question
This is a selection framework, not a measured ranking. A sorted list can be perfectly adequate for a modest prefix dictionary, especially when updates are infrequent. A trie can make prefix traversal natural while spending substantial memory on nodes or child representations. Measure the actual implementation and corpus.
Do not describe a trie of whole keys as automatically supporting arbitrary substring search. A prefix walk starts at the key’s beginning. Adding every suffix changes both the represented problem and the storage budget.
For suffix arrays, locating a candidate range and reporting all occurrences are distinct work. A query that matches nearly every position cannot return every answer in constant time. Include the cost of comparing patterns and materializing results when discussing complexity.
For document search, string containment may not match reader intent. Token boundaries, spelling, stemming, synonyms, ranking, and permissions can matter more than raw substring speed. Choose the information-retrieval contract before selecting its low-level index.
Define Unicode semantics before returning positions
A visible character can be represented by more than one code-point sequence. A user-facing selection can also span multiple code points. State whether an offset counts bytes, code points, UTF-16 code units, or grapheme clusters; those units are not interchangeable.
Normalize consistently at indexing and query time if the product requires canonical-equivalent text to match. Decide whether compatibility distinctions should be preserved. Compatibility normalization can intentionally collapse forms that a domain may need to distinguish, so do not apply it as a universal cleanup step.
Case folding can change length. In the example, an offset into the transformed string cannot be directly applied to the original text to highlight a character. A production highlighting feature needs a mapping or another alignment strategy that preserves the required source positions.
Record the normalization and Unicode-data policy with the index. A runtime upgrade can change available character data or matching behavior. Rebuild or compatibility testing may be needed when the persisted representation and query processor no longer use the same assumptions.
Specify empty-pattern behavior and overlap explicitly. Returning every boundary for an empty pattern can be mathematically reasonable but undesirable in an application. Similarly, advancing by pattern length gives nonoverlapping matches, while advancing one transformed position can include overlaps.
Compare performance without hiding the workload
Build a representative fixture with text lengths, pattern lengths, alphabet characteristics, repetition, expected match counts, and update frequency. Include absent and common matches. Repeated text can stress algorithms differently from random text.
Measure construction time and peak memory separately from steady-state queries. An index that wins a microbenchmark may be unsuitable when the corpus changes every few seconds or the process cannot afford its memory footprint.
Include the actual result contract: first occurrence, count, all positions, top completions, or ranked documents. Comparing an operation returning one position with one returning every match is not a fair workload comparison.
Check correctness against a simple trusted implementation on bounded cases before measuring speed. Add Unicode variants and boundary cases selected from the intended audience’s data. Keep the test corpus approved and free of unnecessary personal content.
Start with the simplest implementation that meets the requirement. Adopt a more elaborate index when measured query load, latency, or scale justifies its construction and maintenance costs. Revisit that choice when the query shape or update rate changes.
Best Practices
Write the matching policy down
Specify representation, case, normalization, overlap, and offset units beside the API. Test the same policy in indexing, queries, and presentation.
Count the whole lifecycle
Compare build, storage, update, lookup, and output costs. Treat implementation constants and corpus shape as measured inputs.
Preserve a correctness oracle
Use a simple bounded reference method for regression tests. An optimized index should return the same defined answers before its speed matters.
Common Mistakes
Bad: All suffix indexes answer substrings in the same time.
Correct: Name the specific structure, construction algorithm, comparison cost, and output requirement.
Bad: Normalized offsets point into the original string.
Correct: Preserve or compute the mapping needed for original-text highlighting.
Bad: Case-insensitive means language-aware.
Correct: Define the intended folding or collation semantics and test the relevant languages.
FAQ
When is built-in find enough?
When its semantics and measured cost meet the workload. Avoid an index whose maintenance exceeds the benefit of repeated queries.
Is a trie always smaller than a map?
No universal storage claim follows from the name. Child layout, alphabet, shared prefixes, compression, and runtime object overhead matter.
Can the example highlight original text?
No. It deliberately returns transformed-string offsets and does not retain an alignment map.
Related Topics
- Data Structures — Representation and time/memory tradeoffs.
- Trees — Tree structure and traversal foundations.
- Regular Expressions — Pattern matching beyond literal substrings.