Metadata-Version: 2.4
Name: lexindex
Version: 0.9.0
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Operating System :: OS Independent
Classifier: Topic :: Text Processing :: Indexing
Classifier: Topic :: Software Development :: Libraries
Classifier: Typing :: Typed
License-File: LICENSE
Summary: Compact, immutable string<->id indexes for huge catalogs: an ordered FST with prefix/range/fuzzy, plus minimal-perfect-hash dictionaries (the compact one is ~1.3 B/key).
Keywords: index,fst,perfect-hash,prefix,fuzzy,autocomplete,catalog,string-interning
Author-email: Ilia Gradina <ilia.gradina@gmail.com>
License-Expression: MIT
Requires-Python: >=3.11
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Changelog, https://github.com/ilgrad/lexindex/blob/main/CHANGELOG.md
Project-URL: Documentation, https://ilgrad.github.io/lexindex/
Project-URL: Homepage, https://github.com/ilgrad/lexindex
Project-URL: Issues, https://github.com/ilgrad/lexindex/issues
Project-URL: Repository, https://github.com/ilgrad/lexindex

# lexindex

[![PyPI](https://img.shields.io/pypi/v/lexindex)](https://pypi.org/project/lexindex/)
[![Python](https://img.shields.io/pypi/pyversions/lexindex)](https://pypi.org/project/lexindex/)
[![CI](https://github.com/ilgrad/lexindex/actions/workflows/ci.yml/badge.svg)](https://github.com/ilgrad/lexindex/actions/workflows/ci.yml)
[![Docs](https://img.shields.io/badge/docs-mkdocs-blue.svg)](https://ilgrad.github.io/lexindex/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://github.com/ilgrad/lexindex/blob/main/LICENSE)
[![Rust core · PyO3](https://img.shields.io/badge/Rust%20core-PyO3-orange.svg)](https://github.com/ilgrad/lexindex)
[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.22119002.svg)](https://doi.org/10.5281/zenodo.22119002)

Compact, immutable **string↔id indexes for huge catalogs**, with a Rust core and Python bindings.
Build once over a set of strings (entity names, document keys, vocabulary terms, cluster labels);
query many times. Pairs naturally with [`betula-cluster`](https://github.com/ilgrad/betula-cluster) —
map string ids to cluster ids and back — but stands on its own.

Three complementary, build-once / query-many structures — pick by what you need to ask:

- **`StringIndex`** — an **ordered** index backed by a finite-state transducer
  ([`fst`](https://crates.io/crates/fst)). Exact `string → id` and `id → string`, plus **prefix**,
  **range**, **predecessor / successor** (nearest key ≤ / ≥ a query), **fuzzy** (bounded Levenshtein
  edit distance), **subsequence**, and **lazy full iteration** — all driven by automata over the FST,
  with no separate key list to scan (exact/prefix/range seek directly; a broad fuzzy or subsequence
  pattern may still traverse most of the automaton) — in a compressed, serialisable, memory-mappable
  form. The only structure here that
  answers **ordered and typo-tolerant** queries. Use it for autocomplete, fuzzy search, browse, and
  ordered scans of a large catalog.
- **`CompactHashIndex`** — the **smallest** `string → dense id` map: a minimal perfect hash
  ([`ptr_hash`](https://crates.io/crates/ptr_hash)) plus a small fingerprint per key, storing *no keys
  at all*. **1.27 bytes/key** on real dictionary words — **2.3× smaller than `marisa-trie`**, down to
  **0.77 bytes/key** at a 4-bit fingerprint (`fingerprint_bits=4`, 6.25% false-positive rate) — below
  every trie benchmarked (see [Benchmarks](#benchmarks)) — at the cost of **probabilistic membership**
  (a tunable `2^-bits` false-positive rate) and **no reverse lookup**. Use it when a fixed vocabulary's
  footprint is paramount and rare false positives are acceptable.
- **`PerfectHashIndex`** — a minimal-perfect-hash dictionary with **verified membership** (`id`) and
  **reverse lookup** (`key`); the arena stores full keys, so it is exact but larger. For a known-closed
  vocabulary, `id_unchecked` skips the membership comparison and is **faster than `std::HashMap`**. Use
  it as a fixed-vocabulary token↔id map on a hot path when you need exact membership and `id → key`.

All three assign dense ids in `[0, n)` and **serialise to a flat blob** (`save` / `load`, or zero-copy
`load_mmap`) — build once, persist, then reload and query many times. All are immutable after building.
The `mph` feature (on by default) provides the two hash indexes; `--no-default-features` is `fst`-only.

## Python

```bash
pip install lexindex
```

```python
from lexindex import CompactHashIndex, PerfectHashIndex, StringIndex

idx = StringIndex(["apple", "apricot", "banana", "cherry"])
idx.id("banana")             # 2  (sorted rank)
idx.key(0)                   # "apple"  — reconstructed from the FST, no stored reverse map
idx.prefix("ap")             # [("apple", 0), ("apricot", 1)]
idx.fuzzy("aple", 1)         # [("apple", 0)]  — typo-tolerant
idx.successor("ba")          # ("banana", 2)   — nearest key >= query
idx.predecessor("ba")        # ("apricot", 1)  — nearest key <= query
list(idx)                    # [("apple", 0), ...]  — lazy iteration in sorted order
idx.ids_of(["apple", "x"])   # [0, None]  — batched: one FFI call, not one per key
idx.save("catalog.bix")      # persist; StringIndex.load("catalog.bix") reloads it

c = CompactHashIndex(["GET", "POST", "PUT", "DELETE"])  # smallest string->id (~1.3 B/key at scale;
#   fingerprint_bits=4 halves that to ~0.8 at a 6.25% false-positive rate)
c.id("POST")                 # dense id in [0, n); probabilistic membership, no id->key
c.id_unchecked("POST")       # fastest lookup for a known-closed vocabulary

d = PerfectHashIndex(["GET", "POST", "PUT", "DELETE"])
d.id("POST")                 # dense id in [0, n); membership verified, returns None if absent
d.key(d.id("POST"))          # "POST"  — exact reverse lookup (keys stored)
```

No runtime dependencies; a single abi3 wheel covers CPython 3.11+. See
[`examples/quickstart.py`](https://github.com/ilgrad/lexindex/blob/main/examples/quickstart.py) for all
three indexes end to end, and the [documentation site](https://ilgrad.github.io/lexindex/).

### Pairs with betula-cluster

`lexindex` owns the `string id ↔ dense id` mapping; [`betula-cluster`](https://github.com/ilgrad/betula-cluster)
clusters the numeric rows. Use the lexindex dense id as the embedding-matrix row index and you can go
both ways — `string id → cluster` and `cluster → string ids`:

```python
idx = PerfectHashIndex(doc_ids)                  # string id <-> dense [0, n) id
matrix[idx.id(doc_id)] = embedding[doc_id]       # row index == lexindex id
labels = betula_cluster.fit_predict(matrix, n_clusters=k)
cluster = labels[idx.id("doc-00042")]            # string id -> cluster
members = [idx.key(int(r)) for r in (labels == cluster).nonzero()[0]]  # cluster -> string ids
```

Runnable: [`examples/bridge_clustering.py`](https://github.com/ilgrad/lexindex/blob/main/examples/bridge_clustering.py).

## Rust

```toml
[dependencies]
lexindex = "0.8"
# fst-only (drop the ptr_hash dependency):
# lexindex = { version = "0.8", default-features = false }
```

## Usage

```rust
use lexindex::StringIndex;

let idx = StringIndex::build(["apple", "apricot", "banana", "cherry"])?;

assert_eq!(idx.id("banana"), Some(2));     // string → id (sorted rank)
assert_eq!(idx.key(0).as_deref(), Some("apple")); // id → string
assert!(idx.contains("cherry"));

// prefix / range iteration, lexicographically ordered
let fruit: Vec<_> = idx.prefix("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(fruit, ["apple", "apricot"]);

// typo-tolerant fuzzy lookup (Levenshtein edit distance ≤ 1) and subsequence match
let near: Vec<_> = idx.fuzzy("aple", 1)?.into_iter().map(|(k, _)| k).collect();
assert_eq!(near, ["apple"]);
let sub: Vec<_> = idx.subsequence("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(sub, ["apple", "apricot"]);

// serialise to a flat blob, then reload — or `load_mmap` to borrow it zero-copy from the file
idx.save("catalog.bix")?;
// SAFETY: nothing may modify the file while a mapped index borrows it (see `load_mmap`).
let idx = unsafe { StringIndex::load_mmap("catalog.bix") }?; // no read into RAM; pages shared
# drop(idx);
# std::fs::remove_file("catalog.bix").ok();
# Ok::<(), lexindex::IndexError>(())
```

```rust
use lexindex::PerfectHashIndex;            // requires the default `mph` feature

let dict = PerfectHashIndex::build(["GET", "POST", "PUT", "DELETE"])?;
let id = dict.id("POST").unwrap();             // fastest exact lookup, dense id in [0, n)
assert_eq!(dict.key(id), Some("POST"));
assert_eq!(dict.id("PATCH"), None);            // membership is verified, not just hashed

// persist the MPH and reload it (the dense ids are preserved across save/load)
dict.save("verbs.bmp")?;
// `load` is unsafe: the embedded perfect hash cannot be validated, so only blobs this library
// wrote are in contract. See "Design notes" below.
let dict = unsafe { PerfectHashIndex::load("verbs.bmp") }?;
assert_eq!(dict.id("POST"), Some(id));
# std::fs::remove_file("verbs.bmp").ok();
# Ok::<(), lexindex::IndexError>(())
```

```rust
use lexindex::CompactHashIndex;           // requires the default `mph` feature

// The smallest string->id map: an 8-bit fingerprint/key ⇒ ~1.3 B/key, ~0.4% membership
// false-positive (build_bits(keys, 4) ⇒ ~0.8 B/key at 6.25%).
let dict = CompactHashIndex::build(["GET", "POST", "PUT", "DELETE"], 1)?;
let id = dict.id("POST").unwrap();             // Some(slot); a non-member may rarely read as present
assert!(dict.contains("GET"));
let raw = dict.id_unchecked("POST");           // no fingerprint check — for a known-closed vocabulary
assert_eq!(raw, id);
// no key(id): CompactHashIndex stores no keys. Use PerfectHashIndex when you need id → string.
# Ok::<(), lexindex::IndexError>(())
```

## Design notes

- **`StringIndex` is the FST alone — `id → key` is reconstructed by a rank-walk, with no stored reverse
  map.** Ids are the sorted rank of each key, which is exactly the FST's output value, 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`. That is `O(key length)` and
  needs no auxiliary structure, so the serialised blob is just `[magic "BIX4"][fst]` — half the size of
  the 0.2.0 front-coded layout on real words (12.6 → 5.95 B/key) and simpler to reason about.
  `from_bytes`/`load` validate the magic and verify the FST's stored checksum, so a truncated or
  corrupted owned blob is rejected at load rather than queried; `load_mmap` skips that `O(n)` scan to
  keep mapping constant-time, so a mapped file is trusted to be intact.
- **Perfect-hash ids are not reproducible across builds.** `ptr_hash`'s construction is randomised,
  so building the *same* key set twice assigns different slots — measured on 50 k keys, only ~53 % of
  them keep their id. Ids are stable across `save`/`load` of one built index, so persist the **blob**,
  not the key list, whenever an id is written down anywhere else. `StringIndex` ids are the sorted
  rank and are reproducible by construction.
- **`CompactHashIndex` stores no keys — only a minimal perfect hash and one small fingerprint per
  slot.** `id(key)` hashes the key to a slot (the MPH), then compares the key's `b`-bit fingerprint —
  from a *second* hash with a different basis and multiplier — against the stored one; a match is a
  hit. The two hashes are uncorrelated for well-distributed keys, so a non-member survives both with
  probability about `2^-b`: a design rate measured against, not a proof, and no guarantee at all
  against queries chosen by an adversary (both hashes are deterministic and unseeded). It is the
  tunable false-positive rate
  (`fingerprint_bits` ∈ 1..=64, bit-packed). Dropping the key arena is what takes it below
  `marisa-trie`; the price is that membership is probabilistic and there is no `id → key`. The blob
  is `[magic "BCH5"][n][fp_bits][overflow_cap][mph_len][side_len][payload][check][mph][bit-packed
  fingerprints][side]` — the payload hash is verified on owned loads, so a corrupted blob fails
  cleanly. Its build **streams**: only a 16-byte `(hash, second hash)` pair is kept per key, never
  the strings. 0.7 blobs (`BCH3`) still load, as does a collision-free 0.8.0 `BCH4` (bit-identical);
  a `BCH4` holding a side table is refused — its side fingerprints were truncated — with a message
  naming the rebuild. 0.5/0.6 blobs (`BCH1`/`BCH2`) are **refused**: they predate the recorded remap
  bound and store no keys to recompute it from, so loading one would reinstate an out-of-bounds
  read — rebuild instead.
- **`PerfectHashIndex`** keys the MPH on a deterministic 64-bit hash of each string (so queries take
  `&str` without allocating), then verifies the hit against the stored key — an MPH returns a slot for
  *any* input, so verification is what turns it into a real membership test, and the stored keys give
  exact `id → key`. Two distinct keys colliding in the 64-bit hash cannot fail the build: the MPH is
  built over one representative per distinct hash value and the colliding leftovers are served — still
  exactly — from a tiny side table consulted only after the stored-key comparison has missed, so the
  hot path pays nothing. The expected number of colliding pairs is `n(n-1)/2^65` ≈ 2.7×10⁻⁸ at 1 M
  keys, 2.7×10⁻⁴ at 100 M — the table is almost always empty. The hash is **version-stable** (FNV-1a
  + a splitmix64 finalizer, not `std`'s `DefaultHasher`), so a `save`d MPH (the `ptr_hash` structure
  serialised via [`epserde`](https://crates.io/crates/epserde), alongside the arena) reloads and
  queries identically on any build — the precondition for persistence. `CompactHashIndex` shares the
  same version-stable slot hash plus a second, uncorrelated one for the fingerprint, and resolves hash
  collisions the same way — its side table keeps the second hash at its **full 64 bits** whatever
  `fingerprint_bits` is set to, so only a pair colliding in **both** 64-bit hashes at once
  (`≈ 2^-128` per pair) would merge.
- **Zero-copy `load_mmap`** (the default `mmap` feature, `memmap2`) memory-maps a saved blob and
  borrows the index directly from the mapped pages — no read into RAM, so a multi-gigabyte index is
  ready instantly and the OS shares its pages across processes. `StringIndex` maps the whole FST;
  `CompactHashIndex` maps its fingerprint table; `PerfectHashIndex` maps the key arena (the bulk) and
  reads only the tiny MPH into memory. Every read is byte-wise, so there is no alignment gotcha. It is
  an **`unsafe fn`** — deliberately, since the mapped bytes are borrowed rather than copied, so a write
  to the file from *any* process while the index is alive is undefined behaviour and nothing in the
  library can check for it. lexindex blobs are written once and never updated in place, so publishing
  new versions under new paths discharges the obligation; the Python binding, which has no way to
  express it in the type system, states the same contract in its docstring.
- **Loading a perfect-hash index is `unsafe` too — `from_bytes` and `load`, not just `load_mmap`.**
  The blob framing is validated and checksummed, so accidental corruption is rejected cleanly, but the
  embedded MPH is an `epserde` region whose pilot table `ptr_hash` reads unchecked, and the fields that
  would bound that read are private to `ptr_hash` — no amount of checking downstream can make a crafted
  blob safe. A function that is unsound for *some* input belongs behind `unsafe fn`, so both
  perfect-hash indexes say so in their signatures rather than in a doc paragraph. Upstream agrees:
  `epserde` 0.13 made `deserialize_full` an `unsafe fn`, and PtrHash declined a checked `try_index()`
  on the same grounds. `StringIndex` keeps safe `from_bytes`/`load` — `fst` validates its own structure
  and guarantees invalid input cannot violate memory safety.
- `mph` is opt-in-by-default: with `--no-default-features` the crate depends only on `fst` (and keeps
  `StringIndex`). Enabling `mph` pulls `ptr_hash` and its dependency tree, which currently carries a few
  informational RustSec advisories (unmaintained / unsound) on transitive crates — `cargo audit`
  reports them as warnings, not vulnerabilities. The `fst`-only build is free of them.

## Benchmarks

### Serialised size on real English words

`python bench/compare.py` on `/usr/share/dict/words` (479 823 words, 9.3 B/key raw). **Keys are a real
vocabulary, never a synthetic `entity-{i}` sequence** — sequential keys collapse the FST to a
near-regular automaton and report a misleading ~0 B/key, so the benchmark refuses them. Smaller is
better; the capability columns are why you would still pick a larger one.

| library | prefix | range | fuzzy | reverse id→str | exact membership | zero-copy mmap | **bytes/key** |
|---|:---:|:---:|:---:|:---:|:---:|:---:|---:|
| **lexindex `CompactHashIndex` (fp=4 bits)** | — | — | — | — | probabilistic | ✅ | **0.77** |
| **lexindex `CompactHashIndex` (fp=1)** | — | — | — | — | probabilistic | ✅ | **1.27** |
| **lexindex `CompactHashIndex` (fp=2)** | — | — | — | — | probabilistic | ✅ | **2.27** |
| `marisa-trie` | ✅ | — | — | ✅ | ✅ | ✅ | 2.98 |
| **lexindex `StringIndex`** | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | 5.95 |
| lexindex `PerfectHashIndex` | — | — | — | ✅ | ✅ | ✅ | 13.60 |
| DAWG (`dawg2`) | ✅ | — | — | — | ✅ | — | 23.96 |
| `datrie` | ✅ | — | — | — | ✅ | — | 30.69 |

Two honest crowns, both scoped to what is measured above — libraries a Python or Rust project can
actually install. Research-grade C++ (CoCo-trie, XCDAT, PDT, SuRF) has no bindings to benchmark and
is not claimed against. **`CompactHashIndex` is the smallest `string → dense id` map here — 2.3×
below `marisa-trie` at the default 8-bit fingerprint, 3.9× at 4 bits** — when you can accept a bounded
false-positive rate (about `2^-fingerprint_bits` by design — the fingerprint comes from a second hash,
uncorrelated with the slot hash for well-distributed keys — measured **6.2530 %** at 4 bits and **1.5553 %** at 6 over 2 M non-member probes,
z = +0.18 / −0.83 against theory; **≈0.4 %** at 8 bits, **≈0.0015 %** at 16) and don't need
`id → key`. It is not a security primitive: both hashes are deterministic and unseeded, so an
adversary who chooses the queries can find false positives at will. It stays below
marisa's 2.98 B/key at every width up to 21 bits — the [width guide](docs/usage.md) tables the
trade-off. **`StringIndex` is the only
structure that answers fuzzy and range queries at all**, at 4× below a plain DAWG. `marisa-trie`
remains the pick when you need *exact* membership *and* ordering *and* the smallest such index —
lexindex doesn't claim that particular cell (see below for why).

### Against other Rust string indexes

`marisa-trie` is C++. Among ordered string indexes you can `cargo add`, **none is smaller than
`StringIndex`** — the double-array tries trade space for lookup speed, and no succinct LOUDS trie
(marisa / XCDAT / CoCo-trie-style) exists in Rust to depend on. So `StringIndex` at 5.95 B/key is the
**smallest ordered `string → id` index available in pure Rust** — second only to a C++ library, and the
only one of them that does fuzzy and range. Same real words:

| Rust structure | bytes/key | vs marisa |
|---|---:|---:|
| `marisa-trie` (C++, reference) | 2.98 | 1.0× |
| **lexindex `StringIndex`** (ordered + fuzzy + reverse) | **5.95** | 2.0× |
| `fst::Set` (membership only — no ids, no reverse) | 4.85 | 1.6× |
| `yada` (double-array) | 15.98 | 5.4× |
| `crawdad::MpTrie` (minimal-prefix) | 19.63 | 6.6× |
| `crawdad::Trie` (double-array) | 26.22 | 8.8× |

<sub>Measured with `crawdad` 0.4, `yada` 0.5, `fst` 0.4 over the same word list; size = serialised bytes
(`serialize_to_vec().len()`) ÷ key count. Not lexindex dependencies — reproduce in a throwaway crate.</sub>

Reaching `marisa`'s 2.98 needs its recursive succinct-trie label nesting, which the byte-oriented `fst`
automaton is ~1.6× away from by construction (even a bare `fst::Set`, which stores no ids at all, is
4.85) — so beating it on the *ordered* index means reimplementing marisa from scratch, not a bounded
tweak. `CompactHashIndex` takes the size crown the other way: by dropping the keys entirely.

### Point-lookup latency vs the standard library

`cargo run --release --example bench` — 1 M **real dictionary-word bigrams** (`word_i.word_j`, the
same key generator as `bench/scale.py`; mean key 10.9 bytes). Keys are never synthetic
`entity-000…N` sequences — those arrive pre-sorted and hash-degenerate and flatter every number.
Measured on the 0.9.0 code in one session (min of 12 runs, idle machine, four seconds between runs
so clocks settle). Absolute numbers are machine-dependent — this session runs ~19% faster than the
one that produced the 0.8.0 table, `std::HashMap` control included — so compare the **ratios**, and
only within a column.

| structure | build | lookup | note |
|---|---|---|---|
| lexindex `CompactHashIndex::id` (fp=1) | **~114 ms** | ~151 ns | fingerprint-verified, `2^-8` false-positive rate |
| lexindex `PerfectHashIndex::id_unchecked` | ~291 ms | **~111 ns** | closed vocabulary, no membership check |
| `std::HashMap<String, u32>` | ~187 ms | ~246 ns | in-RAM, not serialisable |
| lexindex `PerfectHashIndex::id` (verified) | ~294 ms | ~273 ns | one extra cache line + full key compare |
| lexindex `StringIndex` (FST) | ~253 ms | ~337 ns | *and* prefix / range / fuzzy |
| `std::BTreeMap<String, u32>` | ~201 ms | ~770 ns | in-RAM |

<sub>Run-to-run lookup spread over the 12 runs: 1.9% for the `HashMap` control, 2.3% for
`id_unchecked`, 5.4% `BTreeMap`, 7.1% `CompactHashIndex::id`, 8.0% `PerfectHashIndex::id`, 11.0%
`StringIndex` — the control's tightness is what says the session was quiet. The ratio to `HashMap`
is itself session-dependent: `id_unchecked` measured 2.2× here and 1.7× in the 0.8.0 session on the
same machine, so read it as "roughly twice", not as a constant. 0.9's fused two-hash pass was
verified separately by an interleaved A/B against the 0.8.1 binary in one session:
`CompactHashIndex::id` 165 → 158 ns (−4.3%), build 117 → 116 ms, with `HashMap`, `BTreeMap` and both
`PerfectHashIndex` rows flat. `CompactHashIndex`'s build halved back in 0.8: it sorts 16-byte
`(hash, second hash)` pairs instead of strings, keeping it below `HashMap`'s build. Real keys move
lookups in lexindex's favour versus synthetic ones (byte-wise FNV vs `HashMap`'s SipHash), while
every `build` reads higher because real input is not pre-sorted and sorting is part of the
build.</sub>

**Honest reading:** for a **fixed / closed vocabulary**, `PerfectHashIndex::id_unchecked` is the
**fastest** — roughly twice as quick as `HashMap` (1.7–2.2× depending on the session; no probing,
no membership comparison) *and* compact + serialisable. `CompactHashIndex::id` keeps a probabilistic
membership check and *still* beats `HashMap` on lookup (~1.6× here), and builds faster than it too. Full verification (`id`) pays one extra
cache line + a key comparison; `StringIndex` trades more latency for **ordered / prefix / range /
fuzzy** queries the hash maps cannot answer at all. So: `CompactHashIndex` when footprint dominates
and a rare false positive is fine; `PerfectHashIndex::id` for exact membership + reverse;
`StringIndex` when order or fuzzy/prefix matters; `HashMap` when you just need a general in-RAM map
with nothing persisted.

### Scaling to millions of keys

`python bench/scale.py` on real high-entropy keys (dictionary-word bigrams). Build time and memory grow
linearly, lookups stay sub-microsecond, and `CompactHashIndex`'s **1.27 bytes/key holds constant** as
`n` grows:

| n | structure | build | bytes/key | peak RSS | lookup |
|---|---|---:|---:|---:|---:|
| 1 M | `StringIndex` | 0.33 s | 0.68\* | 126 MB | 280 ns |
| 1 M | `CompactHashIndex` | 0.34 s | 1.27 | 161 MB | 209 ns |
| 10 M | `StringIndex` | 5.1 s | 2.00\* | 1.08 GB | 873 ns |
| 10 M | `CompactHashIndex` | 5.1 s | 1.27 | 1.35 GB | 372 ns |

<sub>\* bigram keys share far more prefixes than single words — at 1 M the generator draws on only
1 000 distinct words, which is why `StringIndex` compresses to an unrepresentative 0.68 B/key there;
the honest single-word figure is in the size table above. The whole table is one measurement session
on the 0.5.1 code (min of 3 runs per cell). Peak RSS includes the input key list, which dominates at
this scale and is why the column falls by 8-17% rather than by the 47-73% the build itself dropped
in 0.5.0. Linear extrapolation puts 100 M at ~50 s and ~13.5 GB (a big-memory box). Hash collisions
do not change the picture at any n: since 0.8 both perfect-hash indexes absorb them into a side
table instead of failing the build, and the fst build has no collision failure mode at all.</sub>

## License

MIT © Ilia Gradina

