search
Full-text search indexes for a small corpus — a user's notes, say — in pure Louise. Two indexes:
search: a trigram inverted index over documents;searchanswers the ids of the documents containing a query.search/fm: an FM-index over one text (or a corpus of documents);count/locate/extractanswer where a pattern occurs.
import search
let idx = search.build [(1, "Toki Pona notes"), (2, "TODO: plant the toki pona stickers")]
search.search idx "toki" // [1, 2]
search.search idx "PONA" // [1, 2]: case-insensitive
import search/fm
let idx = fm.build "banana"
fm.count idx "ana" // 2 (overlapping counts)
fm.locate idx "ana" // [1, 3]
fm.extract idx 1 3 // "ana"
The trigram index (search)
build :: List<(DocId, String)> -> Index indexes documents by their
ids; search :: Index -> String -> List<DocId> answers the ids of the
documents containing the query, ascending. add (an upsert) and remove
change one document and return a new index, leaving the old one as it was
— keep one index per user and swap it in.
Matching is a substring match on the normalized text (normalize:
lowercase, trimmed). Indexing posts each document's id to the lists of its
distinct trigrams (3-character windows); a query's trigrams intersect
those lists — roaring-style compressed bitmaps, search/bitmap — into
candidates, and each candidate is verified with a real substring test.
The trigrams only narrow the scan: results are exact, with no false
positives.
Queries shorter than three characters have no trigram and scan every
document instead; an empty query matches every document. DocIds are
non-negative Ints you choose; dense small ids compress best.
Memory: the index stores the normalized text of every document (for verification) on top of the postings.
The bitmaps (search/bitmap)
Roaring-style sets of non-negative Ints: containers of 65,536 values
(the low 16 bits) keyed by the high bits, each a sorted list while it
holds at most 4,096 values and a 65,536-bit bitmap (a big Int) past
that. Intersecting two bitmap containers is one int.and; a result that
gets sparse drops back to a list. add, remove, contains,
intersect, to_list, from_list, from_sorted_list (the ids
ascending), size, stats (which containers a set uses).
The FM-index (search/fm)
An FM-index (Ferragina & Manzini): a suffix array of the text plus a
sentinel (built by prefix doubling, O(n log² n)), its Burrows–Wheeler
transform, and occurrence checkpoints every 64 rows, walked by backward
search. count/locate take time proportional to the pattern, not the
text; extract reads any slice back. An empty pattern has no matches.
build_corpus :: List<String> -> Corpus indexes a list of documents as
one text; corpus_count/corpus_locate answer counts and
(document, offset) pairs. Documents and patterns may not contain
U+0000, the document separator (build_corpus panics).
Limits
- Substring matching only: no tokenization, stemming, or ranking.
- Build is O(corpus size): fine for a per-user corpus (notes, messages), not for a document store. The FM-index's O(n log² n) build is the heavier one.
- In the interpreter both builds are slow; use native builds for
anything but tests (
louise test --native,louise run --native). search.add/removetouch one document's trigrams each; bulk changes are faster as a freshbuild.
Bench
bench/ (its own package; louise run --native there) builds a
10,000-note corpus and times the build and 400 queries, and an FM-index
of the first 500 notes. The corpus is seeded, so the hit counts are the
same on every run.
Tests
louise test here, and louise test --native for the native backend.
The property tests (packages/gen) check both indexes against naive
scans of random corpora.