Fast Regex Search

Fast Regex Search — Indexed Text Search for Agent Tools

Purpose

Replace brute-force ripgrep scans with an indexed search pipeline when working in large codebases. This algorithm pre-indexes source files using sparse n-grams so that regex queries hit a posting-list lookup (O(log n) binary search) instead of scanning every file (O(n) linear).

When to use: Any codebase where rg takes >2s. Particularly monorepos, vendor-heavy projects, or codebases with >10k files.

When NOT to use: Small projects (<1k files) where rg completes in <500ms. The overhead of index construction isn't worth it.

Algorithm Overview

The search pipeline has three phases: Index, Query, Verify.

Phase 1: Index (build time)

Build a sparse n-gram inverted index over all source files.

1A. Sparse N-gram Extraction (build_all mode)

For each file, extract variable-length n-grams using a deterministic weight function:

weight(char_pair) = frequency_rank(char_pair)

Where frequency_rank is derived from a character-pair frequency table built from a large corpus of open-source code. Rare pairs get HIGH weight; common pairs get LOW weight.

N-gram boundary rule: An n-gram is any substring where the weights at both endpoints are strictly greater than all weights contained inside.

def build_all_sparse_ngrams(text: str, weight_fn) -> list[tuple[str, int]]:
    """Extract ALL sparse n-grams from text for indexing.

    Returns list of (ngram, position) tuples.
    """
    ngrams = []
    n = len(text)
    if n < 2:
        return ngrams

    # Compute weights for every adjacent character pair
    weights = [weight_fn(text[i], text[i+1]) for i in range(n - 1)]

    # Stack-based extraction: find all substrings where
    # edge weights > all interior weights
    for start in range(n - 1):
        # Walk right from start, extending while interior weights are lower
        max_interior = -1
        for end in range(start + 1, min(start + MAX_NGRAM_LEN, n)):
            if end < n - 1:
                # Check if this could be an endpoint
                if weights[end] > max_interior and weights[end] >= weights[start]:
                    ngrams.append((text[start:end+2], start))
            if end > start:
                max_interior = max(max_interior, weights[end - 1] if end - 1 > start else -1)

    return ngrams

1B. Inverted Index Construction

For each file F in codebase:
    For each (ngram, position) in build_all_sparse_ngrams(F.content):
        hash = fnv1a_64(ngram)
        postings[hash].append(FilePosting(
            file_id = F.id,
            loc_mask = 1 << (position % 8),      # 8-bit position bloom
            next_mask = char_hash(F.content[position + len(ngram)]) if exists  # 8-bit follow-char bloom
        ))

1C. Disk Layout (two files)

Why two files: Only the lookup table is mmap'd into the editor process. Posting lists are read on-demand from disk at the offset found in the lookup table. This keeps resident memory minimal (~2-4 bytes per unique n-gram).

Phase 2: Query (search time)

2A. Sparse N-gram Covering (build_covering mode)

At query time, extract only the MINIMUM set of n-grams needed to cover the search pattern. Because the weight function is deterministic, the covering set is guaranteed to be a subset of what was indexed.

def build_covering_ngrams(pattern: str, weight_fn) -> list[str]:
    """Extract MINIMAL covering n-grams for a query pattern.

    Uses the same weight function as indexing, but only generates
    n-grams at boundary positions — far fewer than build_all.
    """
    ngrams = []
    n = len(pattern)
    if n < 2:
        return ngrams

    weights = [weight_fn(pattern[i], pattern[i+1]) for i in range(n - 1)]

    i = 0
    while i < n - 1:
        # Find the local maximum weight starting from position i
        best_end = i
        for j in range(i + 1, min(i + MAX_NGRAM_LEN, n - 1)):
            if weights[j] >= weights[best_end]:
                best_end = j

        # Extract n-gram from i to best_end + 2
        ngram = pattern[i:best_end + 2]
        if len(ngram) >= 2:
            ngrams.append(ngram)

        # Advance past the covered region
        i = best_end + 1

    return ngrams

2B. Regex Decomposition

For regex patterns (not just literals), decompose into extractable literal segments:

Pattern: /MAX_FILE_SIZE/     → literals: ["MAX_FILE_SIZE"]
Pattern: /foo(bar|baz)/      → literals: ["foo"] + OR(["bar"], ["baz"])
Pattern: /test_\w+\.py/      → literals: ["test_"], [".py"]
Pattern: /[rbc]at/           → OR(["rat"], ["bat"], ["cat"])
Pattern: /\d{3}-\d{4}/      → literals: ["-"]   (character classes break n-gram extraction)

