Query Parser

Project 8/10 of the beacon-search-engine ecosystem — Query Service category. Repository: github.com/juanmmm21/query-parser-autocomplete

The entry point of the query pipeline: turns a raw string a user types into a search box into a structured, normalized query with operator support (exact phrases, exclusions, basic filters), corrects likely typos against the real vocabulary of the crawled index, and serves ranked, sub-100ms autocomplete suggestions as the user types — the layer that stands between "a text box" and "a search engine that understands what you meant."

What problem it solves

A real search box is not LIKE '%query%'. Users misspell terms, want an exact phrase honored literally, want to exclude a term, want to scope a search to a site or file type, and expect suggestions to appear before they finish typing. None of that is something bm25-ranking-engine should have to know about — it expects a clean, already-structured query. This project is the layer that absorbs that messiness: a hand-written recursive-descent style scanner parses operators without ever throwing on malformed input, a length-bucketed bounded edit-distance search corrects likely typos against the index's actual vocabulary (never a generic dictionary), and two prefix tries — one over frequent whole queries, one over vocabulary terms — serve ranked completions fast enough for interactive typing.

Role in beacon-search-engine

inverted-index-builder
        │ postings.jsonl (term -> document_frequency)
        ▼
┌─────────────────────────────────────────────────┐
│            query-parser-autocomplete              │   (this project)
│  parse (operators) + spellcheck + autocomplete     │
└───────────────────┬───────────────────┬───────────┘
                     │                   │
                     │ ParsedQuery       │ Suggestion[]
                     ▼                   ▼
          bm25-ranking-engine    beacon-search-console
                                  (live suggestions)

