在 Rust 中实现高性能的 MinHash 实现,并使用 Python 绑定,以便高效地估计大型数据集的相似性并去重
Rensa is a MinHash library written in Rust with Python bindings. It estimates Jaccard similarity from compact signatures and finds near-duplicate documents using locality-sensitive hashing (LSH). Rensa supports batch and streaming deduplication on Linux, macOS and Windows. Try it in Maxime Labonne's AutoDedup notebook.
Rensa's rho batch pipeline averaged 600× faster than Datasketch and 12× faster than FastSketch.
| Comparison | Average speedup |
|---|---|
| Rensa vs. Datasketch | 608.52× faster |
| Rensa vs. FastSketch | 11.92× faster |
The benchmark measures sketch construction and duplicate detection together across seven datasets, using 128 signature slots, eight LSH bands, a 0.8 threshold, and both one-thread and eight-thread runs. It uses Rensa's rho pipeline, which samples token positions to increase throughput. The performance section explains how that differs from full-set MinHash.
RMinHashDeduplicator finds candidate matches and
checks their estimated similarity against your threshold.Rensa provides full-set R-MinHash and C-MinHash for similarity estimation, along with a separate rho pipeline for faster bulk filtering. Choose full-set R-MinHash when token order should have no effect on the result. Rho samples token positions, so document length and token order affect which duplicates it finds.
Yes, by a wide margin in the batch benchmarks: about 600× faster than Datasketch and 12× faster than FastSketch on average. These results measure the complete rho batch pipeline, from sketch construction to duplicate detection.
Rensa is fast because:
rustc_hash::FxHasher without trait dispatch in the hot path, and prehashed
input skips token hashing altogether.(num_perm, seed) share
fallback parameters and their SIMD layouts. Short-input paths keep scratch
space on the stack, and standard builds use mimalloc for heap allocation.The rho pipeline samples token positions for bulk filtering. Full-set R-MinHash uses every token and gives the same signature when tokens are reordered or repeated. The accuracy benchmark checks estimation error and retrieval against exact Jaccard, including pairs whose tokens have been reordered.
Rensa also implements a practical variant of C-MinHash, using two seeded nonlinear permutations and 64-bit signature slots. Its streaming deduplicator indexes candidate signatures and stops comparing a pair as soon as it cannot meet the threshold.
If you'd like to try Rensa before installing it, Maxime Labonne created an AutoDedup notebook that runs in Google Colab.
Choose a Hugging Face dataset, the column to deduplicate, a split and the MinHash implementation, then run the notebook. It reports how many rows remain and shows removed samples alongside the records they matched, so you can inspect what the deduplicator considered a duplicate.
uv add rensaUpgrading from 0.4.x or earlier: Rensa 0.5.0 uses algorithm version 2 for R-MinHash and C-MinHash. Rebuild saved signatures, digest matrices and LSH indexes from the original tokens. Old serialized sketches and indexes are rejected; do not compare or combine raw digests from different algorithm versions.
from rensa import RMinHash
first, second = RMinHash.from_token_sets(
["the quick brown fox".split(), "the quick brown dog".split()],
num_perm=128,
seed=42,
)
print(first.jaccard(second))Use update(tokens) to extend a sketch incrementally. CMinHash supports the
same similarity interface.
from rensa import RMinHashDeduplicator
documents = [
"select id from users",
"select name from orders",
"select id from users",
]
dedup = RMinHashDeduplicator(threshold=0.8, num_perm=128, use_lsh=True)
keep = dedup.add_pairs(
(str(i), text.split()) for i, text in enumerate(documents)
)
print(keep) # [True, True, False]The deduplicator keeps its index across calls, so the same API works for batches and streams. LSH candidate retrieval is approximate; the deduplicator checks candidates against the sketch similarity threshold.
暂无开放 Issues,或尚未同步最近议题。