Two clerks, one filing cabinet

Imagine two clerks sharing a cabinet. The first files a card under café. The second receives a request that looks identical on the page, walks to the café drawer, and finds nothing.

The first card used the single code point é. The request used e followed by a combining acute accent. Human perception supplied equality that the cabinet never encoded.

A search engine has these two clerks:

• the index analyzer turns source records into dictionary keys and postings;
• the query analyzer turns a request into keys to look up.

Their governing law is agreement. For one pinned analyzer contract $A$ and one input text $x$,

$$A_{\mathrm{index}}(x) = A_{\mathrm{query}}(x).$$

The equality covers the ordered token keys and all options that affect them. The two sides may receive different kinds of records—an authored heading at index time and a query box at request time—but the shared text function cannot quietly drift.

Name the whole function

Writing lowercase(split(text)) hides every consequential choice. A useful analyzer accepts source records, not an unmarked string, and emits token records, not bare words.

Let a source record be

$$r = (\text{text},\text{field},\text{origin},\text{span},\text{confidence}).$$

Let an emitted token be

$$t = (\text{key},\text{field},\text{origin},\text{span},\text{position}, \text{confidence},\text{analyzer-id}).$$

The key supports equality and lookup. The remaining coordinates preserve why that key exists. A title token and an inferred caption token may spell the same word and still be different evidence.

A contract must pin at least:

1. accepted input encoding and malformed-input behavior;
2. source extraction and field rules;
3. Unicode normalization form;
4. segmentation rules and any tailoring;
5. case mapping or folding rule;
6. language-specific stemming or lemmatization policy;
7. retained positions and source spans;
8. stopword and punctuation policy;
9. deterministic output order;
10. an analyzer identifier that changes when any prior item changes.

The identifier is not decoration. The index artifact records it. A query engine that cannot supply the same contract rejects the artifact or selects a compatible analyzer explicitly. Silent fallback converts a detectable version mismatch into unexplained misses.

The stages do different jobs

The pipeline is easier to reason about when each stage has one meaning.

A complete reference analyzer

The following algorithm separates structural extraction from the shared key function. Its helper operations are not implementation defaults: each is named by the contract and covered by fixtures.

ANALYZE(records, contract)
Input:  ordered source records carrying text, field, origin, span, confidence
        a contract naming decode, normalize, segment, fold, stem, and filters
Output: ordered token records, or a typed analysis error

if contract identifier is unknown
    return UNKNOWN-CONTRACT
tokens ← empty sequence
position ← 0
for each record r in records
    decoded ← contract.DECODE(r.text)
    if decoded is an error
        return decoded
    normalized ← contract.NORMALIZE(decoded)
    pieces ← contract.SEGMENT(normalized)
    for each piece p in pieces from left to right
        if not contract.ACCEPTS(p)
            continue
        folded ← contract.FOLD(p.text)
        renormalized ← contract.NORMALIZE(folded)
        key ← contract.STEM(renormalized, contract.language)
        if key is empty
            continue
        source-span ← MAP-SPAN(r.span, p.span)
        token ← TOKEN(key, r.field, r.origin, source-span, position, r.confidence, contract.identifier)
        tokens.APPEND(token)
        position ← position + 1
return tokens

The second normalization is explicit because the selected fold or tailoring may emit a sequence outside the chosen normal form. A contract backed by a single standardized combined operation can implement the same interface with one call; its observable token stream, not its number of internal passes, is the promise.

The algorithm stops on malformed input instead of silently substituting a key. Another contract could replace malformed subsequences, but then the replacement rule becomes part of key identity. Either policy is reproducible. An implicit runtime default is not.

The loop is linear in the number of decoded code points plus the work of its declared transforms. That asymptotic statement is intentionally modest. Dictionary-driven segmentation, language analysis, and span mapping can have large constants. The artifact should measure their bytes, allocations, and latency on the scripts and fields it actually admits.

Agreement needs a witness

An analyzer identifier is useful only if it identifies behavior. A robust artifact includes a compact conformance corpus with rows such as:

Run the same rows through the index path and query path, then compare canonical token bytes. Testing each implementation only against itself is too weak: two different functions can each be internally deterministic.

A migration needs three analyzer versions at once:

• the version recorded by the old index;
• the version used to build the candidate index;
• the version selected for each query during comparison.

