Usage guide¶

Runnable snippets for every interface, in Python and Rust.

`plan` — which index, before you build one¶

Five indexes with five size curves is a choice nobody should have to make from a README table: the sizes are corpus-specific, and the spread between them on one corpus is larger than the spread of any one of them across corpora. plan sorts the keys once, measures what the formats are actually paid in, and prices every index that answers the questions you say you need answered.

import lexindex

keys = ["apple", "apricot", "banana", "blackberry", "blueberry", "cherry"]

p = lexindex.plan(keys, prefix=True)   # prefix and range queries; nothing else required
print(p["best"]["kind"])               # the cheapest index that answers them
print(p["text"])                       # the whole ladder, and why the winner won

# An index that cannot answer what was asked is left out of the ranking rather than ranked last.
assert {e["kind"] for e in p["estimates"]} == {"DictIndex", "StringIndex"}

Which index wins is a property of your keys and not of this library — six fruit names are not a corpus, and neither is a range of numbers, which an fst folds into almost nothing. Run it on the keys you actually have. The keywords are reverse (key(id) as well as id(key)), ordered, prefix, fuzzy and exact — the last rules out the two probabilistic indexes, which is where their size comes from. Nothing is required by default, so a bare plan(keys) prices all five.

Past 100 000 keys the three numbers no statistic gives — what the codec squeezes a suffix into, the bytes an fst spends a key, the bits the perfect hash spends per key — come from two draws of that size, and each estimate says so in measured. Scored against the built blob on 23 corpora of half a million to ten million keys, at each of the three priced blocks, DictIndex lands within 1.0 % median, 4.2 % at the 90th percentile and 7.2 % at worst; StringIndex within 1.1 / 6.7 / 11.7 over 19 corpora, because an fst merges equal right-languages and how much it merges is a property of the density of the whole key set rather than of any statistic of it. A dense id space is where that still breaks: ten million decimal ids merge to 356 bytes whole, which no draw of a hundred thousand of them can see, and the estimate reads about a hundredfold high — the ranking survives, the byte count does not, and thin says so. Below the sample size nothing is modelled: the candidates are built and reported at what they weigh.

That error is not random in n. Holding a corpus's content fixed and moving only its size — stride samples of one file, so the difference is scale and nothing else — the estimate reads about 2.8 % low at a million keys and converges to within 0.2 % by ten million on urls and article titles. It does not converge on a deep directory tree, where shared prefixes keep lengthening with the key count: a path list reads level at a million and 7.2 % high at seven. The suffix rate is measured on a uniform draw of 100 000 keys, whose neighbours are n / 100 000 apart, so what it reads is a longer suffix than the blob's — plan a large path index expecting the blob to come in under the number, and re-plan on a sample of the real keys if the margin matters.

What a sample cannot see by itself is how good the vocabulary gets. A shard's symbol table and the blob-wide phrase dictionary are trained on the keys the blob holds, and the miner buys a phrase against what it saves over the whole blob — so a hundred thousand keys afford a tenth of the dictionary a million do, and a sample built as an index of its own reads the suffix ratio 0.71 where the million-key blob spends 0.53 on article titles. The sample is therefore built with the corpus's economics: its phrases mined at the corpus's key count, over every suffix it holds, once for the plan and not once a block. That takes a million urls from 14 % high to 0.9 % low and three million article titles from 24 % to 1.4 %.

There are two draws because the blob is paid in two currencies. What a suffix compresses to is a property of the whole key set, so it is read off a uniform draw: a key is kept while its hash is under a cutoff, and the cutoff falls as the draw fills — the same sample on every run over the same keys, needing neither the corpus's size in advance nor the corpus in memory, which is what lets plan_file answer as plan does. It is also the more accurate draw for an fst: a stride over sorted keys takes one key from every prefix group whatever the group's size, and a StringIndex estimate read off such a sample runs 5 % low on a corpus of shared prefixes where this one lands within 0.4 %. But what a stored (lcp, len) pair and a block's arrays cost is a property of the neighbours a key is coded against, which a uniform draw destroys — it read a million decimal ids 0.51 bytes a header where that blob spends 0.34, a third of it. So those come off a second draw, of runs of 4 096 consecutive keys each started by the hash of its first, coded under the same dictionary.

Two flags say when not to trust the ranking. close means the two cheapest are within 1.3× of each other, which is inside what an estimate can separate; thin means the mean suffix is under two bytes, where a compression ratio read from a sample carries least well — ten million decimal numbers are the worst cell in the score, at 4.1 % high. Either one means build both and measure.

plan_file(path, needs, objective) prices a keys file the same way without ever holding it. The file is sorted externally — runs in memory, spilled beside it, merged back — and the merge is where the key count, the mean length and both shared-prefix distances are counted, exactly rather than sampled; only the three unmeasurable constants still come from a sample, and that sample is the hash draw above, which does not depend on the corpus being in hand. So it is not an approximation of plan: on a 925 MB, 7 343 721-line path list the two print the same ladder to the byte, at 0.27 GB of resident memory against 1.30 and in less wall time. The runs go in a directory beside the file and are removed however the call ends, so that directory must be writable.

`StringIndex` — ordered, FST-backed¶

import lexindex

# Duplicates are removed and keys sorted; the id of a key is its rank in sorted order.
idx = lexindex.StringIndex(["banana", "apple", "apricot", "cherry", "apple"])

# Keys already in ascending byte order build without ever being materialised: the constructor
# has to hold the whole corpus to sort it, these consume the iterable lazily. Measured at 10 M
# keys, the streamed build peaks at 11.6 MB against the list build's 1053.4 -- 91x.
keys = (line.rstrip("\n") for line in open("sorted-keys.txt"))   # any lazy iterable
n = lexindex.StringIndex.build_sorted_to_file(keys, "keys.bix")  # -> number of keys written
n = lexindex.StringIndex.build_to_file(unsorted, "keys.bix")     # any order: sorted in runs on disk
idx2 = lexindex.StringIndex.from_sorted(["apple", "apricot", "banana"])  # or straight to memory

len(idx)                 # 4  (duplicate "apple" deduped)
idx.id("apple")          # 0
idx.id("missing")        # None
"cherry" in idx          # True
idx.key(2)               # "banana"  (id → string)

# the dict spelling of the same lookup, on all four classes: KeyError on a miss, or a default
idx["apple"]             # 0
idx.get("missing", -1)   # -1

# ordered iteration — automaton-driven: prefix/range seek directly; a broad fuzzy or
# subsequence pattern may still walk most of the FST
idx.prefix("ap")         # [("apple", 0), ("apricot", 1)]
idx.common_prefix("applesauce")  # [("apple", 0)]  — the keys that are prefixes OF the query
idx.longest_prefix("applesauce") # ("apple", 0)    — what a longest-match tokeniser takes
idx.occurrences("cherry-apple")  # [(0, 6, 3), (7, 12, 0)]  — every key in a text, as (start, end,
                                 # id) in characters: common_prefix at every position, in one call
idx.range("apricot", "cherry")   # [("apricot", 1), ("banana", 2)]  — [lo, hi)
idx.successor("ba")      # ("banana", 2)   — smallest key ≥ query
idx.predecessor("ba")    # ("apricot", 1)  — largest key ≤ query
idx.fuzzy("aple", 1)     # [("apple", 0)]  — Levenshtein edit distance ≤ 1
idx.subsequence("ae")    # [("apple", 0)]  — "a…e" in order, not necessarily contiguous
# "character" above means a Unicode scalar value: no normalisation, case folding or grapheme
# segmentation is applied — normalise before building and querying if you need it

# order statistics — answers about the id space without decoding any key, so the cost does not
# grow with the number of matches
idx.lower_bound("ba")            # 2  — how many keys sort below "ba"; an insertion point in 0..=len
idx.prefix_id_range("ap")        # (0, 2)  — a prefix is a contiguous *slice* of the id space
idx.prefix_count("ap")           # 2
idx.range_count("apricot", "cherry")  # 2  — what range() would return, uncounted

