beowolx/rensa

해결하는 문제

Rensa는 모든 문서 쌍을 비교할 필요 없이 대규모 데이터셋에서 근사 중복 문서를 빠르게 찾는 고성능 방법을 제공합니다. 계산 비용이 큰 중복 제거 문제를 해결하기 위해 컴팩트한 서명과 근접성 감지 해싱(Locality-Sensitive Hashing, LSH)을 사용하여 자카르 유사도를 추정합니다.

작동 방식

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배 빠릅니다.
• 컴팩트한 서명: 슬롯당 32비트를 사용하므로, 128슬롯 서명은 문서 길이와 관계없이 단지 512바이트만 차지합니다.
• 유연한 처리: 배치 처리와 스트리밍 중복 제거를 모두 지원합니다.
• 증분 업데이트: 전체 문서를 다시 처리하지 않고도 스케치를 증분적으로 업데이트할 수 있습니다.