百科.dev
全部条目在线工具AI 编程趋势榜开源项目技术资讯提交条目
登录
< 返回工具列表
R

rensa

> 编程语言
开源

在 Rust 中实现高性能的 MinHash 实现,并使用 Python 绑定,以便高效地估计大型数据集的相似性并去重

373 stars0 点赞1 次浏览
访问官网GitHub

工具介绍

在 Rust 中实现高性能的 MinHash 实现,并使用 Python 绑定,以便高效地估计大型数据集的相似性并去重

Rensa

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.

Contents

  • Quick comparison with other tools
  • Why should I use Rensa?
  • Why shouldn't I use Rensa?
  • Is it really faster than everything else?
  • Playground
  • Installation
  • Usage

Quick comparison with other tools

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.

Why should I use Rensa?

  • You want to find near-duplicates in a dataset without comparing every pair of documents. With LSH enabled, RMinHashDeduplicator finds candidate matches and checks their estimated similarity against your threshold.
  • You want to process a batch or keep filtering documents as they arrive. The batch APIs build sketches from token lists in one call; streaming deduplicators retain their indexes between calls.
  • You need compact signatures. R-MinHash uses 32 bits per slot, so a 128-slot signature occupies 512 bytes, excluding object overhead. The signature stays the same size as the document grows.
  • You need to update a sketch incrementally. Full-set R-MinHash gives the same signature when tokens are reordered, repeated or split across updates.
  • You already tokenize your data in Python. Rensa accepts token iterables, including strings and bytes, and provides prehashed input APIs when you want to reuse token hashes.

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.

Why shouldn't I use Rensa?

  • You need exact similarity or guaranteed duplicate detection. MinHash estimates similarity, and LSH can miss matching pairs. Use exact set comparisons if those errors are unacceptable.
  • You need semantic similarity. Rensa compares token overlap. Two paraphrases can mean the same thing and share very few tokens.
  • You need other sketches, such as Weighted MinHash or HyperLogLog. Datasketch supports both.
  • You have a workload where another implementation is faster. Document size, signature size and how much work you send through each Python call all matter. If Rensa is unexpectedly slow, please open an issue with a small reproducer.

Is it really faster than everything else?

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:

  • Fewer hash evaluations. Classical MinHash evaluates a hash function for every signature slot for each token. R-MinHash adapts Fast Similarity Sketching: each token chooses a slot and rank in up to three seeded bucket rounds. Only slots still empty after those rounds need their own fallback hash over all tokens. Dense inputs can fill every slot during the bucket rounds and skip fallback entirely.
  • Skipping updates that cannot change the result. For sufficiently long, dense inputs with power-of-two signature sizes, small signature values establish an upper bound. R-MinHash can then discard updates that cannot improve any slot and skip later rounds. It produces the same signature as processing the full token set.
  • SIMD where it pays off. Runtime dispatch selects NEON, AVX2 or AVX-512 kernels when available. A few empty slots are handled directly; larger fallback sets use SIMD batches. Some conditional bucket loops remain scalar because scattering vector results would cost more than it saves.
  • Less work at the Python boundary. A CPython fast path reads compact ASCII strings directly. Specialized list and tuple paths avoid temporary Rust strings and a Python call for every token. Token hashing matches rustc_hash::FxHasher without trait dispatch in the hot path, and prehashed input skips token hashing altogether.
  • Less repeated setup. Sketches with the same (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.
  • Batch processing in Rust. Batch APIs write contiguous signature matrices and can distribute large batches across Rayon workers. Native LSH processes a whole matrix in one call, avoiding a Python sketch object and query call for each document.

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.

Playground

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.

Installation

bash
uv add rensa

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

Usage

Estimate similarity

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

Keep unique documents

python
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· 0 开放

查看全部 Issues在 GitHub 打开

暂无开放 Issues,或尚未同步最近议题。

> 标签

Rustminhashminhash-similarity

暂无评论,来聊聊你的看法吧

> 工具信息

发布日期2026年8月1日
最后更新2026年9月17日
分类编程语言
定价开源

> 相关工具

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言