full-text-search

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:

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

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, TermStats):

• 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.
• TextIndex::term_stats(&self, token: &str) -> Option<TermStats> — exact per-token corpus statistics using the index's analyzer: document frequency (doc_count), total term frequency (total_tf), and the same BM25 inverse document frequency (idf) used by search scoring. Returns None for absent tokens and input that does not analyze to exactly one token; it does not expand prefixes. [GPT-5.6] sq-rviwn
• 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(), total_postings(), heap_bytes(). len() counts indexed literal documents, token_count() counts distinct tokens, and total_postings() counts (token, document) posting pairs. [GPT-5.6] sq-ukr2k
• struct Hit { pub id: sparq_core::dict::Id, pub score: f32 } (score comparable within one query only).

Highlighting (default-OFF highlight feature — re-exported at crate root as snippet, Snippet):

• snippet(text: &str, query_token: &str, context_chars: usize) -> Option<Snippet> — after resolving a hit id to its literal lexical form, find every occurrence of one default-analyzer token and render a word-trimmed contiguous window with <mark> / </mark> around each occurrence. Matching is case-insensitive; Snippet.spans contains absolute half-open UTF-8 byte ranges into the complete text. Empty text, a query that is not exactly one token, and no match return None. [GPT-5.6] sq-lsp7k.19

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):

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:

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

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 .

Highlight a resolved hit (default-OFF highlight feature). The hit carries only a dictionary id and score, so pass the literal text after resolving the id:

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

use sparq_text::snippet;

let text = "the quick fox jumps";
let excerpt = snippet(text, "fox", 10).expect("matching token");
assert_eq!(excerpt.spans, [(10, 13)]);
assert_eq!(excerpt.rendered, "quick <mark>fox</mark> jumps");

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

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"):

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)):

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:

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:

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:

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

Gotchas / feature flags / prerequisites

• Feature flags. engine (default on) brings in the rewrite module + sparq-engine/spargebra (with NO engine default features) — needed for query_text/prepare_text/rewrite_query and all text: magic predicates. engine-builtins (default on) turns the engine's regex (SPARQL REGEX/REPLACE) + digest (hash builtins) back on, so a text: rewrite over a query that ALSO uses those builtins works. parallel (default on) rayon-shards TextIndex::build and forwards the engine's parallel execution. fuzzy is default-OFF and adds only the bounded deletion-neighbour index/API plus the text:fuzzy/text:maxDistance rewrite arms. highlight is default-OFF and adds only literal snippet extraction; it has no index, engine, or dependency edge. Disable defaults for the bare index (tokenizer + TextIndex + BM25) with no engine in the graph; take features = ["engine"] ONLY for the lean wasm shape (engine present, but no rayon/regex/digest/fuzzy/highlight — what the sparq-text-wasm bundle does). [GPT-5.6] sq-lsp7k.14 sq-lsp7k.19
• 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.