# lazy iteration in sorted (= id) order — streams the transducer a chunk at a time, so it never
# builds a giant list and never decodes a key twice
list(idx)                # [("apple", 0), ("apricot", 1), ("banana", 2), ("cherry", 3)]
dict(idx)                # {"apple": 0, "apricot": 1, "banana": 2, "cherry": 3}

# every query takes a limit: stop after that many matches, walking no further
idx.prefix("ap", limit=1)        # [("apple", 0)]
idx.fuzzy("aple", 1, limit=1)    # [("apple", 0)]

# batched lookups — one Rust↔Python crossing instead of one per key (named ids_of / keys_of so the
# class is never mistaken for a mapping)
idx.ids_of(["banana", "x"])   # [2, None]
idx.keys_of([0, 2])           # ["apple", "banana"]

What `limit` buys — and what it cannot¶

limit is not a faster walk; it is not doing work whose result would be thrown away. Without it, prefix("s") on the 479 823-word system dictionary walks the whole s subtree of the FST and materialises every match — 45 064 (str, int) tuples — even if the caller wanted ten. With it, the walk stops at the tenth match. The saving is therefore proportional to how much of the result you discard, and it varies enormously by query (same dictionary, idle machine, min of 9 runs):

query	matches	full	`limit`	speedup
`prefix("s", limit=10)`	45 064	10.96 ms	0.004 ms	~3 000×
`prefix("a", limit=10)`	25 192	4.83 ms	0.003 ms	~1 500×
`prefix("un", limit=10)`	20 358	4.09 ms	0.006 ms	~700×
`subsequence("abc", limit=10)`	1 910	41.31 ms	0.51 ms	~80×
`fuzzy("hello", 2, limit=5)`	242	1.52 ms	0.26 ms	~6×

Three regimes hide in that column, and they tell you when to reach for limit:

Prefix / range: the walk is cheap, the discarded results were the cost. Speedup tracks matches ÷ limit almost linearly. This is the autocomplete case, and it is why the numbers are in the thousands.
Subsequence: the walk itself is expensive. The .*a.*b.*c.* automaton visits many FST nodes per match produced, so stopping early saves traversal, not just tuples — 80× despite discarding far fewer results than prefix("un").
Fuzzy: a fixed cost dominates that limit cannot skip. The Levenshtein automaton is built eagerly before the walk starts (deliberately, so a too-large distance raises up front rather than on first use). limit only trims the walk after that, hence single-digit gains.

There is also a floor under every query: one call costs ~3 µs of FFI plus stream construction, so per-match cost at limit=1 reads ~2 000 ns against a steady ~200 ns from limit≈100 up. Asking for one match costs about the same as asking for ten — batch your UI accordingly.

If you will consume all matches, limit (or omitting it) changes nothing: the eager form is the lazy walk collected, measured within noise of each other. In Rust, prefer the *_iter forms (prefix_iter / range_iter / fuzzy_iter / subsequence_iter) and .take(n) — same machinery, no intermediate Vec at all.

Persistence and zero-copy loading¶

idx.save("catalog.bix")                            # write a flat, relocatable blob
idx = lexindex.StringIndex.load("catalog.bix")     # read it back into RAM
idx = lexindex.StringIndex.load_mmap("catalog.bix") # …or memory-map it: no read, borrowed zero-copy
idx = lexindex.StringIndex.load_mmap_verified("catalog.bix")  # …mapped, with the payload checksum
idx = lexindex.StringIndex.load_untrusted("theirs.bix")       # a file someone else wrote, see below

data = idx.to_bytes()                              # or go through bytes directly
idx = lexindex.StringIndex.from_bytes(data)

import pickle                                      # every class pickles, including Overlay
idx = pickle.loads(pickle.dumps(idx))              # …so one can be sent to a spawned worker

Pickling copies the blob. An index goes onto the wire as its to_bytes() and comes back through from_bytes, which is what makes it work across a multiprocessing spawn — a path would not survive a worker that cannot see the same filesystem, and a memory-mapped index would not survive the file changing. So a mapped index pickles by value like any other, and a large one costs its serialised size in the pickle: when both ends can see the same file, save plus load_mmap shares the pages instead of copying them.

load_mmap maps the file and borrows the index from the mapped pages, so load time is independent of the index size and the pages are shared across processes. The mapped file must stay immutable while an index borrows it.

The loaders, on two axes — whether the bytes are copied and how far they are checked:

Loader	Copies	Checks	For
`from_bytes` / `load`	yes	header, payload checksum, rank spot check	your own blob
`from_untrusted_bytes` / `load_untrusted`	yes	the above plus the full validation of the transducer (`StringIndex`; the hash indexes and `DictIndex` need none, their loaders are total)	a stranger's blob
`load_mmap`	no	header only — the payload checksum is skipped by design, since reading every page is what a mapping avoids; `DictIndex` skips the walk over its per-block arrays for the same reason and bounds every access instead	your own file, unchanged while mapped
`load_mmap_verified`	no	header and payload checksum, one pass over the mapping at load	your own file, carried by someone else
`load_mmap_untrusted` (`StringIndex`)	no	the full validation, over the mapping	a stranger's file too large to copy — map a copy you own, since the check trusts what it saw once

A truncated or corrupt blob is refused with ValueError, and no load can produce undefined behaviour. StringIndex has one documented exception, and it is the reason SECURITY.md states a threat model rather than a promise: its blob is an fst transducer whose node decoder is safe Rust but not total, and the checksum in front of that decoder is public, so bytes crafted to carry a matching one can panic instead of returning. In Python that surfaces as pyo3_runtime.PanicException, which derives from BaseException and so slips past except ValueError.

idx = lexindex.StringIndex.from_untrusted_bytes(data)          # a blob someone else wrote
ov = lexindex.Overlay.from_untrusted_bytes(data, lexindex.StringIndex)   # …or one wrapping it

That loader checks the transducer as a graph — every reachable node once, in time proportional to nodes and transitions rather than to the keys they spell, so a tiny blob spelling a billion keys is refused or accepted in microseconds — requires its values to be ranks and its keys to be UTF-8, and catches the panic at the load boundary, so a crafted blob raises ValueError like any other bad input. It costs 32× from_bytes (22.9 ms against 0.7 ms on 479 823 words), which is the trade: pay it once for a stranger's blob, never for your own. The overlay form exists for the same reason — an overlay's own framing is checksummed and validated either way, but the base region inside it is handed to a base loader, and over a StringIndex base that is exactly the choice above. The hash indexes need no such call: their loaders are total, so Overlay.from_untrusted_bytes over a hash base does the same work as from_bytes.

One thing neither loader can promise: the contained panic still runs the process-wide hook on its way out, so a rejection normally prints a panic message to stderr before the ValueError arrives.

Before loading a blob, or instead of it, inspect says what it is from its header alone:

info = lexindex.inspect("catalog.bix")       # a path or bytes; only the header and footer are read
info["kind"], info["format"], info["keys"]   # 'StringIndex', 'BIX4', 479823

The dict carries the kind, the format, the key count, and the sizes a caller would otherwise have to load the blob to learn: the perfect hash's region (8 * mph_bytes / keys is its bits per key), the key arena or the fingerprint table, the side table, and for an overlay its additions and retired ids with the base inspected in turn. Nothing is decoded or verified, so an index of gigabytes inspects in microseconds — an overlay excepted, since counting its retired ids reads its tombstone words, one byte per eight ids — and a blob that inspects cleanly may still fail to load. A blob from before 1.0 is a ValueError naming the type to rebuild.

`PerfectHashIndex` — exact lookup with `id → key`¶

from lexindex import PerfectHashIndex

dict_ = PerfectHashIndex(["GET", "POST", "PUT", "DELETE"])
i = dict_.id("POST")           # dense id in [0, n); membership is verified against the stored key
dict_.key(i)                   # "POST"
dict_.id("PATCH")              # None  — a verified miss, not a hash collision
dict_.id_unchecked("GET")      # fastest lookup; skips verification (closed-vocabulary hot path)

dict_.save("verbs.bmp")
dict_ = PerfectHashIndex.load_mmap("verbs.bmp")   # arena mapped zero-copy; tiny MPH read into RAM

# a corpus that does not fit in memory: hand it a factory — it is called twice — never the iterable
n = PerfectHashIndex.build_to_file(lambda: (line.rstrip("\n") for line in open("keys.txt")), "keys.bmp")

