Capstone: Quarry's Text Index
In short: one text_index function routes each query to whichever
linear-time tool fits it best — KMP for an exact phrase, a rolling hash's
fingerprint set for many same-length phrases at once, and two Z-arrays
(forwards and backwards) for a query that allows one typo. None of the tools
is faster than the others; what differs is what each one remembers between
characters: a border, a fingerprint, or a matched box.
Three lessons have given Quarry three linear-time ways to look at text. This one
puts them behind a single function, text_index, that takes a set of documents
and a batch of queries and returns every place each query occurs. A query may
also ask for one typo of slack. By the end, the piece you build is the one a
user actually types into.
Picking the tool
Each technique answers a slightly different question, and the index uses each one where it fits best:
| question | best tool | why |
|---|---|---|
| where does this one phrase occur? | KMP (or Z) | exact, worst-case O(n + m), no false alarms |
| does this phrase occur in a live stream? | KMP | the only state is j, so the text is read once |
| which of many same-length phrases occur? | rolling hash | one pass, and a set lookup per window covers every phrase |
| which passages repeat across documents? | rolling hash | fingerprint every window, group by fingerprint |
| where does it occur with at most one typo? | Z, forwards and backwards | front match plus back match covers all but one character |
None of them is "the fast one". They are all linear. What differs is what they remember: a fingerprint, a border, or a box of known matches.
The contract
text_index(docs, queries):
docsmaps a document id to its text, for example{"n1": "Disk full on node7"}.queriesis a list of strings. A query starting with~means "the rest, allowing one substituted character".- Matching ignores case: compare
text.lower()withquery.lower(). - The result maps each query, exactly as given, to a list of
[doc_id, start]pairs, ordered by document id and then by position. Overlapping matches count. An empty query, or a bare~, maps to[].
Positions refer to the lowercased text. For plain ASCII that is the same as the original. Case handling is less simple than it looks:
print("STRASSE".lower() == "Straße".lower(), "STRASSE".casefold() == "Straße".casefold())Exact queries
Build the failure function once per query, not once per document, then run
the same matcher over every document. With Q queries and documents totalling
N characters, exact search costs O(Q · N + total query length), and each
query makes at most 2N character comparisons however repetitive the text is.
Here is the matcher over one document, with a running count of character
comparisons. Swap in a naive matcher, or a text full of near-misses like
"disk fuldisk fuldisk full", and compare the counters:
Your matcher over one document, one character per frame. The highlighted run is how much of the query is matched so far, and the comparison count never exceeds twice the document's length.
A common shortcut gets overlapping matches wrong:
The contract counts overlapping matches, so "aa" occurs in "aaaa" at 0, 1 and 2. This prints [0, 2].
One-typo queries
The Z lesson's capstone idea becomes a query type. For each window, count how many
characters match from the front (a Z-array of query + [None] + text) and how
many match from the back (a Z-array of the reversed query against the reversed
text). If the two together cover at least m − 1 characters, at most one
character is wrong.
The only fiddly part is indexing into the reversed text. A window that starts at
i ends at i + m − 1, and in the reversed text that character sits at
n − 1 − (i + m − 1):
Here is ~disk against the text disk dusk, with pre and suf for each start:
The front match and the back match are read straight off two Z-arrays. When they cover all but one character, the window is a one-typo hit, and nothing inside it is compared again.
At start 0 the front match covers all four characters, so this is an exact hit. 9 cells. i at index 0. Comparing d, i, s and k.
pre = 4, suf = 4
def z(s):
n = len(s)
out = [0] * n
if n:
out[0] = n
l = r = 0
for i in range(1, n):
if i < r:
out[i] = min(r - i, out[i - l])
while i + out[i] < n and s[out[i]] == s[i + out[i]]:
out[i] += 1
if i + out[i] > r:
l, r = i, i + out[i]
return out
q, t = "disk", "dusk"
front = z(list(q) + [None] + list(t))[len(q) + 1]
back = z(list(q[::-1]) + [None] + list(t[::-1]))[len(q) + 1]
print(front, back, front + back >= len(q) - 1)Putting it together
The finished function is short, because each piece is a function you already have. Lowercase every document once, and for each query choose the matcher:
The one-typo branch plugs in the same way, with two Z-arrays per document. Every query is linear in the text it scans, and the whole batch is O(Q · N) plus the query lengths.
An interview question: redact many secrets in one pass
A message must have every occurrence of any banned token replaced by *. All the
tokens have the same length k, and there may be thousands of them. Running KMP
once per token costs O(tokens · n). One rolling hash, with a dict from fingerprint
to the tokens that have it, checks every window against all of them at once:
The expected cost is O(n + total token length), plus O(k) for each real hit. That is the rolling hash's niche: many patterns of one length.
What it costs
| operation | cost |
|---|---|
| lowercase all documents | O(N), once per batch |
| one exact query | O(m) for π, then O(N) over all documents |
one ~ query |
O(N + D · m) for D documents: two Z-arrays per document |
| shared passages of length k | O(N) expected, rolling hash plus a dict |
| a batch of Q queries | O(Q · N) plus the total query length |
Scanning every document for every query is the honest limit of this section. A production engine goes further and indexes the documents once, for example by sorting all their suffixes, so that each query costs roughly the query's length times a logarithm rather than a full scan. That is a different structure, built from the same ideas: borders, fingerprints and prefix matches.
Idioms & real-world patterns
- Preprocess the query once, reuse it for every document. That applies to π, the reversed query and the fingerprint alike.
- Normalise once. Lowercase every document when it's loaded, not inside the query loop.
- Sentinels over separators.
list(q) + [None] + list(t)can't collide with any real character. - Sort ids, then walk positions in order. Deterministic output is what makes a search engine testable.
- Where this lives: log search in operations tools, "find in files" in editors, and spam and secret scanners that check thousands of fixed tokens in one pass.
Quick practice
def z(s):
n = len(s)
out = [0] * n
if n:
out[0] = n
l = r = 0
for i in range(1, n):
if i < r:
out[i] = min(r - i, out[i - l])
while i + out[i] < n and s[out[i]] == s[i + out[i]]:
out[i] += 1
if i + out[i] > r:
l, r = i, i + out[i]
return out
q, t = "full", "fall"
front = z(list(q) + [None] + list(t))[len(q) + 1]
back = z(list(q[::-1]) + [None] + list(t[::-1]))[len(q) + 1]
print(front, back, front + back >= len(q) - 1)"dusk" differs from "disk" by exactly one character, so this should be True. It prints False, rejecting the boundary case the contract is supposed to accept.
🎯 Your turn
Build text_index(docs, queries), Quarry's text index:
docsmaps a document id to its text, andqueriesis a list of strings.- A plain query finds exact occurrences. A query starting with
~finds windows that differ from the rest of the query in at most one character. - Matching is case-insensitive (use
.lower()on both sides), and overlaps count. - Return a dict mapping each query, as given, to its
[doc_id, start]pairs, sorted by document id and then by position. An empty query or a bare~maps to[].
For example, text_index({"n1": "Disk full", "n2": "dusk"}, ["disk", "~disk"]) →
{"disk": [["n1", 0]], "~disk": [["n1", 0], ["n2", 0]]}.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.