Skip to content

Changelog

All notable changes to this project are documented here. The format follows Keep a Changelog and the project adheres to Semantic Versioning.

[0.4.0] — 2026-07-06

Added

  • Ordered navigation on StringIndex — successor(query) (smallest key >= query) and predecessor(query) (largest key <= query), each O(query length) by seeking the FST (no scan), plus lazy iteration: for key, id in index in Rust StringIndex::iter() decodes one key per step by the rank-walk, so it never materialises the whole key set the way prefix("") would.
  • Batched lookups — ids_of(keys) and keys_of(ids) on StringIndex and PerfectHashIndex, plus ids_of(keys) on CompactHashIndex. Each loops in Rust and crosses the Python↔Rust boundary once instead of per key, so a bulk string → id / id → string mapping avoids the per-call FFI overhead. Returns a list aligned with the input, None where a key/id is absent. Named ids_of/keys_of (not keys) so a class is never mistaken for a mapping — dict(index) builds {key: id} from the iterator instead.
  • musllinux_1_2 wheels (x86_64 + aarch64) for Alpine / musl-based containers, alongside the existing manylinux, macOS, and Windows wheels.
  • Scale benchmark (bench/scale.py) measuring build time, peak memory, and lookup latency from 1M to 100M real keys.

Fixed

  • CompactHashIndex::from_bytes guards the fingerprint-table length check with a checked multiply, so a corrupt blob with a fabricated huge n fails cleanly instead of overflowing usize (a debug-build panic; release builds already wrapped to a clean error). Documented the trust boundary shared by both minimal-perfect-hash blobs: from_bytes / load validate the lexindex framing but deserialise the embedded MPH via epserde, which does not bound-check a corrupted MPH region — feed only blobs you produced (the same contract as load_mmap). StringIndex blobs are fully validated and unaffected.

Testing

  • Property-based tests (proptest, dev-dependency only): the rank-walk id ↔ key round-trip over random prefix-nested and multibyte key sets; the PerfectHashIndex bijection onto [0, n); CompactHashIndex never false-negatives a member; and every from_bytes deserialiser rejects arbitrary or (for lexindex-owned bytes) single-byte-flipped input cleanly — never panics or reads out of bounds. Line coverage rose to 97.0%.

[0.3.0] — 2026-07-05

Added

  • CompactHashIndex — the smallest string → dense id map, and smaller than any installable alternative. A minimal perfect hash (ptr_hash) plus a k-byte fingerprint per key, storing no keys at all. On the real /usr/share/dict/words (479 823 words) it serialises to 1.30 bytes/key at fingerprint_bytes=1 and 2.30 at 2 — 2.3× smaller than marisa-trie (2.98) and far below every trie benchmarked. The trade-offs are explicit: membership is probabilistic (a non-member reads as present with probability 256^-fingerprint_bytes — measured 0.36 % at 1 byte, 0.001 % at 2) and there is no reverse id → key (the keys are not stored). Reach for it when a fixed vocabulary's footprint is paramount and rare false positives are acceptable; use PerfectHashIndex for exact membership + reverse, or StringIndex for ordered/fuzzy queries. Exposed to Python as CompactHashIndex(items, fingerprint_bytes=1) with id / id_unchecked / contains / to_bytes / from_bytes / save / load / load_mmap; in Rust behind the default mph feature.

Changed

  • StringIndex dropped its stored reverse map — id → key is now reconstructed from the FST by a rank-walk. Each id is the key's rank, i.e. the FST's output, so key(id) walks the automaton from the root, at each node taking the last transition whose accumulated output stays ≤ id, and returns the path once the outputs sum to exactly id (O(key length), no auxiliary structure). This deletes the front-coded reverse dictionary added in 0.2.0: the serialised blob is now just [magic][fst]. The effect on real-world size is large — on /usr/share/dict/words the StringIndex blob shrinks from 12.61 to 5.95 bytes/key (−53 %), because 0.2.0's front-coded map only reached its advertised "~6 B/key" on structured keys that share long prefixes, not on a natural vocabulary. Full prefix / range / fuzzy / subsequence are retained.
  • Breaking: the on-disk blob magic is now BIX4; StringIndex blobs written by 0.1.x / 0.2.0 must be rebuilt. PerfectHashIndex blobs are unchanged.
  • Benchmarks are now measured on real English words, not a synthetic entity-{i} catalog. Sequential structured keys collapse the FST to a near-regular automaton and report a misleading ~0 bytes/key; bench/compare.py refuses synthetic keys and compares size and build against marisa-trie, DAWG and datrie on /usr/share/dict/words.