Rule: Extract n-grams only from literal segments. Character classes (., \w, \d, [...]) break n-gram boundaries. Alternations (|) create OR branches where ANY branch matching is sufficient.

2C. Posting List Lookup

For each covering n-gram:
    hash = fnv1a_64(ngram)
    offset = binary_search(mmap'd lookup_table, hash)
    posting_list = read_at_offset(postings_file, offset)

candidate_files = intersect(all posting_lists)  # AND for sequential n-grams
                                                 # OR for alternation branches

2D. Adjacency Filtering (Bloom Masks)

For consecutive n-grams in the query, apply two additional filters before accepting a candidate:

1. nextMask filter: Does the first n-gram's follow-char bloom contain
   the first char of the second n-gram?
   → nextMask(ngram1, file) & char_hash(ngram2[0]) != 0

2. locMask filter: Are the two n-grams actually adjacent in the file?
   → (locMask(ngram1, file) << 1) & locMask(ngram2, file) != 0

Both filters are probabilistic (bloom filters can false-positive) but never false-negative. They dramatically reduce candidate sets for common trigrams.

Phase 3: Verify (match time)

For each candidate_file in candidate_files:
    content = read_file(candidate_file)
    matches = regex_match(pattern, content)  # standard ripgrep/RE2 matching
    yield matches

This is always required. The index only narrows candidates — final matching must be exact.

Weight Function: Character-Pair Frequency Table

The weight function is the critical optimization. Use inverse frequency from a large code corpus:

# Pre-computed from ~2TB of open-source code
# Higher weight = rarer pair = better n-gram boundary
PAIR_FREQUENCY = {
    ('e', ' '): 1,    # very common → low weight
    (' ', 't'): 2,    # very common → low weight
    ('t', 'h'): 3,    # common → low weight
    ...
    ('X', '_'): 847,   # rare → high weight
    ('Q', 'z'): 9241,  # very rare → high weight
}

def weight_fn(c1: str, c2: str) -> int:
    return PAIR_FREQUENCY.get((c1, c2), len(PAIR_FREQUENCY) // 2)

Why frequency-based weighting wins: Rare character pairs become n-gram boundaries, which means the extracted n-grams contain the MOST SPECIFIC substrings. At query time, the covering algorithm produces fewer, longer, more discriminating n-grams — resulting in smaller posting lists and fewer candidates to verify.

Fallback: If no frequency table is available, use crc32(c1 + c2) as a deterministic pseudo-random weight. This still works but produces ~30% more candidates than frequency-based weighting.

Index Lifecycle

Construction Triggers

• First open of a workspace with >5k files
• Background rebuild after git pull / git checkout that changes >100 files

Incremental Updates

• Base index is keyed to a git commit SHA
• Uncommitted changes (dirty files) are stored as a delta layer on top
• Agent writes are immediately reflected in the delta layer (read-your-own-writes)
• On commit, delta merges into base; on checkout, base rebuilds

Staleness Contract

• Index MUST reflect the current working tree within 1s of any file write
• Stale index results in agents chasing phantom code — worse than no index at all

Performance Characteristics

Integration with Agent Search Tools

When this index is available, the search tool pipeline becomes:

Agent calls grep("pattern", path) →
  1. Decompose pattern into covering n-grams
  2. Query index for candidate files
  3. Run ripgrep ONLY on candidate files (not full codebase)
  4. Return matches

This is transparent to the agent — it still calls grep the same way. The index acts as a pre-filter that reduces the search space by 90-99%.

Implementation Notes

• Hash function: FNV-1a 64-bit for n-gram hashing. Fast, well-distributed, no crypto overhead.
• Posting list compression: Delta-encoded file IDs + varint encoding. Typical compression ratio: 3-5x.
• Max n-gram length: Cap at 8 characters. Longer n-grams have diminishing returns and bloat the index.
• Minimum n-gram length: 2 characters (bigrams as floor). Single characters are too broad.
• Bloom filter size: 8 bits for both locMask and nextMask. Saturation becomes a problem above ~40 entries per posting; at that point, the bloom filter matches everything and provides no filtering benefit.

References

• Zobel, Moffat, Sacks-Davis (1993): "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files"
• Russ Cox (2012): "Regular Expression Matching with a Trigram Index" (Google Code Search)
• Nelson Elhage (2015): "Regular Expression Search with Suffix Arrays" (livegrep)
• GitHub Project Blackbird: Trigram + probabilistic bloom masks
• GitHub Code Search / ClickHouse: Sparse n-gram indexing with frequency-weighted boundaries
• Cursor (2026): "Fast regex search: indexing text for agent tools" — local index with mmap'd lookup tables