lexindex v0.4.0

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%.

lexindex v0.3.0

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.

lexindex v0.2.0

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

lexindex v0.1.0

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