How Do You Index Text for Regex Search?

How does a trigram index work?

Split each document into every overlapping run of three characters and store a posting list for each trigram. The string alan turing produces nine grams.

["ala", "lan", "an ", "n t", " tu", "tur", "uri", "rin", "ing"]

Any document that contains alan turing must contain all nine grams, so intersecting their posting lists gives a candidate set. Russ Cox described the same approach for Google Code Search, and it has the property that keeps the whole scheme safe, which is that it cannot produce false negatives.

Why are trigrams a compromise?

Short grams are common. A trigram such as the or ing occurs in a large fraction of any corpus, so its posting list is expensive to read and removes almost nothing. Trigrams also lose adjacency past three characters, so a document can contain every trigram from a query in unrelated places and still become a candidate.

Longer fixed grams are more selective, but they create a different problem. An index over one width cannot help with required fragments shorter than that width, and indexing every width repeats the same text at each width, so the index grows with the maximum width. Sparse grams resolve the tension between the two.

What do sparse grams change?

Sparse-gram tokenization assigns a deterministic weight to every bigram, and TopK uses CRC32 for the weight. It then selects an n-gram only when its two boundary bigrams outweigh every bigram inside it. The rule depends only on the contents of the span, so if a query string occurs inside a document, every gram selected from the query is also selected from the same interval in the document. Text before or after the match cannot change the decision.

The selection probability for a span of n characters is 2 / ((n-1)(n-2)), so every trigram is selected and longer grams appear less and less often. The expected gram count telescopes to about 2L for a document of length L, compared with order LN for a dense index over every width up to N. The difference is what lets the index admit long, selective terms without paying for every long interval. The derivation is in the fast regex search post.

How does a regex become a boolean expression?

The planner parses the regex into the same representation the exact matcher uses. It then tracks what it can prove about every possible match, which includes required literal runs, required prefixes and suffixes, and whether a subexpression can match the empty string. Concatenation combines constraints with AND, alternation combines them with OR, and a wildcard contributes nothing. For colou?r of the (sky|sea), a conservative plan looks like the following.

" the" AND "r of t" AND ("e se" OR "e sk")

The plan states only facts that every match must satisfy. A document that fails the plan cannot match and gets skipped, and a document that passes is a candidate. Because the guarantee only goes one way, the planner can drop a weak gram or cap a large alternation whenever that is cheaper. Each of those choices admits more candidates and never loses a true match. Patterns made mostly of wildcards fall back to a scan, and the fallback is safe for the same reason.

What decides which grams the planner uses?

Information decides it, not length. The usefulness of a gram is I(g) = -log2 P(g), so rare grams filter well and common grams do not, and two grams of the same length can have very different posting lists. A familiar phrase stays common even when it is long, and an unusual name becomes selective after a few characters. The planner therefore prefers the terms with the lowest measured document frequency, whatever their length. Raising the maximum gram length adds only about 2L / (N(N-1)) terms per step under the sparse model, so it stays cheap and still helps.

TopK ships the index behind its ordinary regex filter, so field("message").regexp_match(pattern) plans through sparse grams automatically. The design and its measurements are in the fast regex search post (August 2026), and the interactive gram explorer in the post shows which grams a given string produces.