query-parser-autocomplete sits upstream of the whole ranking pipeline: it reads the on-disk vocabulary of inverted-index-builder (for spellcheck and term-level autocomplete, using the exact same Unicode/casefold normalization that project applies when tokenizing, so corrected and completed terms actually match the index's vocabulary), and produces the structured ParsedQuery that bm25-ranking-engine consumes, plus the ranked suggestion list beacon-search-console shows live. It never imports either project's Python package — integration is always through the on-disk format each documents, per beacon-search-engine's polyrepo contract. It does not depend on pagerank-link-analysis or learning-to-rank-reranker at all: those sit further downstream in the ranking pipeline, past the point this project's output enters it.

Goal and skills demonstrated

• A hand-written query grammar that never crashes on malformed input: quotes that are never closed, a dangling field:, a - followed by a space — every one of these degrades to the simplest reasonable interpretation (see query_parser.py's docstring) instead of raising, the same "never fail the whole pipeline on one bad input" principle ../CLAUDE.md (section 2.D) applies to malformed HTML, applied here to malformed query text.
• Bounded-cost spellcheck at real vocabulary scale: spellcheck.py never runs edit distance against the whole vocabulary — it buckets terms by length (a term more than max_distance characters longer or shorter than the query term can never be within max_distance edits of it) so each correction only touches a small neighborhood of candidates, and edit_distance.py's DP aborts a row early once its minimum already exceeds the bound, both hand-written from scratch (no python-Levenshtein, no spellcheck library — ../AGENTS.md).
• A prefix trie built for the latency budget it has to meet: descending a prefix is O(len(prefix)), and collecting matches only walks the subtree under that prefix, never the full vocabulary — see Latency below for a measured number, not just an asymptotic claim.
• A clearly documented synthetic data source, not a hidden one: v1 has no real search traffic yet (beacon-search-console doesn't exist until project 10/10), so query_log.py's synthetic query log generator is documented in full — Zipf-shaped rank-based frequencies, deterministic under a fixed seed — exactly the same transparency principle learning-to-rank-reranker's synthetic training set follows.
• Train/serve-style consistency treated as a correctness concern: this project reimplements inverted-index-builder's exact tokenization algorithm (NFC normalization, casefold(), the same token-boundary regex) independently, not approximately — a spellcheck correction or an autocomplete match is worthless if it doesn't actually exist as a term in the real index.

How it works

1. Parsing the grammar (query_parser.py): a hand-written character scanner walks the raw query once, recognizing exact phrases ("..."), term exclusion (-term), and basic filters (field:value, including field:"quoted value") — deliberately not a single giant regex, so that malformed input degrades predictably instead of failing to match at all. This step never touches the index: it only understands grammar, not spelling.
2. Normalizing (normalization.py): every free term and phrase term is tokenized with the exact algorithm inverted-index-builder uses to build the index (NFC normalization, Unicode-aware letter/digit runs, casefold() — never lower(), which does not fold characters like the German ß); filter values are normalized as a whole string instead (site:example.com must stay example.com, not split into ["example", "com"]).
3. Reading the real vocabulary (index_reader.py): an independent, minimal reader of inverted-index-builder's uncompressed manifest.json + postings.jsonl format — only term and document_frequency are needed here, so documents.jsonl and stats.json are never even parsed. A compressed index-compression-codec index is rejected with a clear error, same convention as learning-to-rank-reranker.
4. Spellchecking (spellcheck.py, edit_distance.py): each free query term not already in the vocabulary is corrected against the closest vocabulary term within a bounded edit distance (2 by default), searched only within a length-bucketed neighborhood — never a brute-force scan of the whole vocabulary. Terms inside an exact phrase or an exclusion are never corrected: quoting or excluding a term is the user asking for it literally.
5. Autocomplete (trie.py, query_log.py, autocomplete.py): two prefix tries — one over frequent whole queries (real completions like "python tuto" → "python tutorial for beginners"), one over vocabulary terms (completes only the word currently being typed, e.g. "search engi" → "search engine", even when the log has no matching query) — are merged by suggestion text, keeping the maximum score on a collision, and ranked by score descending with an alphabetical tie-break for determinism.
6. Orchestration (pipeline.py, __main__.py): parse_and_correct_query combines steps 1–4; build_autocomplete_index/suggest combine steps 3, 5. Both accept the protocols.TermCorrector/PrefixSuggester interfaces, so tests exercise pipeline logic with in-memory doubles without rebuilding a real index each time.

Architecture

src/query_parser_autocomplete/
├── models.py            # ParsedQuery, Filter, QueryCorrection, VocabularyTerm, ...
├── protocols.py          # TermCorrector / PrefixSuggester interfaces
├── normalization.py        # NFC + casefold tokenizer, matching inverted-index-builder
├── edit_distance.py          # bounded, early-exit Levenshtein distance
├── index_reader.py             # independent reader of the index vocabulary
├── query_parser.py               # hand-written scanner: phrases, exclusions, filters
├── spellcheck.py                   # length-bucketed bounded-distance correction
├── trie.py                           # prefix trie, weighted by frequency
├── query_log.py                        # query log IO + documented synthetic generator
├── autocomplete.py                       # merges query-trie + term-trie suggestions
├── pipeline.py                             # parse_and_correct_query(), suggest()
└── __main__.py                               # CLI (`parse`, `suggest`, `generate-query-log`)

Requirements and installation

• Python >=3.11
• Zero runtime dependencies — spellcheck (edit distance) and autocomplete (trie) are implemented from scratch, per ../AGENTS.md.

git clone https://github.com/juanmmm21/query-parser-autocomplete.git
cd query-parser-autocomplete
python3 -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]"

Usage (CLI)

# Parse a query with combined operators against a real index, with spellcheck
query-parser-autocomplete parse ./index \
  '"exact phrase" pyhton -deprecated site:example.com'

# Same, without spellcheck, writing the result to a file for bm25-ranking-engine
query-parser-autocomplete parse ./index "python tutorial" \
  --no-spellcheck --output ./parsed-query.json

# Autocomplete suggestions for a prefix, against a real query log
query-parser-autocomplete suggest ./index "python tuto" \
  --query-log ./query_log.jsonl --limit 5

# Materialize a synthetic query log once, to reuse across `suggest` calls
query-parser-autocomplete generate-query-log ./index ./query_log.jsonl \
  --num-queries 500 --seed 42

Try it end-to-end against the tiny fixture checked into samples/tiny_example/ (a 5-document index and a hand-picked query log):

query-parser-autocomplete parse samples/tiny_example/index \
  'pyhton tutorial -javascrpt site:example.com'
query-parser-autocomplete suggest samples/tiny_example/index "python tuto" \
  --query-log samples/tiny_example/query_log.jsonl

It can also be invoked as a module: python -m query_parser_autocomplete parse ....

Data formats

Input — index vocabulary: the uncompressed manifest.json + postings.jsonl produced by inverted-index-builder (only term and document_frequency are read from each posting line). A compressed index-compression-codec index is rejected explicitly.

Input — query log (query_log.py), one JSON object per line:

{"query": "python tutorial", "frequency": 120}

Real production traffic would populate this once beacon-search-console exists; until then, generate-query-log materializes a documented synthetic one from the index's own vocabulary.

Output — parsed query, the contract bm25-ranking-engine consumes (ParsedQuery.to_json_dict):

{
  "required_terms": ["python", "tutorial"],
  "phrases": [["exact", "phrase"]],
  "excluded_terms": ["deprecated"],
  "filters": [{"field": "site", "value": "example.com"}],
  "corrections": [{"original": "pyhton", "corrected": "python"}]
}

Output — suggestions, the contract beacon-search-console consumes (Suggestion.to_json_dict), printed by the CLI as rank. text (score=...):

{"text": "python tutorial for beginners", "score": 45}

Programmatic usage

from pathlib import Path

from query_parser_autocomplete import pipeline

# Parsing + spellcheck
corrector = pipeline.build_spell_checker(Path("./index"))
parsed = pipeline.parse_and_correct_query(
    '"exact phrase" pyhton -deprecated site:example.com', corrector
)
print(parsed.required_terms, parsed.corrections)

# Autocomplete
autocomplete_index = pipeline.build_autocomplete_index(
    Path("./index"), Path("./query_log.jsonl")
)
suggestions = pipeline.suggest("python tuto", autocomplete_index, limit=5)
for suggestion in suggestions:
    print(suggestion.text, suggestion.score)

Development

pytest
ruff check .
ruff format --check .
mypy --strict src/

Tests cover the domain models (JSON round-trips, validation), normalization (NFC/casefold parity with inverted-index-builder's exact algorithm, including composed vs. decomposed Unicode input), bounded edit distance (hand-computable cases, boundary conditions on the distance cap), the independent index-vocabulary reader (round-trips and malformed-input errors against small on-disk fixtures), the query parser grammar (ambiguous, misspelled, and combined-operator queries, plus every malformed-input degradation path — unterminated quotes, a dangling field:, - followed by whitespace), spellcheck (deterministic tie-break by frequency then alphabetically, length-bucket pruning), the trie and autocomplete index (ranking order, deduplication across the two suggestion sources, and a timed benchmark against a 20,000-term/5,000-query synthetic fixture asserting sub-100ms latency), the synthetic query log generator (determinism under a fixed seed), and the pipeline/CLI end to end using in-memory TermCorrector/PrefixSuggester test doubles where the intent is testing this project's own orchestration, not spellcheck or autocomplete logic already covered elsewhere.

Latency

Autocomplete must be sub-100ms for interactive typing to feel responsive. AutocompleteIndex.suggest is not a scan: descending a prefix through the trie is O(len(prefix)) (one dict lookup per character), and collecting matches only walks the subtree rooted at that prefix, never the full set of indexed queries or terms — a specific, narrow prefix has an inherently small subtree almost by construction. tests/test_autocomplete.py measures this directly against a synthetic fixture of 20,000 vocabulary terms and 5,000 query-log entries (larger than any real corpus this ecosystem currently indexes) and asserts the average call stays well under 100ms; on the development machine used to build this project it measures well under 1ms per call (~0.16ms average over 100 calls). Building the two tries from scratch — the one operation that is linear in corpus size, ~27ms for that same fixture — happens once per process, in build_autocomplete_index, never per keystroke.

Troubleshooting

• ValueError: ... es un índice comprimido de index-compression-codec: this project only reads the uncompressed inverted-index-builder format — decompress with index-compression-codec first.
• parse returns a filter you didn't intend, e.g. a bare word containing a colon like 9:00 becomes {"field": "9", "value": "00"}: v1's filter grammar treats any alnum_or_underscore:value bare word as a filter, with no restriction to a known operator set (site, filetype, ...) — wrap it in quotes ("9:00") to force it to be parsed as a literal phrase instead.
• A misspelled term inside a quoted phrase or after - is never corrected: this is intentional, not a bug — see How it works, step 4.
• suggest for an empty prefix returns the most frequent whole queries: also intentional — a reasonable "trending searches" default before the user has typed anything, rather than an empty result.
• Spellcheck returns None (no correction) for an obviously misspelled term: the closest vocabulary term is farther than max_distance (2 by default) edits away — either raise max_distance when constructing SpellChecker, or the term genuinely isn't in the index's vocabulary at all (e.g. it was never crawled).

License

MIT — see LICENSE.