git:20260712.a489a6c to git:20260712.77789c7

---

name: full-text-search

description: "Full-text search and IRI/label prefix completion via sparq-text: build TextIndex or CompletionIndex and run text: magic predicates inside SPARQL. Use for keyword/prefix/phrase/proximity or opt-in typo-tolerant search, relevance ranking, or entity autocomplete in a sparq Graph."

---

# sparq full-text search (sparq-text)

`sparq-text` is an **opt-in, separate crate** that adds full-text search over the string literals of a sparq `Graph`. It gives you two surfaces: a low-level owned BM25 inverted index (`TextIndex`) keyed by dictionary term id, and `text:` **magic predicates** that you write inside ordinary SPARQL and that `query_text` rewrites into inline `VALUES` over the index's hits. The engine, planner, and the **lean** `sparq-wasm` bundle carry zero text-search code — full-text support exists only when you depend on `sparq-text` (or load its dedicated tier-b `sparq-text-wasm` browser bundle; see below).

## Quickstart

`Cargo.toml`:

```toml

[dependencies]

sparq-core = { path = "../sparq-core" }

sparq-text = { path = "../sparq-text" } # default features: ["engine", "parallel"]

```

```rust

use sparq_core::Graph;

use sparq_text::{query_text, TextIndex};

let g = Graph::load_str(r#"

<http://ex/post1> <http://ex/title> "The quick brown fox" .

<http://ex/post2> <http://ex/title> "Fox hunting banned" .

"#, "ntriples").unwrap();

// 1. Library-level: build the BM25 index (one dict scan), search returns Hit { id, score }.

let index = TextIndex::build(&g);

for hit in index.search("quick fox") { // AND of tokens, BM25 best-first

let literal = g.dict.term(hit.id); // hit.id IS the dict id of the literal

println!("{literal} (bm25 {})", hit.score);

}

// 2. SPARQL-level: text: magic predicates, rewritten + executed by the engine.

let r = query_text(&g, r#"

PREFIX text: <http://sparq.dev/text#>

SELECT ?post ?s WHERE {

?post <http://ex/title> ?title .

?title text:matches "fox" .

?title text:score ?s .

} ORDER BY DESC(?s)"#, &index).unwrap();

assert_eq!(r.rows.len(), 2); // r.rows: Vec<Vec<Option<oxrdf::Term>>>, r.vars

```

The dictionary term id of a string literal **is** its document id, so search results join back to subjects/predicates through the store's ordinary permutation indexes — that join is what the SPARQL surrounding the magic pattern does.

## Key APIs

Index (always available, `index` module — re-exported at crate root as `TextIndex`, `Hit`):

- `TextIndex::build(graph: &Graph) -> TextIndex` — cheap 8-B-per-posting index, **no positions** (rayon-sharded under `parallel`; result identical to serial).

- `TextIndex::build_with_positions(graph: &Graph) -> TextIndex` — also records token offsets, enabling `phrase`.

- `TextIndex::with_positions() -> TextIndex` — empty position-enabled index for the delta-fed case (positional counterpart of `TextIndex::default()`).

