beowolx/rensa

解決的問題

Rensa 提供了一種高性能的方法，用於估算大型資料集之間的相似性並識別近似重複文件。它被設計為 datasketch 和 FastSketch 等現有庫在大規模去重任務中的顯著更快替代方案。

工作原理

Rensa 實作了 MinHash，這是一種使用隨機哈希函數創建集合緊湊「簽名」的技術。兩個簽名之間匹配槽位的比例可估算原始集合的 Jaccard 相似度。

Rensa 提供兩種變體：

• R-MinHash：一種自訂變體，使用乘法-移位哈希（取 64 位乘加運算的高 32 位）而非模運算，從而減少 CPU 開銷和記憶體使用。
• C-MinHash：基於正式論文，該變體採用兩階段方案，從更小的參數集中推導出多個槽位，提供更緊的變異數邊界。

此專案使用 Rust 編寫，並附帶 Python 綁定，並採用多種底層優化，包括非加密哈希、元素批量處理以及使用 MiMalloc 分配器更高效地管理記憶體。

適用對象

需要在標準 Python 實作過於緩慢的大規模資料集上執行近似重複檢測或相似性估算的資料工程師與機器學習實務者。

主要亮點

• 極致速度：基準測試顯示，比 datasketch 快高達 608 倍，比 FastSketch 快 11 倍。
• 記憶體高效：R-MinHash 簽名使用 32 位整數，相比 64 位實作，記憶體需求減半。
• LSH 集成：內建局部敏感哈希（LSH），無需比較每對即可高效查詢候選項目。
• 串流支援：內建去重器，支援連續資料流處理。
• 靈活 API：支援一次性批量處理與增量更新。