# a workload that is mostly misses (a stop list, a block list): one more byte per key, and an
# absent key stops after one cache miss instead of two — 166 → 74 ns on the 480 k-word dictionary,
# a member +3 ns, the same ids. build_to_file takes the same keyword.
stop = PerfectHashIndex(stop_words, fingerprints=True)
stop.has_fingerprints()        # True

Use id_unchecked only for a fixed / closed vocabulary where membership is already guaranteed — it returns an arbitrary (but valid) slot for an unknown key. Use id everywhere else.

`CompactHashIndex` — smallest footprint¶

from lexindex import CompactHashIndex

# fingerprint_bytes ∈ {1, 2, 4}; or a keyword-only fingerprint_bits ∈ 1..=64 for finer control.
# 8 bits (the default) is 1.24 B/key with a ~0.4% membership false-positive
# rate; 2 → ~0.0015%; 4 → effectively exact. No keys are stored, so there is no id → key.
dict_ = CompactHashIndex(["GET", "POST", "PUT", "DELETE"], fingerprint_bytes=1)
i = dict_.id("POST")           # dense id in [0, n); a non-member may rarely read as present
dict_.contains("GET")          # True
dict_.id_unchecked("GET")      # fastest lookup; no fingerprint check (closed-vocabulary hot path)

dict_.save("verbs.bch")
dict_ = CompactHashIndex.load_mmap("verbs.bch")   # fingerprint table mapped zero-copy

# A corpus that does not fit in memory: hashed as it streams, the pairs sorted in runs beside the
# output, the perfect hash built from them a chunk at a time -- the same file `save` writes.
n = CompactHashIndex.build_to_file((line.rstrip() for line in open("keys.txt")), "verbs.bch")

Choosing the fingerprint width¶

Size is the minimal perfect hash (0.24 B/key, flat in n) plus exactly fingerprint_bits/8 bytes per key, and the membership false-positive rate is about 2^-fingerprint_bits — a design rate for well-distributed keys, measured 6.2530 % at 4 bits and 1.5553 % at 6 over 2 M non-member probes; not a defence against an adversary who chooses the queries, since both hashes are deterministic and unseeded — every width is a point on the same trade-off (measured on /usr/share/dict/words, 479 823 keys):

`fingerprint_bits`	bytes/key	false-positive rate	false hits per 1 M non-member probes
4	0.74	6.25%	62 500
6	0.99	1.56%	15 625
8 (= `fingerprint_bytes=1`, default)	1.24	0.39%	3 906
12	1.74	0.024%	244
16 (= `fingerprint_bytes=2`)	2.24	0.0015%	15
32 (= `fingerprint_bytes=4`)	4.24	2.3×10⁻⁸%	~0

Pick by the probe mix, not the key count: the rate is per non-member lookup, so a workload that only ever queries members never sees a false positive at any width, while a filter in front of a network hop wants the rate priced against the cost of a wasted hop. For scale: marisa-trie's exact index costs 2.98 B/key on this corpus — CompactHashIndex is below it at every width up to 21 bits (rate 2⁻²¹ ≈ 5×10⁻⁵%).

tiny = CompactHashIndex(keys, fingerprint_bits=4)   # 0.74 B/key, 1-in-16 false positives
tiny.fingerprint_bits                               # -> 4

CompactHashIndex trades exactness for size: membership is correct except for a 2^-fingerprint_bits false-positive chance on a non-member, and it cannot map an id back to a string. Reach for it when a fixed vocabulary's on-disk / mmap footprint dominates; use PerfectHashIndex when you need exact membership or id → key, or StringIndex when you need order or fuzzy/prefix.

`ClosedHashIndex` — the perfect hash and nothing else¶

from lexindex import ClosedHashIndex

# For a vocabulary known to be closed: every query is a member by construction, so nothing is
# stored to say otherwise. `id` returns a member's id, and for any other string *some* id in
# [0, n) -- there is no `in`, no `[]`, no `contains`. About 0.24 B/key, a fifth of CompactHashIndex.
vocab = ClosedHashIndex(["the", "of", "and", "to"])
i = vocab.id("the")            # the id CompactHashIndex([...]).id_unchecked("the") gives
ids = vocab.ids_of(["to", "of"])   # list[int]; ids_of_bytes / ids_into as on the other indexes
vocab.save("vocab.bcl")
vocab = ClosedHashIndex.load("vocab.bcl")   # no load_mmap: the whole blob is the perfect hash

The same perfect hash as CompactHashIndex over the same keys, so the ids agree with its id_unchecked; what is missing is the fingerprint table, and with it the ability to say no. Reach for it as a token → id map on a hot path where the caller controls the queries — a tokenizer over its own vocabulary, a join on a key column the index was built from — and for CompactHashIndex the moment a stranger can ask.

`DictIndex` — ordered, every key stored, 51 % below `StringIndex`¶

from lexindex import DictIndex

# Exact string <-> rank both ways, about 2.64 B/key: the sorted keys front-coded in blocks of 256,
# each cut into microblocks of 16, with the suffixes under a symbol table trained on the index
# itself. Ordered, so ranges of keys
# are ranges of ids, and prefix and range fall out of that -- only fuzzy needs an automaton and
# stays with StringIndex.
words = DictIndex(["apple", "apricot", "banana", "cherry"])
words.id("banana")                 # 2 -- the sorted rank; None if absent
words.key(2)                       # "banana"
words.prefix("ap")                 # [("apple", 0), ("apricot", 1)] -- a range, not an automaton
words.common_prefix("bananas")     # [("banana", 2)] -- the keys that are prefixes OF the query
words.longest_prefix("bananas")    # ("banana", 2) -- what a longest-match tokeniser takes
words.prefix("ap", limit=1)        # [("apple", 0)] -- stops there, walks no further
lo, hi = words.prefix_id_range("ap")   # (0, 2) -- two order lookups, whatever the match count
words.prefix_count("ap")           # 2, without decoding a key
words.keys_of(range(lo, hi))       # ["apple", "apricot"] -- the keys alone, and the fastest
                                   # way to them: no id is decoded, and one walk stays open
                                   # across a block. 1.5x `prefix` on a 763-match prefix.
words.range("apricot", "cherry")   # [("apricot", 1), ("banana", 2)]
words.successor("az"), words.predecessor("az")   # ("banana", 2), ("apricot", 1)
list(words)                        # [("apple", 0), ...], lazily
faster = DictIndex(words_list, block=64)    # 2.72 B/key against 2.64; id 268–270 ns against 291–298
smaller = DictIndex(words_list, block="compact")  # a name for a point on that curve: "fast" is
                                                  # 32 keys a block, "balanced" 256, "compact" 1024
words.save("words.bdx")
# A corpus that does not fit in memory: sorted in runs spilled beside the output, encoded into the
# file as it goes. Same bytes as the constructor plus save; returns the number of distinct keys.
DictIndex.build_to_file((line.rstrip("\n") for line in open("words.txt")), "words.bdx")
words = DictIndex.load("words.bdx")        # checked like the others
words = DictIndex.load_mmap("words.bdx")   # keys and block data borrowed; header, tables and 8 B/block read
words.route_microblocks()  # opt-in: 0.5 B/key more memory at this block, in no blob, for a faster
                           # search; returns those bytes

id finds the block by its head's first eight bytes, walks the block's restarts to one microblock and compares the stored suffixes there against the query without decoding them; key climbs the same two runs and decodes only the entries whose shared-prefix length strictly increases up to the id, a handful rather than one per entry read. A lookup therefore scans block / micro + micro - 2 entries — 30 at the default, where a block of 256 keys holds 255. On the dictionary: 2.64 bytes per key, id 291–298 ns and key_into 193–194, against 5.95 / 200–210 / 436–445 for StringIndex — which keeps fuzzy and subsequence iteration, and Overlay.

route_microblocks() trades memory for that walk over the restarts. It derives eight bytes of every microblock's first key — 0.5 bytes a key at the default block, 0.25 at 1024, held beside the index and in no blob — and every lookup then picks its microblock off those words, walking the restarts only where the query's eight bytes tie a restart's. Deriving them reads the start of every block, so a load_mmap index is paged in whole by the call rather than as queries reach it. On the dictionary, routed, id reads 217–228 ns at the default block, and 239–241 at block="compact" for 2.76 bytes a key in memory — faster than "fast" unrouted, at fewer bytes.

