tobogganSe connecter

packages

The Louise packages, each released on its own

Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.

NomDernier commitDate
bench/Packages: search's bench and READMEil y a 3 sem.
src/Packages: search/fm, an FM-index over a text or corpusil y a 3 sem.
test/Packages: search/fm, an FM-index over a text or corpusil y a 3 sem.
CHANGELOG.mdA repository of its own: README, CI, release checks, fixturesil y a 4 j
louise.tomlVersion every package 0.21.0, on louise 0.22.0il y a 4 j
README.mdPackages: search's bench and READMEil y a 3 sem.
README.MD

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; search answers the ids of the documents containing a query.
  • search/fm: an FM-index over one text (or a corpus of documents); count/locate/extract answer 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/remove touch one document's trigrams each; bulk changes are faster as a fresh build.

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.