Unicode-Aware Document Search System

Search Semantics and System Architecture

A search system must define text equality before choosing an index. This design decodes input as strict UTF-8, preserves the original text for display, and indexes a separate NFC-normalized representation. Case-insensitive queries use NFC plus full Unicode casefold() in a distinct index because folding can change length. Exact and prefix queries operate on normalized code points; grapheme clusters are display units, and returned half-open spans are mapped back to the original document before highlighting.

The service supports exact substring, prefix, tagged multi-pattern, approximate, and constrained regular-expression queries. Immutable segments provide compact high-throughput search, while recent writes enter a dynamic delta. A planner chooses compatible indexes, unions candidates from visible segments, verifies probabilistic or approximate candidates, maps offsets to original text, and removes stale document versions.

flowchart TD
    I["Documents and updates"] --> N["Strict decode, normalize, tokenize"]
    N --> S["Immutable segments and dynamic delta"]
    Q["Typed query and text contract"] --> P["Query planner"]
    P --> S
    S --> V["Verify, map offsets, rank, deduplicate"]
    V --> R["Results with original-text spans"]

Index Portfolio and Query Planning

No single structure efficiently supports every query and update pattern. The planner first resolves normalization, case, tokenization, distance, and overlap semantics. It then selects an index that returns exact answers or a candidate superset. Hashes, q-grams, and BK-trees require exact verification whenever their guarantees do not establish the requested match directly.

Mutable data favors radix tries, small rebuilt Aho-Corasick automatons, n-gram postings, and direct scans. Sealed segments use positional indexes, suffix arrays, or FM-indexes. Every segment records its normalization profile, Unicode-data version, tokenizer version, and index parameters so incompatible results cannot be combined.

Static and Incremental Data Paths

Each update receives a monotonically increasing document version. Original bytes, decoded text, normalized text, offset map, and searchable fields are committed together before becoming visible. Deletions create tombstones so older copies in immutable segments cannot reappear.

When a delta reaches a measured age or size threshold, it is frozen and converted into an immutable segment. The builder validates the new indexes against naive oracles before atomically publishing a new segment manifest. Compaction merges live versions, removes tombstones, rebuilds compressed indexes, and swaps one generation pointer; readers retain their pinned generation until completion.

Result Location and Highlighting

Normalization is not position preserving: a decomposed base-plus-mark sequence may compose into one code point, while case folding may expand one code point into several. Ingestion therefore stores a monotone mapping from each normalized position to the original half-open span that produced it. Overlapping mapped matches are merged before markup is generated, preventing duplicate or nested highlights.

The educational implementation below groups a starter with following combining marks, applies NFC, maps each output code point to the whole source group, and safely escapes untrusted text. Production grapheme segmentation should use a Unicode Standard Annex #29 implementation with a pinned Unicode-data version.

from __future__ import annotations

from dataclasses import dataclass
import html
import unicodedata


@dataclass(frozen=True)
class NormalizedDocument:
    original: str
    normalized: str
    source_spans: tuple[tuple[int, int], ...]


@dataclass(frozen=True)
class Match:
    normalized_start: int
    normalized_end: int


def canonical_clusters(text: str) -> list[tuple[int, int]]:
    clusters: list[tuple[int, int]] = []
    start = 0
    for i in range(1, len(text)):
        if unicodedata.combining(text[i]) == 0:
            clusters.append((start, i))
            start = i
    if text:
        clusters.append((start, len(text)))
    return clusters


def normalize_with_offsets(
    text: str,
    *,
    case_insensitive: bool = False,
) -> NormalizedDocument:
    pieces: list[str] = []
    spans: list[tuple[int, int]] = []
    for start, end in canonical_clusters(text):
        piece = text[start:end]
        if case_insensitive:
            piece = piece.casefold()
        piece = unicodedata.normalize("NFC", piece)
        pieces.append(piece)
        spans.extend([(start, end)] * len(piece))
    return NormalizedDocument(text, "".join(pieces), tuple(spans))


def map_span(doc: NormalizedDocument, start: int, end: int) -> tuple[int, int]:
    if not (0 <= start < end <= len(doc.normalized)):
        raise ValueError("match must be a non-empty normalized span")
    return doc.source_spans[start][0], doc.source_spans[end - 1][1]


def merge_spans(spans: list[tuple[int, int]]) -> list[tuple[int, int]]:
    merged: list[list[int]] = []
    for start, end in sorted(spans):
        if start >= end:
            continue
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return [(start, end) for start, end in merged]


def highlight(doc: NormalizedDocument, matches: list[Match]) -> tuple[list[tuple[int, int]], str]:
    spans = merge_spans([
        map_span(doc, match.normalized_start, match.normalized_end)
        for match in matches
    ])
    output: list[str] = []
    cursor = 0
    for start, end in spans:
        output.append(html.escape(doc.original[cursor:start]))
        output.append("<mark>")
        output.append(html.escape(doc.original[start:end]))
        output.append("</mark>")
        cursor = end
    output.append(html.escape(doc.original[cursor:]))
    return spans, "".join(output)


def exact_matches(text: str, query: str) -> tuple[NormalizedDocument, list[Match]]:
    doc = normalize_with_offsets(text)
    needle = unicodedata.normalize("NFC", query)
    matches: list[Match] = []
    if not needle:
        return doc, matches
    start = 0
    while True:
        start = doc.normalized.find(needle, start)
        if start < 0:
            return doc, matches
        matches.append(Match(start, start + len(needle)))
        start += 1


if __name__ == "__main__":
    doc, matches = exact_matches("Cafe\u0301 and café; <safe>", "café")
    spans, rendered = highlight(doc, matches)
    assert doc.normalized == "Café and café; <safe>"
    assert spans == [(10, 14)]
    assert rendered == "Cafe\u0301 and <mark>café</mark>; &lt;safe&gt;"

    folded = normalize_with_offsets("Straße", case_insensitive=True)
    assert folded.normalized == "strasse"
    assert map_span(folded, 4, 6) == (4, 5)
    print(rendered)

Correctness, Security, and Adversarial Testing

Correctness starts with exhaustive tiny corpora checked against naive algorithms. Property, differential, fuzz, and metamorphic suites vary empty inputs, overlaps, normalization forms, combining marks, supplementary characters, malformed encodings, replacements, deletions, and compaction. Canonically equivalent inputs must yield equivalent normalized matches while mapping to their own original spans.

Malformed bytes are rejected or handled by an explicitly named replacement policy before indexing. Hash candidates are verified unless an API explicitly offers quantified probabilistic results. User regexes run in a supported regular subset under an automata engine, or under strict time, memory, and input limits. Repetitive text, match storms, adversarial hash keys, and pathological edit queries exercise backpressure and resource caps.

Benchmarking and Design Defense

Evaluation separates correctness, retrieval quality, latency, throughput, memory, update cost, and output volume. Exact tests report p50, p95, and p99 latency for present and absent patterns across natural, random, multilingual, and repetitive inputs. Approximate search reports candidate count, verification time, recall, and false positives by threshold. Static-index experiments vary rank checkpoints and suffix-array sampling; update experiments measure acknowledgement, visibility, recovery, compaction amplification, and query latency during publication.

Every run records the corpus digest, Unicode and tokenizer versions, hardware, warm-up policy, cache state, segment layout, parameters, and confidence intervals. A threshold is accepted only when it satisfies a stated objective on representative and adversarial workloads.