beowolx/rensa

何を解決するか

Rensaは、すべての文書ペアを比較する必要なく、大規模なデータセット内の類似した重複文書を高速に検出する方法を提供します。計算コストの高い重複除去問題を、コンパクトなシグネチャと局所性に敏感なハッシュ（LSH）を用いたJaccard類似度の推定により解決します。

動作方法

Rustで記述され、Pythonバインディングを備えるRensaは、いくつかのMinHashバリエーションを実装しています。

• R-MinHashとC-MinHash：これらの手法はトークンの重複に基づいて類似度を推定します。R-MinHashは高速性を重視しており、トークンの順序や重複に関係なく同じシグネチャを生成します。
• Rhoパイプライン：バッチフィルタリングの最大スループットを実現するために、トークンの位置をサンプリングする専用パイプラインです。
• LSH（局所性に敏感なハッシュ）：この手法により、候補となるマッチを迅速に特定でき、その後類似度閾値と照合することで、全組み合わせの比較を回避できます。
• パフォーマンス最適化：SIMD（AVX2、AVX-512、NEON）を活用して計算を高速化し、PythonからRustへのオーバーヘッドを最小限に抑え、Rayonを用いてマルチスレッドでのバッチ処理を実現しています。

対象ユーザー

大規模なコーパスから類似した重複テキストデータを除去したい開発者やデータサイエンティスト。特にPythonで既にトークン化を行っているユーザーで、Datasketchなどの既存ライブラリよりもはるかに高速なツールを必要としている方々です。

特徴

• 極めて高速：バッチパイプラインにおいて、Datasketchの600倍、FastSketchの12倍の速度を達成しているとベンチマークされています。
• コンパクトなシグネチャ：1スロットあたり32ビットを使用するため、128スロットのシグネチャは文書長に関係なく512バイトで済みます。
• 柔軟な処理：バッチ処理とストリーミングでの重複除去の両方をサポートしています。
• インクリメンタルな更新：完全な文書の再処理なしに、スケッチをインクリメンタルに更新できます。