- **CJK n-gram analyzer (opt-in).** [OPUS-4.8] sq-m3ln The default analyzer splits an unspaced Han run per ideograph, so a multi-char CJK term searches as the (low-precision) AND of its characters. `TextIndex::build_with_analyzer(graph, Analyzer::CjkNgram)` (and `build_with_positions_analyzer` / `with_analyzer` / `with_positions_analyzer` for the positional and delta-fed cases) instead indexes each maximal Han run as its **overlapping character bigrams** (`東京都` → `東京`,`京都`), so `text:matches "東京"` (or `search("東京")`) matches only docs where that pair co-occurs. The index **records its analyzer** (`index.analyzer() -> Analyzer`), so `search`/`phrase`/`apply_delta`/`reconcile`/the `text:` rewrite all tokenize the query the same way. Non-CJK text is byte-for-byte the default analyzer (so a Latin corpus is unchanged); kana/Hangul are not bigrammed (UAX #29 already groups them). Trade-off: a single-ideograph query only matches docs where that char is an *isolated* run — hence opt-in. No new dependencies.

- `TextIndex::search(&self, query: &str) -> Vec<Hit>` — AND of tokens (`*`-suffix = prefix token), BM25-ranked best-first.

- `TextIndex::search_any(&self, query: &str) -> Vec<Hit>` — OR of tokens; scores sum over tokens present.

- With `features = ["fuzzy"]`: `TextIndex::fuzzy(&self, term: &str, max_distance: u8) -> Result<Vec<FuzzyHit>, FuzzyError>` — exactly one analyzed query token; distance must be `0..=2`. A bounded deletion-neighbour index supplies candidates (no full token-dictionary scan), exact Unicode-scalar Levenshtein verifies them, and results order by `(distance asc, BM25 desc, matched term asc, id asc)`. `max_distance = 0` has exactly the `search(term)` hit set and scores. `FuzzyHit { id, distance, score, term }`; defaults/constants are `DEFAULT_MAX_DISTANCE = 1` and `MAX_DISTANCE = 2`. [GPT-5.6] sq-lsp7k.14

- `TextIndex::phrase(&self, query: &str) -> Vec<Id>` — adjacent-and-in-order tokens, ascending ids (unranked). **Panics** if the index has no positions.

- `TextIndex::phrase_near(&self, query: &str, slop: u32) -> Vec<Hit>` — proximity/slop: in-order tokens within a bounded total gap, **relevance-ranked** best-first (`score = 1/(1+gap)`, so adjacency = 1.0). `phrase_near(q, 0)` == `phrase(q)` (each at score 1.0); the hit set grows monotonically with `slop`; order stays significant. Same positions requirement / panic as `phrase`. [OPUS-4.8]

- `TextIndex::apply_delta(&mut self, graph: &Graph, inserts: &[[Term;3]], deletes: &[[Term;3]])` — mirror a `Graph::apply_delta` batch (inserts of new string literals are indexed; deletes are a documented no-op).

- `TextIndex::reconcile(&mut self, graph: &Graph) -> usize` — the **rebuild-on-boot + reconcile** warm fast-path: bring a warm index current with a grown graph in `O(new terms)` by scanning only the dictionary tail appended since the last build/reconcile/delta (the batch-free counterpart of `apply_delta`); returns the number of newly indexed docs, and afterwards `index == TextIndex::build(graph)`. Preserves the positions mode. **Panics** if `needs_rebuild` holds. [OPUS-4.8] sq-oddt

- `TextIndex::indexed_dict_len(&self) -> usize` — generation marker: the graph `dict.len()` the index has indexed up to. `is_consistent_with(&graph) -> bool` — cheap staleness check (has it seen every term the graph now holds?). `needs_rebuild(&graph) -> bool` — flags the one unrepairable case: a **shorter** dictionary (a reopened, durably-recompacted base), mandating a fresh `build`. [OPUS-4.8] sq-oddt

- `TextIndex::has_positions(&self) -> bool`, `len()`, `is_empty()`, `token_count()`, `heap_bytes()`.

- `struct Hit { pub id: sparq_core::dict::Id, pub score: f32 }` (`score` comparable within one query only).

Completion (always available, `complete` module — re-exported at crate root):

- `CompletionIndex::build(&graph)` indexes every IRI under its full IRI and local name,

plus literal values attached through `rdfs:label` or `skos:prefLabel`.

- `CompletionIndex::apply_delta(&mut self, graph, inserts, deletes)` mirrors newly interned IRIs and inserted `rdfs:label`/`skos:prefLabel` triples after `Graph::apply_delta`; deletes are a documented no-op. `reconcile(&graph)` scans the appended dictionary tail plus label triples involving a new subject or object, while `is_consistent_with` / `needs_rebuild` expose the same append-only staleness contract as `TextIndex`. Label triples added solely between pre-existing terms must be forwarded through `apply_delta`.

- `complete(prefix, k, scores)` returns case-insensitive prefix matches ordered by

descending injected entity score, then key and id. Pass `None` for lexical ordering.

- Results are `Candidate { id, key, kind, score }`; label candidates carry the subject

entity id, and `CandidateKind::Label(predicate_id)` records their predicate.

- Matching is prefix-only; fuzzy completion is intentionally outside this index.

SPARQL rewrite (`engine` feature, default on — `rewrite` module):

- `query_text(graph: &Graph, sparql: &str, index: &TextIndex) -> Result<QueryResult, String>` — parse, rewrite `text:` patterns, evaluate.

- `query_text_with_budget(graph, sparql, index, budget: &sparq_engine::QueryBudget) -> Result<QueryResult, String>`.

- `prepare_text(graph, sparql, index) -> Result<sparq_engine::PreparedQuery, String>` — rewrite only; compose with `sparq_engine::ask_prepared` / `construct_prepared` / `query_prepared`.

- `rewrite_query(query: spargebra::Query, graph, index) -> Result<spargebra::Query, String>` — algebra-level rewrite; queries without `text:` patterns pass through unchanged.

Magic predicates (`sparq_text::vocab`, namespace `http://sparq.dev/text#`):

- `?lit text:matches "q"` — `?lit` ranges over literals containing **every** token of `q` (token ending in `*` = prefix).

- `?lit text:matchesAny "q"` — literals containing **at least one** token.

- With `fuzzy`: `?lit text:fuzzy "term"` — typo-tolerant single-token match, default edit distance one; add `?lit text:maxDistance N` on the same subject for `N` in `0..=2`. It is BM25-scored and accepts `text:score ?s`. [GPT-5.6]

- `?lit text:phrase "foo bar"` — literals where the tokens are **adjacent and in order** (needs a positions-enabled index).

- `?lit text:near "foo bar"` — proximity/slop generalisation of `text:phrase`: tokens **in order within a bounded gap**, **relevance-ranked**. Needs positions. Gap budget defaults to 0 (== `text:phrase`); set it with a `text:slop N` companion. Takes an optional `text:score ?s` (the proximity score). [OPUS-4.8]

- `?lit text:slop N` — sets the proximity gap budget for the `text:near` on the same subject variable in the same BGP (a non-negative integer; at most one; valid only beside a `text:near`). [OPUS-4.8]

- `?lit text:score ?s` — binds the relevance score as `xsd:double`: the BM25 score for a `text:matches`/`text:matchesAny`, or the proximity score (`1/(1+gap)`) for a `text:near`. Must accompany exactly one such scored match on the same subject variable in the same BGP. **Not** valid with `text:phrase` (boolean adjacency, unscored). [OPUS-4.8]

## Common recipes

**Prefix / autocomplete search.** A trailing `*` on a query token matches as a prefix (scored as one pseudo-term):

```rust

let hits = index.search("auto*"); // matches "autonomous", "automatic", ...

// In SPARQL: ?title text:matchesAny "fox auto*"

```

**Typo-tolerant search (default-OFF `fuzzy` feature).** Enable the feature explicitly; ordinary builds contain no fuzzy index or query code:

```toml

sparq-text = { path = "../sparq-text", features = ["fuzzy"] }

```

```rust

let hits = index.fuzzy("quixkly", 1)?; // matches the indexed token "quickly"

// In SPARQL:

// ?title text:fuzzy "quixkly" .

// ?title text:maxDistance 1 .

// ?title text:score ?s .

```

**Relevance-ranked SPARQL results.** `VALUES` rows carry no order through joins — always sort on a `text:score` variable:

```rust

let r = query_text(&g, r#"

PREFIX text: <http://sparq.dev/text#>

SELECT ?post ?s WHERE {

?post <http://ex/title> ?title .

?title text:matches "brown fox" .

?title text:score ?s .

} ORDER BY DESC(?s)"#, &index)?;

// row[1] is an xsd:double literal; rows are unordered until ORDER BY.

```

**Phrase (adjacency) search.** Build the position-enabled index first; order is significant (`"foo bar"` != `"bar foo"`):

```rust

let pidx = TextIndex::build_with_positions(&g);

let ids = pidx.phrase("quick brown fox"); // literal ids, ascending

// In SPARQL (requires pidx, not the default build):

// ?title text:phrase "quick brown"

```

**Proximity / slop search (ranked near-phrases).** `text:near` is the scored, bounded-gap variant of `text:phrase` over the same positional index — tokens still in order, but allowed a total gap up to the slop, ranked tightest-first (`score = 1/(1+gap)`):

```rust

let hits = pidx.phrase_near("quick fox", 2); // Vec<Hit>, best-first; "quick lazy fox" (gap 1) before "quick the lazy fox" (gap 2)

// In SPARQL — text:slop sets the gap budget, text:score binds the proximity score:

// ?title text:near "quick fox" .

// ?title text:slop 2 .

// ?title text:score ?s .

// ... ORDER BY DESC(?s)

// phrase_near(q, 0) == phrase(q); a larger slop only ever admits more docs.

```

**Incremental upkeep after updates.** Mirror the same batch you fed to the graph:

```rust

g.apply_delta(&inserts, &deletes)?; // inserts/deletes: &[[Term;3]]

index.apply_delta(&g, &inserts, &deletes); // new string literals indexed; deletes no-op

```

**Compose with ASK / CONSTRUCT via prepared queries.** Hits are frozen at rewrite time:

```rust

let prepared = prepare_text(&g,

r#"PREFIX text: <http://sparq.dev/text#>

ASK { ?p <http://ex/title> ?t . ?t text:matches "milestones" }"#, &index)?;

let yes = sparq_engine::ask_prepared(&g, &prepared)?;

```

**Pure index, no engine (e.g. lighter dep graph).** Disable default features and use `TextIndex` + `search`/`search_any`/`phrase` directly:

```toml

sparq-text = { path = "../sparq-text", default-features = false } # or default-features = false, features = ["parallel"]

```

## Gotchas / feature flags / prerequisites

- **Fuzzy constraints.** `TextIndex::fuzzy` and `text:fuzzy` accept exactly one analyzed token (not a phrase or prefix expression); `max_distance`/`text:maxDistance` must be `0..=2`. Each result is admitted iff exact Levenshtein distance is within the bound. When one literal contains several admitted tokens, its best `(distance, -BM25, term)` candidate wins, so each literal appears once. [GPT-5.6]

- **In-browser ("W-text") bundle.** `crates/sparq-text-wasm` ([OPUS-4.8] sq-jbe6) compiles the `engine`-on `sparq-text` (BM25 index + `text:` rewrite + `sparq-engine`) to `wasm32-unknown-unknown` as a SEPARATE, lazy-loaded bundle (NOT in the lean `sparq-wasm` bundle), for the showcase site's `/surface/full-text` page. It exposes a stateless one-shot `TextSearch`: `query(data, format, sparql)` (parse → build a **positions-enabled** index → rewrite + run the `text:` query → SPARQL-1.1-JSON) and `indexStats(data, format)` (a `{docs,tokens,heapBytes,hasPositions}` footprint — the index-build memory is the bundle's risk, so keep the corpus small). `parallel` is off (no wasm threads); the tokenizer's `unicode-segmentation` is pure-Rust and wasm-portable. Build with `wasm-pack build crates/sparq-text-wasm --target web --release`.