Shadowing the candidate on a pinned query corpus exposes gains and losses before activation. Rebuilding the index is usually the honest migration. A query-time compatibility trick that emits keys for both versions can bridge a small transition, but it broadens retrieval, complicates scoring, and needs an explicit removal condition.

Equality is not ordering

Normalization and case folding help define key equality. They do not define a human-language sort order. Collation can depend on locale, punctuation policy, numeric substrings, and strength. A search artifact therefore separates:

• canonical key bytes for deterministic identity and reproducible lookup;
• semantic enumeration order promised by the interface;
• display collation chosen for a particular reader and locale.

Using locale-sensitive collation as persistent identity is dangerous because implementations and locale data can change. Using canonical byte order as a claim about how names should appear to every reader is equally dishonest. The dictionary chapter's multiple-view lesson applies again: one identity can have separate, explicit orders.

Provenance survives every transformation

Each analyzer stage changes a view of the text. None may launder its origin. If OCR proposes a token from pixels, normalization does not turn that token into authored prose. If speech recognition attaches a time interval and confidence, stemming does not erase either. If a heading extractor points to a source span, a later snippet generator can return to that span rather than inventing context around a normalized key.

Span mapping becomes difficult when a transform changes length. The safe model is not to pretend every output code point has one input offset. Preserve a covering source interval for the token, and retain the original source for display. More precise many-to-many maps are useful when highlighting demands them, but they are additional data with their own bounds and tests.

Eligibility can depend on provenance before ranking begins. A system may admit authored metadata for one query mode and exclude inferred captions below a confidence threshold. Encoding the origin as a tiny relevance bonus would let ineligible evidence participate and perhaps leak. A later chapter will derive that boundary as a set operation.

The historical lesson is reproducibility

Where agreement is not enough

Two machines can agree perfectly on a bad function.

• Compatibility normalization can collapse a distinction the domain needs.
• An English stemmer can damage names or text in another language.
• A segmentation rule tuned for prose can make source-code identifiers hard to find.
• A field extractor can consistently index boilerplate or private text.
• A stable analyzer can preserve a discriminatory or historically accidental naming convention.

Agreement is a necessary reproducibility law, not proof of relevance, fairness, authorization, or linguistic truth. Those properties need separate evidence.

The analyzer can also be more expensive than the retrieval it enables. For a tiny static corpus, an exact substring scan may be simpler and more faithful. For a field of opaque identifiers, normalization and stemming may be actively wrong. The interface should permit the identity analyzer when identity is the right relation.

Lessons

• Indexing and querying are two machines that must share one versioned analyzer contract.
• Extraction, normalization, segmentation, case folding, stemming, and collation answer different questions.
• Normalization and stemming can be non-injective, so normalized keys cannot replace original source text.
• Equal keys establish a lookup relation; they do not erase field, origin, source span, or confidence.
• Analyzer agreement is proven with shared conformance rows and canonical token bytes, not matching implementation names.
• Changing any key-affecting rule changes the artifact contract and normally requires rebuilding the index.
• A shared analyzer can still be wrong for the domain. Reproducibility is necessary, not sufficient.

Practice

Agreement gives us sorted evidence

The two machines now produce the same key for the same declared relation. A lookup can therefore return its postings without wondering whether the miss was created by preprocessing drift.

But a multi-term query still faces several sorted lists. Must it inspect every document identifier in all of them? The next chapter puts one finger on each list and derives exactly when whole regions can be skipped.

References

1. Carroll. “Through the Looking-Glass.” Project Gutenberg, 1871. — primary text for the epigraph in the Humpty Dumpty dialogue
2. Unicode Consortium. “Unicode Standard Annex #15: Unicode Normalization Forms.” Unicode Consortium, revision 57. — normative definitions, stability policy, and conformance for normalization
3. Unicode Consortium. “Unicode Standard Annex #29: Unicode Text Segmentation.” Unicode Consortium, revision 47. — normative default grapheme, word, and sentence boundary algorithms and tailoring
4. Porter. “An algorithm for suffix stripping.” Program, 1980. — original published English suffix-stripping algorithm
5. Porter. “The Porter Stemming Algorithm.” Martin Porter, author-maintained page. — author-maintained history, reference implementations, and algorithm variants
6. Manning, Raghavan, Schütze. “Tokenization.” Introduction to Information Retrieval, 2008. — retrieval-oriented treatment of tokenization decisions