At block=512 the same index stores 2.52 bytes per key, well under marisa-trie's 2.98 on this corpus, and answers prefix, range and key(id) — a marisa id is not the lexicographic rank, so it has no lower_bound to build a range on. The price is a longer scan: key_into 253 ns against 193–194 at the default, and id 313–328 against 291–298.

`HashedDictIndex` — a `DictIndex` whose `id` is a hash¶

from lexindex import DictIndex, HashedDictIndex

# A DictIndex with a sidecar: at each key's slot in a minimal perfect hash, the key's rank and
# `fingerprint_bits` of a second hash. `id` is one hash and a read of each table -- the dictionary
# is not searched -- and the ordered queries go to `.dict`, whose ids are the same ranks.
words = HashedDictIndex.from_dict(DictIndex(words_list), fingerprint_bits=8)
words.id("banana")                 # its rank; a non-member reads as present at 2^-8
words.id_unchecked("banana")       # a member's rank, and some rank below len() for anything else
"banana" in words                  # id's contract again, as are words["banana"] and words.get(...)
words.ids_of(["apple", "cherry"])  # batched: hashed in one pass, the tables' lines in flight
words.dict.key(2)                  # key, prefix, range, iteration: the dictionary's own
words.save("words.bhd")
words = HashedDictIndex.load("words.bhd")        # checked like the others
words = HashedDictIndex.load_mmap("words.bhd")   # dictionary and rank table borrowed

closed = HashedDictIndex.from_dict(DictIndex(words_list), fingerprint_bits=0)
closed.id_unchecked("banana")      # the smallest sidecar, for a vocabulary the caller controls
closed.id("durian")                # None, always: at zero bits `id` is the dictionary's own search

The membership contract is chosen once, at build. From one fingerprint bit up, id answers a member with its rank and a non-member with None except at 2^-fingerprint_bits — CompactHashIndex's contract. At zero bits id is DictIndex.id, exact and at the dictionary's cost, and the hash path is id_unchecked alone. On the 480 k-word dictionary the sidecar is 2.62 bytes per key at zero bits and one more for every eight fingerprint bits, beside the dictionary's 2.64: 5.25 in all, 6.25 at eight bits. On the frontier protocol — every key looked up once, in a shuffled order — id_unchecked answers in 14 to 78 ns and id at eight bits in 19 to 103 over nineteen corpora of half a million to ten million keys, against 245 to 716 for the dictionary's own id and 54 to 673 for XCDAT, the fastest trie measured (the numbers).

The blob holds the dictionary's own blob byte for byte, so a loaded index answers the ids its dictionary answers. plan does not price it yet, and Overlay does not take it: its ids are ranks, as DictIndex's are.

`DoubleArrayIndex` — a lexicon against running text¶

from lexindex import DoubleArrayIndex, StringIndex

# A character-wise double-array trie: a step is a character, one load each, so the queries that walk
# a text -- the keys it starts with, the longest one, every key anywhere in it -- cost a load a
# character. Duplicates are removed; the ids are the keys' ranks, the same StringIndex gives.
words = ["北京", "北京大学", "大学", "大学生"]
lexicon = DoubleArrayIndex(words)
lexicon.occurrences("北京大学生")  # every (start, end, id) in characters: starts ascending, shortest first
lexicon.common_prefix("大学生活")  # the keys the text starts with, shortest first: [("大学", 2), ...]
lexicon.longest_prefix("大学生活")  # ("大学生", 3), or None
lexicon.id("大学")                 # the key's rank; "大学" in lexicon, lexicon["大学"] and .get(...) too
lexicon.ids_of(["大学", "x"])       # batched
StringIndex(words).key(lexicon.id("大学"))   # nothing comes back out of this one: StringIndex spells an id
lexicon.save("lexicon.bda")
lexicon = DoubleArrayIndex.load("lexicon.bda")        # every slot checked
lexicon = DoubleArrayIndex.load_mmap("lexicon.bda")   # the slots and the code table borrowed

occurrences is what a segmenter asks: jieba builds its DAG from every word starting at each position of a sentence, and one call a sentence returns all of them. The empty key, if it was built in, is a prefix of every query — common_prefix reports it first — but never an occurrence.

It answers these queries and id, and nothing else: no key(id), no prefix, no iteration — keep the key list, or build a StringIndex or DictIndex over the same keys, whose ids are the same. A build is refused past 8 388 608 keys, 65 535 distinct characters or a trie that needs more than 8 388 608 slots: about four million Chinese words, fewer long Latin ones — a million word.word pairs of English take 2.2 M. Every load walks all the slots to check them, load_mmap included, so a crafted file answers wrong ids and never reads out of bounds; load_mmap skips only the checksum over the payload.

`Overlay` — edits without a rebuild¶

Every index is built once from the whole key set, so adding a single key has always meant rebuilding for the whole corpus. An overlay wraps one with the keys added since and the ids retired from it. The base is shared, not copied: it stays usable, and several overlays can sit on one index.

from lexindex import Overlay, PerfectHashIndex

base = PerfectHashIndex.load_mmap("vocab.bmp")   # untouched by anything below
ov = Overlay(base)
new_id = ov.add("neologism")                     # ids continue above len(base)
ov.remove("typo")                                # the id is retired, nothing is renumbered
ov.save("vocab.ovl")

back = Overlay.load("vocab.ovl", PerfectHashIndex)   # pass the base class, not an instance
folded = back.compact()                              # rebuild the base; this renumbers
folded, remap = back.compact_with_remap()            # ...with old id -> new id, uint64 bytes
n = back.compact_to_file("vocab2.bmp")               # the same rebuilt base, streamed to a file

An id is never reissued and removal never renumbers, so an id held elsewhere keeps its meaning until compact() — which is explicit for exactly that reason. load and from_bytes take the base class because each index loads itself; the blob records which base wrote it, so passing the wrong class is an error rather than an unchecked read of bytes meant for something else. save is atomic, like the indexes' own — a crash or a full disk leaves the previous file whole rather than a truncated one — and streams: an overlay over a mapped base of a gigabyte saves without a copy of the base.

Overlay.load and Overlay.from_bytes are checksummed and validated throughout. The header carries a check of its own and a hash of everything after it, both verified before any of it is read, so a flipped bit anywhere raises ValueError rather than loading as a different key or a revived id. The framing is checked past the checksums too — the lengths, the additions and their UTF-8, the tombstones against the id space — and the base region goes to the base class's loader, which validates its own. A blob written by 0.12 still loads, without the two checksums that format does not carry; saving it again writes the current one and it gains them.

key, keys and compact need the base to store its keys. CompactHashIndex does not, so an overlay over it answers membership and raises TypeError for the rest — in Rust that same absence is a compile error, since the methods live on a trait the keyless index cannot implement. Removal over that base also inherits its false-positive rate: a contains that was never true of a real key can retire an id, so remove by a key you know is present — or by the id itself:

ids = {key: ov.add(key) for key in ("neologism", "typo")}   # whatever the caller already stores
ov.retire_id(ids.pop("typo"))                               # the tombstone, with no key to be wrong

retire_id sets exactly the tombstone remove sets and asks the base nothing, so it is the one removal a false positive cannot mislead. An id at or above id_space(), or one already retired, is False and changes nothing.

Batched lookups into a buffer¶

ids_of returns a list, which means one Python int per key. When the ids are headed for numpy or array rather than for a loop, ids_of_bytes skips that: it returns the same answers packed as native-endian fixed-width items, and np.frombuffer shares the memory instead of copying it.

import numpy as np

buf = idx.ids_of_bytes(probes)              # 4 bytes/key here, 8 for StringIndex
ids = np.frombuffer(buf, dtype=idx.ID_DTYPE)
found = ids[ids != idx.MISSING_ID]          # absent keys come back as MISSING_ID