- **What gets indexed.** Only plain/`xsd:string` and language-tagged literals from the graph's dictionary. Typed literals (numbers, dates, `geo:wktLiteral`, ...) are skipped.

- **Per-graph indexes.** Dictionary ids are local to each graph. Named graphs have their own dictionaries — build one `TextIndex` per graph you want searchable, and pass the matching index to `query_text`. Hits come from the index you pass (typically the default graph's).

- **`text:phrase` / `text:near` need positions.** Running either against the cheap `TextIndex::build` index is a **hard query error** ("text:phrase/text:near requires a positions-enabled index; build it with TextIndex::build_with_positions"), not a silent empty result. The bare `TextIndex::phrase(...)` / `phrase_near(...)` methods **panic** in the same situation — guard with `has_positions()` if unsure.

- **Proximity scoring is `1/(1+gap)`.** The `text:near` / `phrase_near` score is a closed form of the document's *tightest* in-order gap (`gap = (last − first) − (n − 1)`): 1.0 for an adjacent occurrence, decreasing monotonically as the best occurrence loosens; ties break by ascending id (the `search` ordering). `slop 0` is exact adjacency (== `text:phrase`), and the hit set is monotonic in slop. Order is significant — no slop makes a reversed phrase match. [OPUS-4.8]

- **Rewrite constraints (each a hard error).** Match/phrase/near subject must be a variable; the query string must be a **constant** literal (no per-row bind-time values); `text:score`'s object must be a variable and must bind exactly one scored match (`text:matches`/`text:matchesAny`/`text:near`, **not** `text:phrase`) on its subject in the same BGP; `text:slop`'s object must be a constant non-negative integer, valid only alongside a `text:near` on the same subject (at most one per near); any unknown IRI under `http://sparq.dev/text#` is rejected (typo guard). A query whose tokens match nothing yields zero rows (empty `VALUES`), not an error.

- **Tokenizer semantics.** UAX #29 Unicode word segmentation + full Unicode lowercasing. No stemming, no stopword list, **no diacritic folding** (`café` != `cafe`). Numbers are tokens. Under the default `Analyzer::Unicode`, an unspaced Han run splits **per ideograph** (`東京都` → `東`,`京`,`都`), so a multi-char CJK term matches as the AND of its characters (use `text:phrase` for adjacency) — opt into `Analyzer::CjkNgram` for character-bigram indexing when that low precision matters (see the CJK n-gram bullet above). [OPUS-4.8] sq-m3ln

- **BM25 scoring.** k1 = 1.2, b = 0.75, idf with the +1 floor. `Hit.score` (and the `text:score` `xsd:double`) is only comparable within a single query. A `*`-prefix token scores as one pseudo-term (its expansions' postings unioned). A wide prefix (e.g. a 4-char prefix matching a third of the corpus) is the dominant cost case — real autocomplete prefixes touch far fewer expansions.

- **Differential BM25 oracle (sparq EXTENSION ratchet — NOT conformance).** [OPUS-4.8] sq-ripcg `crates/sparq-text/tests/bm25_oracle.rs` recomputes the exact BM25 score of every `search`/`search_any` hit with a **from-scratch independent reference scorer** (its own inverted view of the tokenized corpus) and asserts the index reproduces it **bit-for-bit** (`f32::to_bits`) AND in best-first order, over a fixed-seed corpus battery; it pins `TEXT_ORACLE_FLOOR` (the measured count of score-exact assertions, may only RISE). It is wired into the central conformance scoreboard (`sparq-conformance` `scoreboard::SUITES`, the `text-search differential oracle` row, family `sparq extension`) and gated by the `text-oracle` CI job. This is HONESTLY an extension self-consistency ratchet, **not a standards-conformance claim** — there is no normative full-text-over-RDF / BM25 recommendation or test suite. The scoreboard tallies it separately from the standards-conformance total, and the dev-only conformance crate takes **no dependency edge** on `sparq-text` (the floor is mirrored + guarded textually). This complements the sibling `tests/oracle.rs`, which checks AND/OR/phrase hit SETS but deliberately not BM25 scores.

- **Deletes + compaction.** `apply_delta` deletions are intentionally a no-op: the dictionary keeps terms, so the incremental index stays exactly equal to a rebuild and orphaned literal ids simply join to zero triples. In-process `Graph::compact` folds the fork structure but **keeps every dictionary id** (it copies records `1..=len` into a fresh frozen base — no renumbering), so an index stays valid across it; `index.reconcile(&graph)` is then a no-op and `needs_rebuild` returns `false`.

- **Durability / sharing — rebuild-on-boot + reconcile contract.** [OPUS-4.8] sq-oddt `TextIndex` has **no on-disk format** and is per-process (not shareable); the durable `Graph` (its WAL/blob) is the source of truth. Under a stateless-core invariant: **boot** rebuilds with `TextIndex::build` over the freshly opened graph (the index is a pure function of the dictionary); a **warm** index kept across updates is brought current by `index.reconcile(&graph)` (`O(new terms)`; the batch-free counterpart of `apply_delta`), after which it equals a fresh `build`. `indexed_dict_len()` / `is_consistent_with(&graph)` are the cheap staleness signals; `needs_rebuild(&graph)` flags the only case `reconcile` cannot repair — a **shorter** dictionary, which arises when a stateless core reopens a *durably*-recompacted base whose persisted store dropped orphaned terms and renumbered ids (so the index's dense id→document mapping no longer lines up; `reconcile` panics there — call `build`).

- **Hits frozen at rewrite time.** `prepare_text`/`rewrite_query` snapshot the index's hits into `VALUES`. Re-prepare after the graph (and index) change.

## See also

- `sparq-vectors` — semantic / approximate-nearest-neighbour (HNSW) search, the sibling opt-in crate for embedding similarity rather than lexical match.

- `sparq-geo` — the same opt-in-separate-crate + `apply_delta` index shape, for spatial predicates.

- `fused-decompress-parse` / `rust-parallel-parsing` — fast ingest into the `Graph` you then index.