Metadata-Version: 2.4
Name: lexindex
Version: 4.4.2
Classifier: Development Status :: 5 - Production/Stable
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: Programming Language :: Python :: Free Threading :: 3 - Stable
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: a front-coded dictionary with prefix and range queries, an ordered FST that adds fuzzy and subsequence search, and minimal-perfect-hash maps (the compact one is 1.24 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
Project-URL: Sponsor, https://github.com/sponsors/ilgrad

# 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/)
[![crates.io](https://img.shields.io/crates/v/lexindex)](https://crates.io/crates/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)
[![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.22119002.svg)](https://doi.org/10.5281/zenodo.22119002)
[![Sponsor](https://img.shields.io/badge/sponsor-GitHub%20Sponsors-ea4aaa?logo=githubsponsors&logoColor=white)](https://github.com/sponsors/ilgrad)

**Compact, immutable string ↔ id indexes for huge catalogs**, with a Rust core, Python bindings and a C ABI.
Build once over a set of strings — entity names, document keys, vocabulary terms, cluster labels —
persist a flat blob, and query it many times, memory-mapped where the structure allows. Pairs with
[`betula-cluster`](https://github.com/ilgrad/betula-cluster) (string ids ↔ cluster ids, both ways)
but stands on its own.

[![lexindex against the smallest trie anyone else built, on thirteen corpora at a million keys: smaller on all thirteen](https://raw.githubusercontent.com/ilgrad/lexindex/main/docs/assets/frontier-1m.svg)](https://ilgrad.github.io/lexindex/benchmarks/#the-research-frontier-measured)

<sub>Thirteen corpora at a million keys against MARISA, XCDAT, CoCo-trie, PDT and the C² benchmark's
structures, each at its own best configuration — the protocol, the ten-million-key table and every
other structure are in [the benchmarks](https://ilgrad.github.io/lexindex/benchmarks/#the-research-frontier-measured).
The figure is the size axis, which `DictIndex` wins. On an exact lookup XCDAT is still ahead on most
corpora at a million keys: lexindex's faster exact search there — `DictIndex` after 4.4's opt-in
`route_microblocks()`, which holds 0.25–0.5 bytes a key more in memory, or `StringIndex` — beats
XCDAT 15 on `dna`, trails it by 6–11 % on `uuid`, `urls` and `titles-ru` and by 1.2× to 1.9× on the
other nine. At ten million keys it is ahead on `dna`, `numeric` and `urls`, level on `titles-en` and
`uuid`, and 1.36× behind on `opaque`. **`HashedDictIndex` (4.1) wins the latency axis outright:**
the same dictionary with its `id` answered by a perfect hash is 4.1× to 9.0× faster than XCDAT 15
and 1.4× to 3.2× smaller, on all thirteen corpora at a million keys and all six at ten million — and
3.1× to 7.4× faster and 1.2× to 2.8× smaller with an 8-bit fingerprint that turns away all but one
stranger in 256; an exact answer for a stranger is the dictionary's search above. Every column is in
[the benchmarks](https://ilgrad.github.io/lexindex/benchmarks/#hasheddictindex-against-xcdat), and
none is quoted here without the others.</sub>

## Six indexes

| | `StringIndex` | `DictIndex` | `HashedDictIndex` | `CompactHashIndex` | `ClosedHashIndex` | `PerfectHashIndex` |
|---|:---:|:---:|:---:|:---:|:---:|:---:|
| `string → id` | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ |
| `id → string` | ✅ | ✅ | ✅ | — | — | ✅ |
| ordered ids, ranges, `lower_bound` | ✅ | ✅ | ✅ | — | — | — |
| prefix | ✅ | ✅ | ✅ | — | — | — |
| common prefix · longest prefix | ✅ | ✅ | ✅ | — | — | — |
| fuzzy · subsequence | ✅ | — | — | — | — | — |
| membership | exact | exact | `2^-bits` false positives ² | `2^-bits` false positives | none: closed vocabulary | exact |
| `Overlay` edits | ✅ | — | — | ✅ | — | ✅ |
| zero-copy `load_mmap` | ✅ | ✅ ¹ | ✅ ¹ | ✅ | — | ✅ |
| **bytes/key**, 480 k English words | 5.95 | **2.64** | 5.25 · 6.25 at 8 bits | **1.24** · 0.74 at 4 bits | **0.24** | 10.88 |
| `id`, 1 M word bigrams | 263 ns | 399 ns | 77 ns · `id_unchecked` 62 | 57 ns | the bare perfect hash | 109 ns · `id_unchecked` 49 |
| Cargo feature | — | — | `mph` | `mph` (default) | `mph` | `mph` |

<sub>¹ `DictIndex` maps every section and builds in memory what a lookup reads on every call: the
per-block samples — eight bytes a block, one byte per thirty-two keys at the default block — the
symbol tables, and where they apply a character code's tables and a trie over blocks whose samples
tie; 0.07–0.39 bytes a key on the corpora measured. `HashedDictIndex` maps its dictionary the same way
and its rank table whole. ² At zero fingerprint bits `id` is the dictionary's own search, exact and
at its cost, and the hash is `id_unchecked`, which answers a stranger with some rank below `n`.</sub>

- **`StringIndex`** — an **ordered** index that is the finite-state transducer
  ([`fst`](https://crates.io/crates/fst)) alone: exact `string ↔ id`, **prefix**, **common prefix**
  (the keys a query starts with, in one walk), **range**, **predecessor / successor**, **fuzzy**
  (bounded Levenshtein distance), **subsequence** and lazy in-order iteration, all automata over the
  FST with no key list to scan. Autocomplete, fuzzy search,
  ordered browse.
- **`DictIndex`** — an **ordered** dictionary with the key stored for every id: `string ↔ rank` both
  ways, `lower_bound`, `prefix`, `common_prefix`, `range`, in-order iteration — no automata, so no
  fuzzy. The sorted keys front-coded in blocks of 256, each cut into microblocks of 16, the suffixes
  coded per shard under a symbol table or a packed alphabet — whichever that shard's own bytes
  prefer — over a phrase dictionary mined from the whole blob where repeated spans pay for it:
  **2.64 bytes/key**, 56 % below `StringIndex`, `id` 291–298 ns against its 200–210 — 217–228 after
  `route_microblocks()` — and `key_into` 193–194 against its `key` at 436–445. A prefix is a range
  here, not an automaton walk, so `prefix_count` is two order lookups — **483 ns where `marisa-trie`
  must enumerate every match to count it (119 840)**. Every block from 32 to 1024 comes in **under
  every `marisa-trie` setting measured on this corpus** — 2.85 down to 2.51 against its 2.96–3.07.
  Over the eleven-corpus sweep at a million keys it is the smaller of the two on **ten**, against
  marisa's *best* setting on each and not its default: 3.9 % on `titles-en` up to 78 % on `dna`,
  with `paths` the one it loses, by 5.3 %. At those same settings it answers faster on all but
  `numeric` too, 1.5–5.7×. Exact queries, every id back to its key, small.
- **`HashedDictIndex`** — a `DictIndex` whose `id` is a hash: the dictionary kept whole, and beside
  it a minimal perfect hash and a table holding each key's **rank** at its slot, so `id` is a hash
  and a read where the dictionary searches, while `key(id)`, prefix, range and iteration are the
  dictionary's own, on the same ids. Against XCDAT, the fastest trie measured, over thirteen corpora
  at a million keys and six at ten million: **4.1–9.0× faster and 1.4–3.2× smaller** through
  `id_unchecked`, for 2.62 bytes a key over the dictionary on real words, and 3.1–7.4× faster and
  1.2–2.8× smaller through `id` with an 8-bit fingerprint — a byte a key more — that turns away all
  but one stranger in 256. The dictionary's queries, and a hash's `id`.
- **`CompactHashIndex`** — the **smallest** `string → dense id` map that can reject a non-member:
  an in-crate minimal perfect hash plus a fingerprint per key, *no keys stored*. **1.24 bytes/key** on real words — **2.4× below
  `marisa-trie`** — and **0.74** at a 4-bit fingerprint (6.25 % false positives), for
  **probabilistic membership** (about `2^-bits`) and no reverse lookup. Footprint first, a rare
  false positive acceptable.
- **`ClosedHashIndex`** — the perfect hash **and nothing else**: `id(key) -> u32`, no `Option` — a
  member's id, and *some* id in `[0, n)` for anything else. **0.24 bytes/key**, a fifth of
  `CompactHashIndex`, and a lookup at `id_unchecked`'s cost (19.8 ns on the dictionary, against
  24.7 for the fingerprint-checked `id`). A token → id map where every query is a member by construction.
- **`PerfectHashIndex`** — the perfect hash with the keys stored: **verified membership** and
  **`id → key`**, no ordering. `id_unchecked` skips the compare and runs 4.8× as fast as
  `std::HashMap`; `fingerprints=True` adds one byte per key so an absent key stops after one cache
  miss instead of two (166 → 74 ns on the dictionary) — a stop list, a block list. A fixed-vocabulary
  token ↔ id map on a hot path.

All six assign dense ids in `[0, n)`, **build deterministically** and **serialise to a flat blob**:
`save` / `load` everywhere, zero-copy `load_mmap` where there is more than the perfect hash to map —
`DictIndex` mapping everything but its per-block samples and a few tables, under 0.4 bytes a key.
They are immutable; **`Overlay`** adds and removes keys on `StringIndex`, `CompactHashIndex` and
`PerfectHashIndex` without a rebuild, keeps every id stable, and folds the edits into a fresh base
with `compact()`. The other three are absent by design rather than omission: an overlay issues a
new key the next id after the base, which is exactly what `DictIndex` and `HashedDictIndex` cannot
accept — their ids *are* the lexicographic rank, and a key added in the middle of the order would
not get one — and `ClosedHashIndex` has no membership to ask, so there is no "already in the base"
for an overlay to test against. Every configuration builds on 32-bit targets, `wasm32-unknown-unknown` included
(leave `mmap` off there — nothing to map).

## Install

```bash
pip install lexindex      # one abi3 wheel for CPython 3.11+, no runtime dependencies
```

```toml
[dependencies]
lexindex = "4.4"
# fst-only (drop the memory-mapping and perfect-hash code):
# lexindex = { version = "4.4", default-features = false }
```

## Python

```python
from lexindex import ClosedHashIndex, CompactHashIndex, DictIndex, HashedDictIndex, 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.ids_of(["apple", "x"])   # [0, None]  — batched: one FFI call, not one per key
idx.save("catalog.bix")      # StringIndex.load("catalog.bix") reloads it; load_mmap borrows it zero-copy

c = CompactHashIndex(["GET", "POST", "PUT", "DELETE"])  # 1.24 B/key at scale; fingerprint_bits=4 → 0.74
c.id("POST")                 # dense id in [0, n); probabilistic membership, no id → key
c.id_unchecked("POST")       # fastest lookup for a known-closed vocabulary

z = ClosedHashIndex(["GET", "POST", "PUT", "DELETE"])   # the perfect hash alone, ~0.24 B/key
z.id("POST")                 # a member's id; any other string gets *some* id in [0, n)

w = DictIndex(["GET", "POST", "PUT", "DELETE"])         # ordered, keys stored, ~2.64 B/key
w.id("POST")                 # 2  (sorted rank); w.key(2) == "POST"; w.lower_bound("P") == 2

h = HashedDictIndex.from_dict(w, fingerprint_bits=8)    # w's ranks from a hash, not a search
h.id("POST")                 # 2; h.dict is w, for key, prefix and range

d = PerfectHashIndex(["GET", "POST", "PUT", "DELETE"])  # verified membership and id → key
d.key(d.id("POST"))          # "POST"; d.id("PATCH") is None
```

[`examples/quickstart.py`](https://github.com/ilgrad/lexindex/blob/main/examples/quickstart.py) runs
all six end to end; the [usage guide](https://ilgrad.github.io/lexindex/usage/) covers every
interface, including batched lookups into NumPy and Arrow buffers and free-threaded CPython.

**With `betula-cluster`:** the lexindex dense id is the embedding-matrix row, so `string id →
cluster` and `cluster → string ids` are both one lookup
([runnable](https://github.com/ilgrad/lexindex/blob/main/examples/bridge_clustering.py)):

```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
```

**With Polars:** `lexindex-polars` is an expression plugin, so the lookup runs in the engine's own
threads, inside a lazy plan and under the streaming engine, without the GIL
([the plugin](https://ilgrad.github.io/lexindex/polars/)):

```python
import lexindex_polars  # noqa: F401  -- the import registers the namespace

df.with_columns(pl.col("track").lexindex.id("tracks.bdx"))   # and .contains, .key, .id_unchecked
```

## Rust

```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, a rank-walk over the FST

// prefix / range / fuzzy / subsequence, all lexicographically ordered
let fruit: Vec<_> = idx.prefix("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(fruit, ["apple", "apricot"]);
let near: Vec<_> = idx.fuzzy("aple", 1)?.into_iter().map(|(k, _)| k).collect();
assert_eq!(near, ["apple"]);                            // Levenshtein distance ≤ 1
let sub: Vec<_> = idx.subsequence("ap").into_iter().map(|(k, _)| k).collect();
assert_eq!(sub, ["apple", "apricot"]);

// a flat blob: reload it, or 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
assert_eq!(idx.id("cherry"), Some(3));                  // the same answers, off the mapped file
# drop(idx);
# std::fs::remove_file("catalog.bix").ok();
# Ok::<(), lexindex::IndexError>(())
```

```rust
use lexindex::{ClosedHashIndex, CompactHashIndex, DictIndex, HashedDictIndex, PerfectHashIndex};

let verbs = ["GET", "POST", "PUT", "DELETE"];

// The smallest string → id map that rejects strangers: an 8-bit fingerprint per key, 1.24 B/key,
// ~0.4 % false positives.
let compact = CompactHashIndex::build(verbs, 1)?;
let id = compact.id("POST").unwrap();                  // Some(slot); a stranger may rarely read as present
assert_eq!(compact.id_unchecked("POST"), id);          // no fingerprint check, for a closed vocabulary

// The perfect hash alone, ~0.24 B/key: a member's id, and *some* id in [0, n) for anything else.
let closed = ClosedHashIndex::build(verbs)?;
assert!((closed.id("POST") as usize) < closed.len());

// Verified membership and id → key, the keys stored; ids survive save / load on every index.
let exact = PerfectHashIndex::build(verbs)?;
let id = exact.id("POST").unwrap();
assert_eq!(exact.key(id), Some("POST"));
assert_eq!(exact.id("PATCH"), None);
exact.save("verbs.bmp")?;
assert_eq!(PerfectHashIndex::load("verbs.bmp")?.id("POST"), Some(id));

// Ordered, the key stored for every id, ~2.64 B/key; prefix and range, no fuzzy.
let dict = DictIndex::build(verbs)?;
assert_eq!(dict.id("POST"), Some(2));                  // the sorted rank
assert_eq!(dict.key(2).as_deref(), Some("POST"));
assert_eq!(dict.lower_bound("P"), 2);                  // the "P…" keys are ids 2..lower_bound("Q")

// The same dictionary with a hash sidecar: its ranks from one hash and two reads, not a search.
let hashed = HashedDictIndex::from_dict(dict, 8)?;
assert_eq!(hashed.id("POST"), Some(2));
assert_eq!(hashed.dict().key(2).as_deref(), Some("POST"));
# std::fs::remove_file("verbs.bmp").ok();
# Ok::<(), lexindex::IndexError>(())
```

## C

Under the `capi` feature the six indexes are one opaque handle behind fourteen `lexindex_*`
functions, declared in [`include/lexindex.h`](include/lexindex.h):

```c
#include "lexindex.h"

const char *keys[] = {"cherry", "apple", "banana", "apricot"};
size_t lens[] = {6, 5, 6, 7};
LexindexIndex *index = NULL;
lexindex_index_build(LEXINDEX_KIND_DICT, keys, lens, 4, &index);

uint64_t id;
lexindex_index_id(index, "banana", 6, &id);            /* 2 — the sorted rank */
char key[16]; size_t len;
lexindex_index_key(index, 0, key, sizeof key, &len);   /* "apple" */
lexindex_index_free(index);
```

Every fallible call returns a `LexindexStatus`, zero on success, with the message behind a failure
in `lexindex_last_error()`. `cargo build --release --features capi` builds the shared library with
the symbols; `examples/capi.c` walks the whole surface and [usage](docs/usage.md#c) has the rules.

## Design notes

One line each; the sections are in [the design notes](https://ilgrad.github.io/lexindex/design/).

- **`StringIndex` is the FST alone.** `id → key` is a rank-walk over the automaton, so the blob is
  `[magic "BIX4"][fst]` and there is no reverse map to store or keep in sync.
- **`DictIndex` is front coding under a symbol table.** Blocks of 256 sorted keys, the first whole,
  cut into microblocks of 16 to 32 whose first keys are coded against each other and the rest against
  their predecessors as (shared-prefix length, suffix) — one byte a header, the headers of a run
  before its suffixes — the suffixes under a 255-symbol FSST-style table (its own format) trained
  on the index's own suffixes; a lookup walks the microblock heads to one microblock, rules most
  of its entries out by the header alone and compares the rest against the probe without decoding
  them. Keys mostly outside ASCII are first respelled in an order-keeping code of one or two bytes a
  character (`BDX4`), which takes Chinese and Russian corpora 6.7–17.9 % smaller for up to 3 %
  on `id` and 4.5 % on `ids_of`. `route_microblocks()` (4.4) swaps the walk for a count of eight
  bytes a microblock — 0.5 B/key at the default block, in memory and in no blob — and takes 19–31 %
  off `id` on twelve corpora of thirteen at a million keys.
- **`HashedDictIndex` stores the rank at the perfect hash's slot.** One bit-packed value a key,
  `⌈log2 n⌉ + fingerprint_bits` wide, beside the dictionary's own `BDX3` or `BDX4` blob embedded byte for byte:
  `id` never reads the dictionary, and nothing ordered reads the hash.
- **`CompactHashIndex` stores no keys.** A minimal perfect hash plus one `fingerprint_bits`-wide
  fingerprint per slot from a second, uncorrelated hash — a design rate of about `2^-bits`, not a
  defence against chosen queries. Its build streams 16 bytes per key, never the strings: 302 MB peak
  at 100 M keys against 8.8 GB for a list, 0.94 GB at 10⁹.
- **`ClosedHashIndex` is that perfect hash alone** — the same slot `CompactHashIndex::id_unchecked`
  gives, with a signature that says nothing can tell a member from a stranger.
- **`PerfectHashIndex` verifies every hit against the stored key.** The pair in a billion that
  collides in the 64-bit hash is served, still exactly, from a side table the hot path never reads.
- **Keys are bytes.** No Unicode normalisation, case folding or collation: normalise (NFC/NFKC,
  casefold) before building *and* before querying if the application needs it.
- **Every build is deterministic.** The same keys give the same blob, byte for byte, on any machine
  and thread count — within one version; ids are arbitrary and change whenever the key set does, so
  persist the blob rather than re-derive it.
- **Loading is safe; mapping is `unsafe`.** `from_bytes` and `load` take arbitrary bytes on every
  index — the reason the perfect hash is in-crate — and a crafted blob answers wrong ids, never
  out-of-range ones. `load_mmap` and its `_verified` / `_untrusted` forms borrow the mapped pages,
  so the file must not change while the index is alive.
- **Blobs move forward, not backward.** 2.0 replaced the key hash (the previous one had a two-word
  collision family on ordinary text) and 4.0 replaced it again (branch-free over the key's
  length, half the time on real words), so every hash blob written before 4.0 (`BMP5`–`BMP7`,
  `BCH6`, `BCH7`, `BCL1`) is refused by name and rebuilt from the keys, as is every dictionary
  blob before `BDX3` (`BDX1`, `BDX2`), which 4.0 rewrote a third smaller; `BIX4` crosses the
  versions unchanged, and an `OVL2` does when its base is one — an overlay embeds its base,
  so one over an older hash blob is refused with it.
- **`--no-default-features` is `fst` only** (`StringIndex`, `DictIndex`, `Overlay`); `mph` adds no
  dependency, so the whole tree is `fst` plus `memmap2`, and `cargo audit` reports nothing on either.

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

<!-- table: compare bench/results/compare-2026-09-24-arz-3a73ed5.json columns=prefix,range,fuzzy,reverse,exact,mmap -->
| library | prefix | range | fuzzy | reverse id→str | exact membership | zero-copy mmap | **bytes/key** | **ns/lookup** |
|---|:---:|:---:|:---:|:---:|:---:|:---:|---:|---:|
| **lexindex `ClosedHashIndex`** | — | — | — | — | none (closed vocabulary) | — | **0.24** | 97 |
| **lexindex `CompactHashIndex` (fp=4 bits)** | — | — | — | — | probabilistic | ✅ | **0.74** | 92 |
| **lexindex `CompactHashIndex` (fp=1)** | — | — | — | — | probabilistic | ✅ | **1.24** | **83** |
| **lexindex `CompactHashIndex` (fp=2)** | — | — | — | — | probabilistic | ✅ | **2.24** | 89 |
| **lexindex `DictIndex` (512 per block)** | ✅ | ✅ | — | ✅ | ✅ | ✅ | **2.52** | 350 |
| **lexindex `DictIndex` (256 per block, default)** | ✅ | ✅ | — | ✅ | ✅ | ✅ | **2.64** | 323 |
| `marisa-trie` (4 tries, tiny cache — its smallest here) | ✅ | — | — | ✅ | ✅ | ✅ | 2.96 | 471 |
| `marisa-trie` (default) | ✅ | — | — | ✅ | ✅ | ✅ | 2.98 | 452 |
| `marisa-trie` (huge cache) | ✅ | — | — | ✅ | ✅ | ✅ | 3.07 | 426 |
| **lexindex `StringIndex`** | ✅ | ✅ | ✅ | ✅ | ✅ | ✅ | 5.95 | 232 |
| **lexindex `HashedDictIndex` (fp=8)** | ✅ | ✅ | — | ✅ | probabilistic | ✅ | 6.25 | 100 |
| lexindex `PerfectHashIndex` | — | — | — | ✅ | ✅ | ✅ | 10.88 | 175 |
| DAWG (`dawg2`) | ✅ | — | — | — | ✅ | — | 23.96 | 232 |
| `datrie` | ✅ | — | — | — | ✅ | — | 30.91 | 576 |
| builtin `dict` | — | — | — | — | ✅ | — | — (in RAM only) | 247 |
<!-- /table -->

<sub>Generated by `bench/compare.py` — raw numbers and the machine that produced them:
[`bench/results/compare-2026-09-24-arz-3a73ed5.json`](https://github.com/ilgrad/lexindex/blob/main/bench/results/compare-2026-09-24-arz-3a73ed5.json)
— every cell's build and lookup samples, the false-positive measurement, the CPU, kernel, rustc,
Python and the load average at both ends of the run. **`ns/lookup`** is one exact lookup through
Python over 100 000 probes, half of them plausible near-misses, shuffled — the counterweight to the
size column, since bytes alone read as though the smallest structure were the best one. Every row
pays a **51 ns** call boundary, which is what the empty loop and call cost in this run, against 48
in the run this table carried until now, 46 in the one before that and 51 before it;
`bench/reproduce.sh` prints them side by side because that floor has measured 100 in another
session, and a column from such a run is only comparable within itself. The builtin `dict` is in the table because it is the thing being
replaced. The four smallest rows are also the fastest, and for the same
reason: they store no keys, so a miss is only probably detected and there is no `id → key` on offer.
Fifth is `HashedDictIndex`, which does keep its keys — its dictionary — and answers `id` beside them
in 100 ns, ahead of every other row that can give a key back and of the builtin `dict`, for 6.25
bytes a key. The two `DictIndex` rows are one type at two block sizes; it builds in 157–158 ms
against `marisa-trie`'s 231, answers faster than every `marisa-trie` setting at fewer bytes than any
of them, and the larger block trades reverse-lookup latency for the bytes.
`marisa-trie` appears three times for the same reason it has tuning parameters: its
own documentation says the right setting depends on the data, so the table carries its compact end,
its default and its fast end rather than one point somebody could fairly call untuned.
[The benchmark notes](https://github.com/ilgrad/lexindex/blob/main/docs/benchmarks.md) table the
whole block-size curve, the prefix queries, and the same nine structures over a pinned set of
thirteen corpora at three scales — where the ranking between `DictIndex` and `marisa-trie` reverses
with how much the keys share, which one word list cannot show.</sub>

Two claims, scoped to libraries a Python or Rust project can install. The research-grade C++
frontier has no binding, so it is measured in a harness of its own, on the C² paper's protocol:
lexindex is on the size–latency front on all thirteen corpora at a million keys and all six at ten
million, `DictIndex` is the smallest structure on twelve and five of them and builds faster than
every compressed trie there, `HashedDictIndex` answers `id` faster than every structure there on
all nineteen while smaller than XCDAT, the fastest of them, on every one, and the one corpus that
keeps a trie smaller than `DictIndex` is `numeric`, where `StringIndex` is smaller still
([measured in the benchmark notes](https://github.com/ilgrad/lexindex/blob/main/docs/benchmarks.md#the-research-frontier-measured);
papers, code and licences [cited](https://github.com/ilgrad/lexindex/blob/main/docs/benchmarks.md#the-research-frontier-cited)).
**`CompactHashIndex` is the smallest `string → dense id` map here that can reject a non-member,
2.4× below `marisa-trie` at the
default 8-bit fingerprint and 3.9× at 4 bits**, when a bounded false-positive rate is acceptable:
about `2^-fingerprint_bits` by design, 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, ≈0.0015 % at 16. Both hashes
are deterministic and unseeded, so an adversary who chooses the queries can find false positives at
will — it is not a security primitive. **`StringIndex` is the only structure here that answers
*fuzzy* and subsequence queries**, at 4× below a plain DAWG; ordered range queries `DictIndex`
answers too, and more cheaply. On this corpus `DictIndex` at its default block is smaller than
`marisa-trie` while answering everything marisa does and `key(id)`, `lower_bound` and `range`
besides — but a trie's size swings 3× across corpora and marisa has tuning parameters of its
own, so that is a result about these words at these settings rather than a general ranking
([how it was measured](https://ilgrad.github.io/lexindex/benchmarks/#against-other-rust-string-indexes)).

### Which one to pick

Every size above is one corpus at one `n`, and the ranking is stable across neither: a trie's size
depends on how much the keys share, a fingerprint index's does not
([three corpora, and 10 M](https://ilgrad.github.io/lexindex/benchmarks/#which-one-to-pick-and-how-much-the-corpus-decides-it)).
**`plan` does this on your keys.** `lexindex.plan(keys, prefix=True)` in Python,
`lexindex::plan(&keys, Needs::default().prefix())` in Rust, and `lexindex plan keys.txt --prefix`
from a shell after either install: it prices every index that answers what you asked for — the
dictionary at each of its three block sizes, though not yet `HashedDictIndex` —
ranks them cheapest first, and
says when two are too close to call or when the corpus is one its model cannot carry. Past 100 000
keys it models from two draws of that size and lands within **1.0 % of the built `DictIndex` blob at
the median and 7.2 % at worst**, over 23 corpora at three blocks each;
below it, it builds the candidates and reports what they weigh. `plan_file` does the same for a
keys file **without ever holding it**: 0.27 GB of resident memory against 1.30 on a 925 MB path
list, and the same ladder to the byte. By hand, in decision order:

- **Do the keys need to come back out, or be scanned in order?** Then the fingerprint indexes are
  out: `StringIndex` for prefix / range / fuzzy, `DictIndex` for exact `string ↔ rank` at 52 % less
  — and `HashedDictIndex` over it where `id` is the hot path, 5.7× to 20× the dictionary's own search
  for 2.6 to 3.2 bytes a key more — `PerfectHashIndex` for `id → key` without ordering; each pays for
  the keys it stores.
- **Is a bounded false-positive rate acceptable?** Then `CompactHashIndex`: 2.4× under `marisa-trie`
  on single words, 4.9× on random pairs, 3.3× at 10 M — and exactly one byte per key above the bare
  `ClosedHashIndex` (1.24 against 0.24), which is the fingerprint that buys the membership check.
- **Do the keys share a lot of structure** (a path namespace, a versioned catalogue, a cross product)?
  Measure before choosing: that is where an FST can beat a keyless hash outright.
- **A `dict` / `HashMap` is not in the table** because it has no serialised form: 71–95 bytes per key
  above the key list across these corpora (58–60 at 10 M), rebuilt from the keys on every process
  start, where every structure here is mapped from a file.

### Point-lookup latency vs the standard library

`cargo run --release --example bench` — 1 M **real dictionary-word bigrams** (`word_i.word_j`, mean
key 10.9 bytes; never a synthetic `entity-000…N` sequence, which arrives pre-sorted and
hash-degenerate). Measured 2026-09-24 at `3a73ed5` (4.4.0), an hour and a half after a reboot, six
runs back to back, each lookup cell the minimum of five passes after a warm-up; the table quotes the
minimum over the six. The six agree within 2 % on `CompactHashIndex`, both `HashedDictIndex` rows
and the `HashMap` control, while `PerfectHashIndex` spreads 6–8 % on one slow pass each and
`DictIndex` 8 % with no trend
([`latency-rs-2026-09-24-arz-3a73ed5.txt`](https://github.com/ilgrad/lexindex/blob/main/bench/results/latency-rs-2026-09-24-arz-3a73ed5.txt)).
Absolute numbers are one machine on one day — the `std::HashMap` control reads 233 ns here against
234 on the 4.1 table, 241 on 4.0, 285 on 3.0.0, 295 on 2.1.0, 289 on 2.0.0 and 245 on 1.1.0 — so
read the **ratios within a column**, and a shift under ~15 % between tables as the session.
`StringIndex` read 1.30–1.47× of that control from 0.5.1 to 4.2 and reads 1.13× since 4.3's reader
of its transducer.

| structure | build | lookup | note |
|---|---|---|---|
| lexindex `PerfectHashIndex::id_unchecked` | ~243 ms | **~49 ns** | closed vocabulary, no membership check |
| lexindex `CompactHashIndex::id` (fp=1) | **~37 ms** | ~57 ns | fingerprint-verified, `2^-8` false-positive rate |
| lexindex `HashedDictIndex::id_unchecked` | ~262 ms | ~62 ns | closed vocabulary; the id is the key's rank, so `key(id)`, prefix and range stay on the same index |
| lexindex `HashedDictIndex::id` (8 bits) | ~268 ms | ~77 ns | fingerprint-checked, `2^-8`; builds are the dictionary's and the sidecar's together |
| lexindex `PerfectHashIndex::id` (verified) | ~228 ms | ~109 ns | one extra cache line + full key compare |
| `std::HashMap<String, u32>` | ~170 ms | ~233 ns | in-RAM, not serialisable |
| lexindex `StringIndex` (FST) | ~241 ms | ~263 ns | *and* prefix / range / fuzzy |
| lexindex `DictIndex` (256 per block) | ~206 ms | ~399 ns | ordered, exact reverse; its worst case — a `word.word` cross product is what a transducer factors out (0.68 B/key against 1.93 here; on the dictionary 2.64 against 5.95, 291–298 ns against 200–210) |
| `std::BTreeMap<String, u32>` | ~195 ms | ~709 ns | in-RAM |

**Reading it:** for a **fixed / closed vocabulary**, `PerfectHashIndex::id_unchecked` is the fastest
structure in the table — 4.7× as quick as the SipHash `HashMap` and 2.9× an FxHash one — *and*
compact and serialisable. `CompactHashIndex::id` keeps a probabilistic membership check and still
beats the `HashMap` 4.1× on lookup, and builds in a fifth of its time. `HashedDictIndex` answers
with ranks — the ids its `DictIndex` gives, which the others cannot — 5.2× as fast as that
dictionary's own `id` at 8 bits and 6.4× closed. Verified `id` pays one
extra cache line and a key compare and is still twice as quick as the `HashMap`; `StringIndex`
trades latency for the queries a hash map cannot answer at all. The other Rust string indexes, the three-corpus table, the Python-level table against `dict`
and `marisa-trie`, the 1 M / 10 M scale table and the protocol behind every number are in
[the benchmarks](https://ilgrad.github.io/lexindex/benchmarks/).

## Security

Every loader is a safe fn on arbitrary bytes since 1.0: a crafted blob answers wrong ids, never
out-of-range ones. The `load_mmap` family is what is `unsafe`, and its obligation is about the file,
not the bytes. The checksums are integrity and not authentication, and the hashes are unseeded, so
this is not a HashDoS defence — the threat model and the supported versions are in
[`SECURITY.md`](https://github.com/ilgrad/lexindex/blob/main/SECURITY.md).

## Sponsoring

If lexindex saves memory or latency in a system you run, consider
[sponsoring its development](https://github.com/sponsors/ilgrad). **Using it in production?**
Corporate sponsorship funds what keeps a library like this dependable — compatibility across Rust
and Python releases, the benchmark suite behind every number above, security hardening of the
loaders, and performance work at hundreds of millions of keys — and tells the maintainer which
workloads to measure next.

**Commercial support and integration work** — a tuning pass on your key distribution, an integration
into your stack, or a support retainer: <ilia.gradina@gmail.com>.

## Used by

Nothing yet that I know of. If lexindex is in something you ship, say so in a
[Discussion](https://github.com/ilgrad/lexindex/discussions) and it goes here — knowing which
workloads are real is what decides what gets measured next.

## Prior art

The minimal perfect hash under the three hash indexes is in-crate and follows **PHast**'s
map-or-bump construction, the successor of PTHash: keys grouped into buckets by a first hash, a
one-byte seed per bucket that slides the bucket's keys along a short slice of the table until every
one lands on a free value, the buckets no seed places *bumped* to a smaller table under a fresh hash,
and a remap that pulls every bumped key into a hole the first table left. Nothing is ever displaced,
which is what makes the build one streaming pass over sorted hashes.

- Giulio Ermanno Pibiri and Roberto Trani, *PTHash: Revisiting FCH Minimal Perfect Hashing*,
  SIGIR 2021 — [arXiv:2104.10402](https://arxiv.org/abs/2104.10402).
- Piotr Beling and Peter Sanders, *PHast — Perfect Hashing with fast evaluation*, 2025 —
  [arXiv:2504.17918](https://arxiv.org/abs/2504.17918).
- Ragnar Groot Koerkamp, *PtrHash: Minimal Perfect Hashing at RAM Throughput*, 2025 —
  [arXiv:2502.15539](https://arxiv.org/abs/2502.15539),
  [`ptr_hash`](https://github.com/RagnarGrootKoerkamp/PtrHash).

Until 1.0 the perfect hash **was** `ptr_hash`. Its pilot table was serialised behind private fields,
so a blob holding one could not be validated from outside the crate that owned it, and `from_bytes`
and `load_mmap` had to be `unsafe fn` on both hash indexes; an MPH whose every array length is
written and checked here makes those loaders safe, and that is the whole of the trade. The
`MPH3` table builds 10 M keys in **38 ns/key on one thread** (11 ns/key on eight) at
**1.92 bits/key**, against 280 ns/key and 2.39 bits for 1.0's, and answers a lookup in 2.6 ns,
2.5 in a batch; the same-process comparison with `ptr_hash` and the PHast authors'
`ph` crate is [in the benchmarks](https://ilgrad.github.io/lexindex/benchmarks/#the-perfect-hash-against-ptrhash-and-phast).

## License

MIT © Ilia Gradina