[0.2.0] — 2026-07-05

Added

  • Zero-copy load_mmap on StringIndex and PerfectHashIndex (new default mmap feature, backed by memmap2): memory-map a saved blob and borrow the index from the mapped pages instead of reading it into RAM, so a multi-gigabyte index loads instantly and its pages are shared across processes. StringIndex maps the whole blob (FST + front-coded dictionary); PerfectHashIndex maps the key arena (the bulk) and reads only the small MPH into memory. Exposed to Python as StringIndex.load_mmap / PerfectHashIndex.load_mmap. Reads are byte-wise (no alignment requirement); the mapped file must stay immutable while an index borrows it. --no-default-features (the fst-only build) omits it.
  • MkDocs documentation site at https://ilgrad.github.io/lexindex/ (Material + mkdocstrings API reference), and a mmap_zero_copy example that times the owned load against the zero-copy load_mmap.
  • CI now enforces a 95% line-coverage floor (cargo llvm-cov) on the Rust core.

Changed

  • StringIndex's reverse map (id → key) is now a front-coded string dictionary instead of a flat arena of raw bytes + one 8-byte offset per key. Because ids are the sorted rank, keys are stored sorted and delta-encoded against their bucket predecessor ((shared-prefix length, suffix), one pointer per 8-key bucket), so on a structured sorted catalog the serialised StringIndex blob shrinks from ~27 to ~6 bytes/key — below the raw key bytes. PerfectHashIndex (unordered MPH slots, which cannot share prefixes) keeps the flat arena and is unchanged.
  • Breaking: StringIndex::key(id) now returns Option<String> (reconstructed on the fly) rather than Option<&str>; the Python StringIndex.key is unaffected (still returns str | None).
  • Breaking: the on-disk blob magic is now BIX2; StringIndex blobs written by 0.1.0 must be rebuilt (PerfectHashIndex blobs are unchanged).

[0.1.0] — 2026-06-28

First public release — compact, immutable string<->id indexes for huge catalogs; a standalone Rust + Python library that also pairs with betula-cluster (map string ids to cluster ids and back).

Added

  • StringIndex — ordered, FST-backed index: exact string <-> id, plus prefix, range, fuzzy (bounded Levenshtein edit distance), and subsequence iteration — all automaton-driven over the FST, never a full scan. Serialises to a flat, relocatable blob (save / load / to_bytes / from_bytes) with fully length- and offset-validated parsing (safe on untrusted input).
  • PerfectHashIndex — minimal-perfect-hash dictionary (ptr_hash): verified-membership id, a faster id_unchecked for closed vocabularies (~1.25× faster than std::HashMap on point lookup), reverse lookup, and persistence (save / load) via epserde, keyed on a version-stable hash (FNV-1a + splitmix64) so a serialised MPH reloads and queries identically on any build.
  • Python bindings (PyO3 abi3 extension, CPython 3.11+): pip install lexindex, zero runtime dependencies, typed (py.typed + stubs).
  • Feature gating — mph (default) provides PerfectHashIndex (pulls ptr_hash + epserde); --no-default-features is an fst-only build, free of the informational RustSec advisories on the ptr_hash dependency tree. fst's levenshtein is always on for fuzzy search.
  • Benchmark — cargo run --release --example bench compares both indexes against std::HashMap / BTreeMap (build time, lookup latency, serialised size).