한양과기고 에듀테크 수업도구 대시보드

MinHash — 큰 문서도 짧은 지문으로 닮은꼴 찾기

웹에는 거의 똑같은 페이지가 수억 개 떠 있다. 두 문서가 얼마나 겹치는지 재는 정확한 척도는 자카드 유사도 |A∩B| / |A∪B| 지만, 문서마다 단어 집합을 통째로 비교하면 너무 느리다. MinHash 는 각 문서를 수백 개의 작은 정수(시그니처)로 압축해 두고, 시그니처가 일치하는 비율만으로 자카드 유사도를 추정한다. 구글의 중복 페이지 제거, 표절 검사기, LLM 학습 데이터 중복 제거에 실제로 쓰인다.

1. 두 문서 & 슁글(shingle)로 자르기

문서 A

문서 B

슁글 크기

슁글 = 이어지는 단어 2개 묶음. 문서를 슁글 집합으로 바꾸면 순서·중복이 사라지고 "어떤 조각들로 이루어졌는가"만 남는다. ■ 교집합 ■ A에만 ■ B에만

2. 정확한 자카드 유사도 (느린 기준값)

∩

–

교집합 |A∩B|

–

합집합 |A∪B|

–

자카드 = ∩ / ∪

3. MinHash 시그니처 & 일치율

해시 함수 hᵢ(x) = (aᵢ·x + bᵢ) mod p 하나가 슁글들을 뒤섞는다. 각 문서에 대해 그 함수값이 가장 작은 슁글의 해시값을 기록한 것이 시그니처의 한 칸이다. 아래는 처음 12개 함수의 결과 — 초록 행은 A·B가 같은 값이 나온 칸이다.

–

추정 유사도 = 일치 칸 / 전체 칸

–

실제 자카드 (2번)

–

오차 |추정 − 실제|

해시 함수 개수 200

4. 함수를 늘릴수록 추정이 정답에 수렴한다

파란 선 = 앞에서부터 k개 함수만 썼을 때의 추정값. 초록 점선 = 실제 자카드 유사도. 함수 개수 n에서 추정 오차의 표준편차는 대략 √(J(1−J)/n) — 정밀도를 2배로 올리려면 함수를 4배 늘려야 한다.

5. 알고리즘 (의사코드)

# 준비: n개의 해시 함수 hᵢ(x) = (aᵢ·x + bᵢ) mod p (p는 큰 소수) def signature(doc): shingles = { hash(s) for s in k_shingles(doc) } # 슁글 집합 → 정수 집합 sig = [] for i in range(n): sig.append( min( hᵢ(x) for x in shingles ) ) # i번째 함수의 최솟값 return sig # 두 문서의 유사도 추정: 시그니처가 같은 칸의 비율 def similarity(a, b): sa, sb = signature(a), signature(b) return mean( sa[i] == sb[i] for i in range(n) ) # ≈ |A∩B| / |A∪B|

6. 왜 "최솟값이 같을 확률"이 곧 자카드일까?

최솟값은 공평한 제비뽑기

해시 함수는 A∪B 의 원소들을 무작위로 줄 세운다. 이때 맨 앞에 서는 원소는 합집합의 어떤 원소든 될 확률이 똑같다. A와 B의 시그니처 칸이 같으려면 그 1등 원소가 교집합에 속해야 한다.

P(일치) = |A∩B| / |A∪B|

1등이 교집합 원소일 확률 = 교집합 크기 / 합집합 크기 = 바로 자카드 유사도. 그래서 함수 n개 중 일치한 칸의 비율이 자카드의 불편추정량이 된다.

크기가 고정된 지문

문서가 1KB든 1MB든 시그니처는 항상 n개 정수. 원문을 버리고 지문만 저장·비교하면 되므로 수억 문서 쌍도 감당할 수 있다. 정확도는 n으로 조절한다.

LSH 밴딩으로 후보만 추리기

시그니처를 b개 밴드(각 r행)로 쪼개, 한 밴드라도 통째로 같은 문서쌍만 후보로 본다. 임계값 ≈ (1/b)^1/r 근처에서 S자 곡선으로 걸러져, 모든 쌍을 비교하지 않고도 닮은꼴을 찾는다.

1997년 Andrei Broder(AltaVista)가 웹 중복 페이지 제거를 위해 고안 — "syntactic clustering of the web".