ID_DTYPE and MISSING_ID are class attributes because the width differs between the index types (StringIndex ids are 64-bit, the hash indexes' are 32-bit) — read them from the class rather than hardcoding one. A buffer cannot carry None, so MISSING_ID stands in for an absent key; it is the largest value of the width, which is never a real id, and ids_of_bytes refuses outright on the one index size where it would be.

When the same probe batch size comes round again and again, ids_into writes the ids into a buffer you already own rather than handing back a fresh bytes each call. Anything with a writable C-contiguous buffer of ID_DTYPE items will do; a read-only, strided or wrongly typed one raises BufferError, and one shorter than keys raises ValueError. The first len(keys) items are written and the rest are left as they were.

out = np.empty(batch, dtype=idx.ID_DTYPE)    # allocate once
for probes in batches:                       # each of exactly `batch` keys
    idx.ids_into(probes, out)
    consume(out)

Arrow columns, without a Python string per key¶

ids_of_arrow takes an Arrow utf8/large_utf8 column — a pyarrow Array or ChunkedArray, a pandas column of ArrowDtype (through its __arrow_array__), a polars Series (through to_arrow()) — and reads the keys straight out of its offset and data buffers, so no Python str is built or borrowed per key; that was half to two thirds of what the list forms cost. The answer is packed like ids_of_bytes, with MISSING_ID for an absent key and for a null (ClosedHashIndex raises on a null — a closed vocabulary has no id for it), and ids_into_arrow writes it into a buffer you own, as ids_into does. The buffers are copied once per call, which is the price of doing this through the buffer protocol rather than Arrow's C Data Interface: a memcpy against a hash and a cache miss per key.

import pyarrow as pa

col = pa.array(probes)                       # or table["word"], a polars Series, a pandas column
ids = np.frombuffer(idx.ids_of_arrow(col), dtype=idx.ID_DTYPE)
idx.ids_into_arrow(col, out)                 # into memory you own

On the shuffled dictionary (479 823 member probes, min of seven alternated rounds in one process, local/arrowbench.py): CompactHashIndex 48 ns a key against 145 for ids_of and 105 for ids_of_bytes; PerfectHashIndex 55 against 153 / 121; ClosedHashIndex 20 against 116 / 87; StringIndex 264 against 468 / 435, where the transducer walk is most of the cost either way.

Threads, including free-threaded CPython¶

The module tells CPython it does not need the GIL, and the guarantee behind that is:

The seven index types are immutable after building. Share one across as many threads as you like and call id, contains, key, ids_of from all of them. Building, batch lookups and persistence release the GIL, so other threads keep running while a large index is built or queried.
The two types that hold mutable state — the StringIndex iterator and Overlay — serialise. Sharing one of those between threads is safe: the calls take an internal lock and queue up rather than raising. A shared iterator hands each key to exactly one thread; concurrent Overlay.add calls each get their own id.

Verified on CPython 3.14t with eight threads. Without the lock, PyO3's borrow flag turns a shared iterator or overlay into RuntimeError: Already borrowed on a free-threaded build — seven of eight threads failed before the fix, which is what tests/test_python.py now pins.

Free-threaded CPython has no stable ABI before 3.15 — PEP 803 puts abi3t there — so the abi3 wheel that serves every other interpreter cannot load on a free-threaded one. 3.14t therefore gets a wheel of its own, cp314-cp314t, built from the same source with the same guarantees; pip picks it over the sdist. Older free-threaded builds have no wheel: PyO3 supports 3.14t and not 3.13t.

Rust¶

use lexindex::{
    ClosedHashIndex, CompactHashIndex, DictIndex, DoubleArrayIndex, HashedDictIndex,
    PerfectHashIndex, StringIndex,
};

let idx = StringIndex::build(["apple", "apricot", "banana"])?;
assert_eq!(idx.id("banana"), Some(2));
assert_eq!(idx.key(0).as_deref(), Some("apple")); // rank-walk over the FST → owned String
assert_eq!(idx.prefix("ap").len(), 2);
let near: Vec<_> = idx.fuzzy("aple", 1)?.into_iter().map(|(k, _)| k).collect();
assert_eq!(near, ["apple"]);

// `save`, `load`, `load_mmap` and their `_untrusted` / `_verified` forms take any `AsRef<Path>`.
let path = std::env::temp_dir().join("lexindex-usage-catalog.bix");
idx.save(&path)?;
let info = lexindex::inspect_file(&path)?; // what the file is, from its header alone
assert_eq!((info.kind, info.keys), (lexindex::BlobKind::StringIndex, Some(3)));
// SAFETY: nothing may modify the file while a mapped index borrows it (see `load_mmap`).
let idx = unsafe { StringIndex::load_mmap(&path) }?; // zero-copy; no read into RAM
assert_eq!(idx.id("banana"), Some(2)); // the same answers, off the mapped file

let dict = PerfectHashIndex::build(["GET", "POST", "PUT"])?; // requires the default `mph` feature
assert_eq!(dict.key(dict.id("POST").unwrap()), Some("POST")); // exact reverse lookup

let small = CompactHashIndex::build(["GET", "POST", "PUT"], 1)?; // 1.24 B/key, no reverse
let tiny = CompactHashIndex::build_bits(["GET", "POST", "PUT"], 4)?; // 0.74 B/key, 6.25% FP rate
assert!(small.contains("POST"));

let closed = ClosedHashIndex::build(["GET", "POST", "PUT"])?; // the perfect hash alone, ~0.24 B/key
assert_eq!(closed.id("POST"), tiny.id_unchecked("POST")); // same hash, same ids; no membership

let words = DictIndex::build(["apple", "apricot", "banana"])?; // ordered, keys stored, ~2.64 B/key
assert_eq!((words.id("banana"), words.key(0).as_deref()), (Some(2), Some("apple")));
assert_eq!(words.lower_bound("ap")..words.lower_bound("aq"), 0..2); // the "ap" keys as an id range
assert_eq!(words.longest_prefix("bananas"), Some(("banana".to_string(), 2))); // longest match
words.route_microblocks(); // opt-in: ~0.5 B/key of memory, in no blob, for a faster search

let hashed = HashedDictIndex::from_dict(words, 8)?; // the dictionary, and a hash sidecar beside it
assert_eq!(hashed.id("banana"), Some(2)); // one hash and a read of each table, not a search
assert_eq!(hashed.dict().key(2).as_deref(), Some("banana")); // ordered queries: the dictionary's

let lexicon = DoubleArrayIndex::build(["北京", "北京大学", "大学", "大学生"])?; // a character a step
assert_eq!(lexicon.longest_prefix("大学生活"), Some(("大学生".to_string(), 3)));
let mut words = Vec::new(); // every key in the text: (start, end) in bytes, and the key's rank
lexicon.for_each_occurrence("北京大学生", |start, end, id| words.push((start, end, id)));
assert_eq!(words, [(0, 6, 0), (0, 12, 1), (6, 12, 2), (6, 15, 3)]);
# drop(idx);
# std::fs::remove_file(&path).ok();
# Ok::<(), lexindex::IndexError>(())

Building a corpus that does not fit in memory¶

Every index but DoubleArrayIndex has a build that never holds the keys, and each takes the shape its structure allows:

use lexindex::{CompactHashIndex, DictIndex, PerfectHashIndex, StringIndex};
# let dir = std::env::temp_dir();
# let (bix, bmp) = (dir.join("lexindex-usage-stream.bix"), dir.join("lexindex-usage-stream.bmp"));
# let (bch, bdx) = (dir.join("lexindex-usage-stream.bch"), dir.join("lexindex-usage-stream.bdx"));

// `CompactHashIndex` keeps a 16-byte pair per key and drops the string: any iterator will do...
let small = CompactHashIndex::build(["a", "b", "c"].iter(), 1)?;
// ...and past memory the pairs are sorted in runs spilled beside the output, the perfect hash is
// built from the merged runs a chunk at a time, and the file is what `build` + `save` would write.
CompactHashIndex::build_to_file(["c", "a", "b"], &bch, 1)?;

// `StringIndex` needs the keys in ascending byte order and streams them into the transducer.
StringIndex::build_sorted_to_file(["a", "b", "c"], &bix)?;
// ...or takes them in any order through an external sort: runs spilled beside the output, merged.
StringIndex::build_to_file(["c", "a", "b"], &bix)?;

// `DictIndex` sorts the same way, then walks the sorted keys three times: the block heads and the
// count, the symbol table's training sample -- whose stride depends on that count -- then the
// encoding, which goes into the file as it is produced.
DictIndex::build_to_file(["c", "a", "b"], &bdx)?;

// `PerfectHashIndex` stores its keys in slot order, and slot order is only known once the perfect
// hash is built -- so it takes a *factory* and reads the source twice. Keys must be distinct.
PerfectHashIndex::build_to_file(&bmp, || ["c", "a", "b"])?;
# assert!(small.contains("a"));
# assert_eq!(std::fs::read(&bch)?, small.to_bytes()?);
# std::fs::remove_file(&bix).ok();
# std::fs::remove_file(&bmp).ok();
# std::fs::remove_file(&bch).ok();
# std::fs::remove_file(&bdx).ok();
# Ok::<(), lexindex::IndexError>(())

At 10 M real-word pairs the streamed PerfectHashIndex build peaks at 471 MB against 1 272 MB for the same keys handed to build as a list; the streamed StringIndex build peaks at 49.6 MB against 721.9. The perfect hash's number includes the output file, which it fills through a mapping — its anonymous memory is 20.6 bytes per key and does not grow with n.

The streamed DictIndex build peaks at 29.4 MB against 66.6 over 479 823 real words, for the same bytes on disk. What it still holds is the block heads, the per-block arrays and one start a microblock, about (mean head length + 20) / block + 8 / micro bytes per key — 0.36 at the default on the dictionary — so a larger block holds less as well as storing less; the block data, which is the bulk of the index, goes into the file as it is encoded. The rest is the symbol tables: one trains per shard of 65 536 keys and they train in parallel, so a build holds one trainer per training thread, about 2.9 MB each and at most 64 MB between them: past 21 trainers they queue rather than multiply, which is what keeps the peak a property of the work and not of the core count. It is never a function of n — on one thread the same two builds peak at 17.2 MB and 34.3, against 12.7 and 32.1 when a single table covered the whole index. It reads the sorted keys three times, and pays about 26 % in build time for it.

The streamed CompactHashIndex build peaks at 302 MB at 100 M real-word pairs against 8 834 MB for the same keys handed to build as a list (254 against 903 at 10 M), and 0.94 GB at 10⁹, where the list would need about 90 GB. Under 256 MiB of fingerprint table the peak is the run buffer itself or the perfect hash's construction plus the table, whichever is larger — at 100 M they are within 5 MB of each other; past it the fingerprints go through range files and the peak is the perfect hash's own construction, 0.9 bytes per key: 0.6 of it the table being built and the keys its first level bumped, the rest the second level's grouping of those keys. Its transient disk is the distinct pairs twice, 32 bytes per key, beside the output, plus twelve more per key for the range files past 268 M keys at the default width, so that no byte of the output is ever written at a random offset. The 10⁹ build took seven and a quarter minutes here, six of them generating the keys.

The perfect hash also needs transient disk space: an output whose key arena exceeds 32 MB is filled window by window through a spill file next to it, so about 2.2× the output size has to be free in the target directory until the build finishes. Filling the arena in one pass instead is what made the build rewrite its own file dozens of times over.

StringIndex::build_to_file is build for a corpus that does not fit: every 256 MiB of keys is sorted and deduplicated in memory and spilled as one run to a temporary directory beside the output, the runs are merged — one buffered reader each — into the transducer, and the file is byte for byte what build then save would have written. Peak memory is one run plus a 1 MiB buffer per run; the transient disk is the distinct keys once, removed on every exit path. A corpus that fits in one run never touches the disk before the output. Measured at 100 M real-word pairs (w1.w2 over /usr/share/dict/words, a 1.30 GB blob), it peaks at 414 MB against 11 985 MB for the same generator handed to build, and finishes in 150 s against 211: a run is an arena of key bytes with a span per key, not a String each, so it also sorts faster. At 10 M pairs the corpus fits in one run — 296 MB against 1 205, 19 s against 24 — and the blobs are identical either way.

Cargo features: mph (default) adds PerfectHashIndex, CompactHashIndex, ClosedHashIndex and HashedDictIndex; mmap (default) adds load_mmap; --no-default-features is an fst-only build (StringIndex, DictIndex, DoubleArrayIndex and Overlay, no extra dependencies). All of them compile for 32-bit targets, wasm32-unknown-unknown included — leave mmap off there, since there is nothing to memory-map.

Editing without a rebuild — `Overlay`¶

Every index is built once from the whole key set, so adding a single key has always meant rebuilding for the whole corpus. Overlay<I> wraps one with the keys added since and the ids retired from it, making add and remove O(1) while the base stays untouched:

use lexindex::{Overlay, StringIndex};
let mut ov = Overlay::new(StringIndex::build(["apple", "banana"])?);
let cherry = ov.add("cherry");            // ids continue above base.len()
assert!(ov.remove("apple"));              // the id is retired, nothing is renumbered
assert_eq!(ov.id("apple"), None);
assert_eq!(ov.key(cherry).as_deref(), Some("cherry"));

let blob = ov.to_bytes()?;                // base + additions + tombstones in one file
let back = Overlay::from_bytes_with(&blob, StringIndex::from_bytes)?;
assert_eq!(back.len(), 2);

let (folded, remap) = back.compact_with_remap()?;   // rebuild the base — this renumbers…
assert_eq!(folded.len(), 2);
assert_eq!(folded.key(remap[cherry as usize]).as_deref(), Some("cherry")); // …and says how
# Ok::<(), lexindex::IndexError>(())

An id is never reissued and removal never renumbers, so an id held elsewhere keeps its meaning for the overlay's lifetime; compact() is the one call that breaks that, and it is explicit for exactly that reason. compact_with_remap() returns the old → new id table alongside, and compact_to_file(path) writes the rebuilt base straight to a file, streaming the live keys from where the base holds them, for a base too large to hold twice. Lookups cost one base lookup plus a bitset probe, and a miss in the base costs a hash map probe on top.

The base may be shared: OverlayBase is implemented for Arc<I>, so Overlay<Arc<StringIndex>> leaves the index usable and lets several overlays sit on one base. That is what the Python bindings use.

from_bytes_with takes the base's loader rather than picking one, because Overlay<I> is generic over the base and each base parses its own blob: Overlay::from_bytes_with(&blob, PerfectHashIndex::from_bytes). All three base loaders are safe fns, so the closure could now be a trait method — it stays a closure because that is also how a base loaded some other way, or a stub that skips the base entirely, gets in: the fuzz target and the framing property tests both need it, and the wrong loader is already refused by the base tag rather than by the type.

key, keys and compact need the base to store its keys, which CompactHashIndex does not — an overlay over it answers membership and nothing else, and the absence is a compile error rather than a runtime one. Removal over that base also inherits its false-positive rate: a contains that was never true of a real key can retire an id, so remove by a key you know is present.

The blob records which base wrote it, so from_bytes_with refuses a mismatch before calling the loader — handing perfect-hash bytes to the wrong deserialiser is not something a caller can do by mistake.

C¶

The capi feature exports six of the seven indexes to C — all but DoubleArrayIndex: one opaque LexindexIndex handle, fourteen lexindex_* functions, and the header include/lexindex.h, generated from src/capi.rs by cbindgen and regenerated in CI so the two cannot drift.

cargo build --release --features capi                           # target/release/liblexindex.so
cargo rustc --release --features capi --crate-type staticlib    # liblexindex.a instead
cc -std=c11 examples/capi.c -Iinclude -Ltarget/release -llexindex -o capi
LD_LIBRARY_PATH=target/release ./capi

#include "lexindex.h"

const char *keys[] = {"cherry", "apple", "banana", "apricot"};
size_t lens[] = {6, 5, 6, 7};
LexindexIndex *index = NULL;
if (lexindex_index_build(LEXINDEX_KIND_DICT, keys, lens, 4, &index) != LEXINDEX_STATUS_OK)
    fprintf(stderr, "%s\n", lexindex_last_error());

uint64_t id;
lexindex_index_id(index, "banana", 6, &id);             /* LEXINDEX_STATUS_OK, id 2 */
lexindex_index_id(index, "durian", 6, &id);             /* LEXINDEX_STATUS_NOT_FOUND */
uint64_t ids[4];
lexindex_index_ids(index, keys, lens, 4, ids);          /* 3 0 2 1; LEXINDEX_NO_ID for a miss */

char key[16]; size_t len;
lexindex_index_key(index, 0, key, sizeof key, &len);    /* "apple", NUL-terminated, len 5 */
lexindex_index_key(index, 3, NULL, 0, &len);            /* BUFFER_TOO_SMALL, len 6: the size first */

lexindex_index_save(index, "fruit.bdx");
LexindexIndex *again = NULL;
lexindex_index_open("fruit.bdx", &again);               /* whatever kind the file holds */
lexindex_index_free(again);
lexindex_index_free(index);

The rules, each of which the header states beside the function it binds:

Every fallible call returns a LexindexStatus, LEXINDEX_STATUS_OK being zero. A failure leaves its message in lexindex_last_error(), one per thread, valid until the next failure on that thread; NOT_FOUND is an answer rather than a failure and leaves it alone. A null pointer where one is required is INVALID_ARGUMENT on every function that has a status to return it in.
One handle, six kinds. A C caller opens a blob it may not have written, so the kind is a run-time fact: lexindex_index_kind says which, and what a kind cannot answer is UNSUPPORTED rather than a missing symbol — key on LEXINDEX_KIND_COMPACT and LEXINDEX_KIND_CLOSED, which store no keys; contains on LEXINDEX_KIND_CLOSED, the perfect hash alone. id means what the kind means: exact for string, dict and perfect; a miss answers as present one time in 256 for compact, and for hashed dict at the width it was built with — eight bits from lexindex_index_build, exact at zero; every key gets some id for closed.
Keys are (pointer, length) UTF-8, not NUL-terminated, so strlen is the caller's; paths are NUL-terminated. key writes NUL-terminated and reports the length without the terminator; buf = NULL, cap = 0 asks for the size, and BUFFER_TOO_SMALL reports it as well.
Ownership. A handle is freed by lexindex_index_free and nothing else; keys and paths are borrowed for the call; lexindex_index_from_bytes copies. A handle is immutable, so any number of threads may query one at once.
Versioning. LEXINDEX_ABI_VERSION is the ABI the header describes and lexindex_abi_version() the one the library was built with; within a number symbols are only added, and a change to one is a major release of the crate. lexindex_version() is the crate version.

Not in the ABI, each additive when someone asks: Overlay, the mmap loaders, the automata queries (prefix, range, fuzzy, subsequence), and the fingerprint and block knobs of build.

Command line¶

The crate ships a binary of the same name, so the choice between five indexes can be made without writing any code: cargo install lexindex, or cargo run --bin lexindex -- from a checkout. The Python wheel carries the same program, so pip install lexindex installs the same lexindex command with no Rust toolchain, and python -m lexindex runs it where the environment's scripts are not on the path. It is a shell over plan_file, the builders, inspect_file and the indexes' own key iterators, and computes nothing of its own.

$ lexindex plan /usr/share/dict/words --reverse --prefix
479823 keys, mean length 9.3, mean shared prefix 6.3, ranked by size
* DictIndex              1190567 bytes   2.48 B/key    384 ns  estimated at block 1024
  DictIndex              1252952 bytes   2.61 B/key    336 ns  estimated at block 256
  DictIndex              1357175 bytes   2.83 B/key    311 ns  estimated at block 32
  StringIndex            2882400 bytes   6.01 B/key    297 ns  estimated
the nanoseconds are a model of this crate's own machine, not a measurement of yours

$ lexindex build /usr/share/dict/words words.bin --reverse --prefix
479823 keys, mean length 9.3, mean shared prefix 6.3, ranked by size
* DictIndex              1190567 bytes   2.48 B/key    384 ns  estimated at block 1024
  DictIndex              1252952 bytes   2.61 B/key    336 ns  estimated at block 256
  DictIndex              1357175 bytes   2.83 B/key    311 ns  estimated at block 32
  StringIndex            2882400 bytes   6.01 B/key    297 ns  estimated
the nanoseconds are a model of this crate's own machine, not a measurement of yours
wrote words.bin: DictIndex over 479823 keys, 1205985 bytes (2.51 B/key)

$ lexindex inspect words.bin
kind: DictIndex
format: BDX3
bytes: 1205985
keys: 479823
arena_bytes: 1173645

$ lexindex dump words.bin | head -3
&c
'd
'em

inspect --sections reads a DictIndex whole and says where its bytes went. The sections always sum to the blob, so the output is an accounting rather than an estimate, and each is given per key and as a share:

$ lexindex inspect words.bin --sections
kind: DictIndex
format: BDX3
bytes: 1205985
keys: 479823
arena_bytes: 1173645
sections.header: 72 (0.0002 B/key, 0.01 %)
sections.tables: 7215 (0.0150 B/key, 0.60 %)
sections.header_codes: 761 (0.0016 B/key, 0.06 %)
sections.phrases: 4 (0.0000 B/key, 0.00 %)
sections.heads: 4282 (0.0089 B/key, 0.36 %)
sections.head_ends: 659 (0.0014 B/key, 0.05 %)
sections.block_offsets: 1128 (0.0024 B/key, 0.09 %)
sections.micro_offsets: 22501 (0.0469 B/key, 1.87 %)
sections.chars: 0 (0.0000 B/key, 0.00 %)
sections.restart_headers: 9845 (0.0205 B/key, 0.82 %)
sections.restart_wide: 794 (0.0017 B/key, 0.07 %)
sections.restart_codes: 47107 (0.0982 B/key, 3.91 %)
sections.entry_headers: 299889 (0.6250 B/key, 24.87 %)
sections.entry_wide: 48282 (0.1006 B/key, 4.00 %)
sections.entry_codes: 763446 (1.5911 B/key, 63.30 %)
sections.total: 1205985 (2.5134 B/key, 100.00 %)
sections.restarts: 14526
sections.entries: 464828
sections.wide: 24538

Read it as four groups. The codes are the front-coded suffixes under whichever codec the shard settled on, which is what the index is for. The headers are the (lcp, len) stream and the varints of the pairs no code could name — 0.75 bytes a key here against the flat 0.97 BDX2 spent, a quarter of the blob on this corpus and near half of it on dense decimal ids, since there is almost nothing else to store. The vocabulary — the symbol tables, the code each shard's headers took, the phrase dictionary and, in a BDX4 blob, the character code its keys are spelled in — is 0.66 % here, and is the part that grows with the shards rather than with the keys. The directory — the three packed offset arrays and the block heads — is 2.7 % at this block and never more than a few per cent, which is worth knowing before optimising it. The per-block samples the opening search reads are not in the list because they are not in the blob: eight bytes of a head each, built from the heads at load. --sections is a DictIndex's alone; on any other kind it says so. The same numbers are on DictSections for a program that would rather not parse text.

dump writes the keys a blob holds, one per line, in id order — sorted order for the two ordered indexes, construction order for PerfectHashIndex, and live keys only for an Overlay. It exists for one reason: lexindex dump old.blob | lexindex build - new.blob is the migration path off a format a later version stops reading, and it round-trips — rebuilding from a dump reproduces the blob byte for byte. CompactHashIndex and ClosedHashIndex store no keys at all, so dumping one is an error that says so rather than an empty file.

plan and build take the same five needs, which say what the index must be able to do and so narrow what may be picked — with none of them the only question asked is id(key), and the two probabilistic indexes are allowed:

--reverse    key(id) as well as id(key)
--ordered    ids in lexicographic order, and in-order iteration
--prefix     prefix and range queries (an ordered index)
--fuzzy      Levenshtein and subsequence queries      -- only StringIndex answers this
--exact      a non-member must be answered as one     -- bars CompactHashIndex and ClosedHashIndex

The command line assumes an open vocabulary, and so implies --exact. Asked to rank with no needs at all, the honest answer on size is ClosedHashIndex at 0.24 bytes a key — and it answers a key it has never seen with some member's id, because it stores nothing to check against. That is the right index for a fixed vocabulary and a trap for anything else, and a ranking is read by someone who has not yet decided. So plan and --index auto leave the two probabilistic indexes out and say on stderr that they did:

$ lexindex plan words.txt
479823 keys, mean length 9.3, mean shared prefix 6.3, ranked by size
* DictIndex              1190567 bytes   2.48 B/key    384 ns  estimated at block 1024
  DictIndex              1252952 bytes   2.61 B/key    336 ns  estimated at block 256
  DictIndex              1357175 bytes   2.83 B/key    311 ns  estimated at block 32
  StringIndex            2882400 bytes   6.01 B/key    297 ns  estimated
  PerfectHashIndex       4641399 bytes   9.67 B/key    131 ns  estimated
the nanoseconds are a model of this crate's own machine, not a measurement of yours
excluded: needs exact — CompactHashIndex (a bounded false-positive rate) and ClosedHashIndex
(a stranger gets some member's id). Pass --closed-vocabulary if every key you will ask about is
in this file, and they are ranked with the rest.

--closed-vocabulary is that promise, and puts both back in the ranking. The line is printed only when the default is what excluded them: ask for --prefix and they were never candidates, so nothing is explained. Naming an index with --index closed builds it whatever the needs say — the needs narrow a choice, and naming one is not a choice to narrow. The library is unchanged: Needs::default() in Rust and Python still asks only for id(key), because a program that calls plan has a caller who decided, and a command line has a person who is still deciding.

build writes only the blob: the ladder and the one-line summary both go to stderr, so stdout stays free. --index auto is the default and is what asks the planner; --index dict | string | compact | closed | perfect names one instead and skips the plan entirely. On the 479 823-word dictionary that is 468-490 ms against 127-135 over nine alternating runs -- --index auto pays for the planner's two 100 000-key draws, which build every candidate the needs left, and the dictionary once per priced block. Below 100 000 keys the plan builds the real indexes rather than modelling them, so an auto build there builds every candidate and then the winner again; naming the index is how not to.

--objective is what the ladder ranks for. memory is the default and the smallest blob, which is what plan has always answered; latency is the fastest id(key); balanced is whichever candidate gives up least on the axis it does worse on. The candidates and their sizes do not change with it -- only the order, and so what --index auto builds. On the word list above, memory answers DictIndex at block 1024 and 2.48 B/key, latency answers PerfectHashIndex, four times the size and a third of the wait, and balanced answers the same dictionary at block 32 -- 19 % faster for 14 % more space. The block is a candidate of its own, so an objective picks one of those too.

--objective also takes a workload: op=weight pairs between commas, ranked by the workload's mean operation. The ops are hits and misses (id(key) on a member and on a stranger), reverse (key(id)), prefix (a prefix or range query, priced as a prefix_count), common_prefix and longest_prefix; batch=N is the keys an ids_of call holds. The weights are relative, so counts read off a log serve as they are. An op is also a question the index has to answer: reverse rules out the two indexes that store no keys and a prefix query asks for an ordered one, whatever the flags said. The ordered pair is where this decides something. On the same word list --objective common_prefix=9,hits=1 answers StringIndex at 397 ns against 1853 for the fastest dictionary, prefix=9,hits=1 answers DictIndex at block 32 -- 276 ns against 806 -- and hits=9,misses=1,batch=1024 leaves PerfectHashIndex first at 56 ns a key.

The nanoseconds are modelled, and of one machine. a + b·s + c·len + d·s·len per structure, operation and DictIndex block, where len is the mean key length and s is log2 of the blob over 64 KiB -- what a lookup waits on is how far its bytes are from the CPU, which the key count alone does not say. The constants are fitted to 240 cells timed on this crate's own hardware -- a Ryzen 7 5800HS with 16 MB of L3 -- by bench/latency_model.py, whose fit re-derives the tables in src/estimate.rs from the artifact under bench/results/. Mean absolute error is 6-12 % on id(key); on prefix_count it is 26-42 %, because that operation's cost is dominated by how many keys the prefix actually matches and the model has no term for it. Two things follow. It is an ordering: fitted with a corpus left out, it names the fastest index on that corpus in 30 of 30 corpus-size cells for id(key), for nine hits to a miss, for batches of 1 024, for key(id) and for a common_prefix-heavy workload; over ten workloads the mean pick costs 1.000-1.050× the fastest. Against the published sweep, which it was not fitted to, it names the fastest of every lane in 28 of 30 cells and picks between DictIndex and StringIndex the way the measurement does in 29, never choosing one more than 1.02× slower. What it gets wrong is a choice between ordered indexes, because there the candidates are close: the transducer is the faster at 100 000 keys on six corpora of thirteen, and the blocks of one dictionary are often within a few per cent of each other. Held out, it names the fastest ordered id(key) in 19 of 30 cells and one within 5 % of it in 23, never one more than 1.11× slower -- and 5 % is about what placement in physical memory moves a single-threaded probe on this machine. And it is high: the cells were timed through the Python binding, so every number carries that call, and the model reads 297 ns for StringIndex on the word list where the Rust harness in docs/benchmarks.md measures 256-270. The overhead falls on every candidate, so it moves the numbers and not the ranking -- but do not quote them as your own.

--block sets the DictIndex block -- 1..=1024, or fast / balanced / compact for 32 / 256 / 1024 -- and requires --index dict. It is refused alongside auto on purpose: the plan prices all three named blocks as candidates of their own and ranks them with the rest, so a block named beside auto would ask the planner to choose one and then overrule its answer. --index auto builds the block on the line it marked; to choose one yourself, read it off the ladder and name both.

--stream decides whether the build holds the corpus. With a named --index and a keys file -- never standard input, which cannot be rewound -- build feeds the file straight into the streaming builders, and what stays in memory is the index being made rather than the keys. auto (the default) does it past a quarter of what /proc/meminfo says is available, always and never force it either way, and a size (1000, 512M, 4G) sets the threshold. On a 925 MB, 7 343 721-line path list the peak resident set falls from 1.34 to 0.28 GB for string, 1.42 to 0.26 for dict, 1.29 to 0.15 for compact and closed, and 2.96 to 0.97 for perfect -- whose own blob is 935 MB, so it is the one index that cannot end below the file it was built from. The blobs are byte for byte the ones the in-memory build writes, so this is a memory setting and never a format. --index auto streams too, since plan_file prices the file without holding it either: the ladder is printed from the streamed plan and the winner is then built the same way. What is still read in is standard input, and a kind with no streaming build in the current feature set — build says which on stderr rather than pretending.

A keys file is one key per line, UTF-8, in any order; - reads standard input, and duplicates are removed by the builders. An empty line is skipped -- a file that ends in a newline is the common case and an empty key is not -- and the count is reported on stderr wherever the command reads the file in. plan over a file does not read it in, so there it is skipped silently. Invalid UTF-8 is an error naming the line rather than a replacement character, since the library takes &str and an index built from lossy bytes would hold keys the file does not.

The exit code is 0, 2 for a command line that does not parse (the usage text follows the message), and 1 for work that fails -- a missing file, a blob that is not one, a build the library refuses, a key with a line break in it that dump cannot write as a line. lexindex --help prints the whole surface; three of the five indexes need the mph feature, and a build without it says so rather than pretending.

Benchmark¶

python bench/compare.py measures serialised size on real dictionary words against marisa-trie, DAWG and datrie (the double-crown table above). python bench/scale.py measures build time, peak memory, and lookup latency from 1 M to 100 M real keys, each cell once with the keys handed over as a list and once as a generator — the second is what CompactHashIndex's streaming build exists for, and the only way to see its own footprint rather than the corpus's. cargo run --release --example bench measures point-lookup latency for the indexes against std::HashMap (SipHash and FxHash) and BTreeMap on real dictionary-word bigrams (it refuses to run without a word list rather than substitute synthetic keys); cargo run --release --example peak reports the peak resident memory and wall time of one build, one index per process; cargo run --release --example mmap_zero_copy times the owned load against the zero-copy load_mmap.

Usage guide¶

plan — which index, before you build one¶

StringIndex — ordered, FST-backed¶

What limit buys — and what it cannot¶