<aside> ⚡

TL;DR: 이메일 중복 제거에는 MinHash + LSH를 선택했다.

1. 이메일 중복은 템플릿/포워딩에 의한 문자열 근사 중복이 대부분 → Exact Hash, SemDeDup 탈락, 문자열 근사 비교 알고리즘으로 좁혀짐
2. Suffix Array는 연속 구간 완전 일치 방식이라 가변 값이 곳곳에 끼는 템플릿 메일에는 최소 일치 길이 L을 하나로 고정할 수 없어 배제
3. Simhash는 짧은 문서에서 끝부분 3글자만 달라도 해밍 거리 15로 중복을 놓침 (실험 검증). 원래 수백~수천 단어의 웹 페이지용으로 설계된 알고리즘
4. MinHash는 같은 케이스에서 Jaccard 0.77로 threshold 조절을 통해 탐지 가능. 0.85~0.95 사이를 세밀하게 튜닝할 수 있고, 유사도가 0~1 연속값이라 해석이 직관적
5. Simhash는 수십억 개의 긴 웹 페이지에서 거의 복사 수준의 중복을 탐지할 때 유리 (64비트/문서, O(1) 비교) → 이메일 시나리오와는 부적합 </aside>

배경

herc-prep 프로젝트에서는 EML 이메일 데이터의 중복을 제거하여 학습 데이터 품질을 확보해야 한다. 다양한 중복 제거 알고리즘 중 MinHash + LSH를 선택한 근거를 정리한다.

중복 제거 알고리즘 전체 비교

선택 사유

1. 이메일 데이터 특성과의 적합성

<aside> 📧

이메일 중복의 특징:

• 포워딩 시 헤더가 바뀌지만 본문은 거의 동일 → Exact Hash로는 못 잡음
• 서명/면책조항 차이로 완전 동일이 아닌 근사 중복이 대부분
• 템플릿 기반 발송(알림, 마케팅, 자동 응답 등)이 중복의 주요 원인 → "의미적으로 비슷한" 것이 아니라 문자열 자체가 거의 동일 (수신자/날짜만 다름)
• 따라서 임베딩 기반 의미적 유사도가 아닌 문자열 근사 비교가 더 적합 </aside>

이와 같은 이유로 Exact Hash(완전 일치만 탐지)와 SemDeDup(의미적 유사도 기준)은 탈락한다.

2. Suffix Array 배제 사유

Suffix Array는 코퍼스 전체에서 길이 L 이상 완전히 일치하는 연속 구간을 찾는 방식이다. 이러한 특성으로 인해 동일한 템플릿 메일을 제거하려는 목적과는 맞지 않아서 배제되었다.

• 템플릿 메일은 가변 값(수신자, 날짜, 금액 등)을 제외하면 순서까지 일치하지만, 가변 값이 낄 때마다 연속 일치 구간이 끊긴다. Suffix Array는 이를 하나의 긴 일치가 아니라 짧은 일치 여러 개로 본다.
• 최소 일치 길이 L은 직접 지정해야 하는데, 템플릿 종류가 많고 가변 값의 위치에 따라 고정 구간 길이가 템플릿마다 달라 전체를 커버하는 L을 하나로 고정하는 것이 사실상 불가능하다. L을 낮추면 흔한 인사말로 무관한 메일이 묶이고, 높이면 템플릿을 놓친다.
• 반면 MinHash는 순서를 버리고 n-gram 조각 집합의 겹침 비율(Jaccard)을 보기 때문에 가변 값이 어디에 몇 개 끼든 주변 조각만 달라지고 나머지는 겹친다. 고정 구간 길이와 무관하게 threshold 하나로 판정할 수 있다.

정리하면 Suffix Array는 연속된 순서 그대로 일치해야 하고, MinHash는 순서를 버리고 조각의 집합만 비교한다. 템플릿 메일 중복에는 후자가 맞는 기준이므로 Suffix Array도 배제한다. 따라서 문자열 근사 비교 알고리즘인 Simhash와 MinHash + LSH 두 가지로 좁혀졌다.

3. Simhash vs MinHash + LSH 비교

두 알고리즘 모두 문자열 근사 비교에 적합하지만, 임계값 조절 정밀도와 유사도 해석 용이성에서 결정적 차이가 있다.