Ribbon filters for Python: a static set-membership filter that never misses a key it was built from, and is wrong about any
other key with a probability you choose (2**-fp_bits), in fewer bits per key than a Bloom filter. Written in C11 with no
Python dependencies. Licensed MIT.
pip install pyribbonPython 3.10 or newer, from PyPI. Prebuilt wheels cover Linux (x86-64 and ARM, glibc and musl), macOS (Intel and Apple silicon) and Windows (x64), including the free-threaded builds of Python 3.14 and 3.15. On any other platform pip builds the source distribution, and a C compiler is the only build requirement.
from pyribbon import RibbonFilter
f = RibbonFilter(["alice", "bob", "carol"], fp_bits=12) # a wrong "yes" about once in 2**12 lookups
assert "alice" in f # a member is always found
assert "mallory" not in f # this non-member was rejected; one in 2**12 would slip through
assert f.contains_many(["alice", "mallory"]) == [True, False] # one answer per keyKeys can be bytes, str or int. RibbonFilter(keys, width=Width.W128) builds a filter 4% to 8% smaller, in 1.2 to 1.5 times the build time and with slower queries. A filter built from a list, an array.array or a numpy array of integers answers a whole
batch with contains_many. Save one with f.to_bytes() and load it back with RibbonFilter.from_buffer(data), which
reads the bytes where they are without copying them. Eight runnable scripts in
examples/ start with 01_quickstart.py.
The false-positive rate is 2**-fp_bits, with fp_bits from 1 to 32 (default 8). Measured at 1,000,000 keys, the 64-byte
header included. Bits per key is a decimal because the filter has about 12% more rows than keys, so its size divided by the
number of keys is not a whole number. A Bloom filter needs 1.44 * fp_bits bits per key.
fp_bits |
false-positive rate | bits per key |
|---|---|---|
| 1 | 50% | 1.12 |
| 2 | 25% | 2.25 |
| 4 | 6.25% | 4.50 |
| 6 | 1.6% | 6.75 |
| 8 | 0.39% | 8.99 |
| 10 | 0.098% | 11.24 |
| 12 | 0.024% | 13.49 |
| 16 | 0.0015% | 17.99 |
| 20 | 0.000095% | 22.48 |
| 24 | 0.0000060% | 26.98 |
| 28 | 0.00000037% | 31.48 |
| 32 | 0.000000023% | 35.97 |
Space, build time and lookup time against the number of keys, on one machine (an i7-7700, CPython 3.14, pinned to one core)
against pyfusefilter and rbloom. Lower is better in every panel. One machine, one run.
The largest size, against the best other filter of the same fingerprint width:
Where pyribbon wins and loses (int keys, n = 10,000,000):
| Class | Metric | pyribbon | Best other | Delta | Verdict |
|---|---|---|---|---|---|
| 8-bit | bits/key | 9.19 | 9.02 (Fuse8) | +2% | pyribbon behind |
| 8-bit | bits/key above log2(1/FPR) | 1.18 | 1.00 (Fuse8) | +17% | pyribbon behind |
| 8-bit | build ns/key | 78 | 203 (rbloom 2^-8, builtin hash()) | -62% | pyribbon ahead |
| 8-bit | in member ns |
91 | 213 (rbloom 2^-8, builtin hash()) | -57% | pyribbon ahead |
| 8-bit | in non-member ns |
94 | 139 (rbloom 2^-8, builtin hash()) | -33% | pyribbon ahead |
| 8-bit | batch Mkeys/s (50/50 mix) | 20.92 | 5.48 (rbloom 2^-8, builtin hash()) | +281% | pyribbon ahead |
| 16-bit | bits/key | 18.39 | 18.04 (Fuse16) | +2% | pyribbon behind |
| 16-bit | bits/key above log2(1/FPR) | 2.36 | 1.95 (Fuse16) | +21% | pyribbon behind |
| 16-bit | build ns/key | 93 | 423 (rbloom 2^-16, builtin hash()) | -78% | pyribbon ahead |
| 16-bit | in member ns |
131 | 411 (rbloom 2^-16, builtin hash()) | -68% | pyribbon ahead |
| 16-bit | in non-member ns |
109 | 162 (rbloom 2^-16, builtin hash()) | -33% | pyribbon ahead |
| 16-bit | batch Mkeys/s (50/50 mix) | 12.24 | 3.40 (rbloom 2^-16, builtin hash()) | +260% | pyribbon ahead |
Delta is relative to the best other filter of the same fingerprint class, including rbloom with its builtin hash(); a negative delta means pyribbon is lower. Lower is better except for batch throughput. The 'above log2(1/FPR)' rows move with the measured FPR, whose uncertainty is in the notes. The batch row compares contains_many with the other libraries' per-key loop, because none of them has a batch API. The table is computed from the raw results of this run.
Everything else is in docs/: the usage guide, the API reference, the limits, how it works, the internals (hashing, the file format, the C core) and the full performance numbers by number of keys. The C core builds and tests on its own: see core/README.md. To work on pyribbon, read CONTRIBUTING.md. To report a vulnerability, read SECURITY.md.
pyribbon is MIT licensed (LICENSE). The vendored xxHash header (core/vendor/xxhash.h) is BSD 2-Clause
(LICENSES/). The algorithm is by Peter C. Dillinger and Stefan Walzer, in
"Ribbon filter: practically smaller than Bloom and Xor" (arXiv:2103.02515). This implementation was written from their papers,
not from existing code.
