도구스개발

MinHash 서명 크기·오차 계산기

해시 개수 k에서 자카드 유사도 추정의 표준오차 √(J(1−J)/k)와 서명 메모리를 계산하고, 목표 오차에 필요한 k를 거꾸로 찾습니다. 밴드 나누기(LSH)의 S곡선과 임계 유사도도 함께 내어 b·r을 고를 수 있습니다.

개

서명 하나에 담는 최솟값 해시의 개수입니다. 그대로 서명 길이가 됩니다.

추정하려는 두 문서의 참값입니다. 오차는 J = 0.5에서 가장 큽니다.

개

서명을 몇 벌 보관할지입니다. 메모리 총량과 짝 개수를 셈하는 데만 씁니다.

해시 100개로 잰 자카드 유사도의 오차

±5%p

표준오차 √(J(1−J)/k)입니다. 95% 구간으로는 0.402 ~ 0.598 사이로 나옵니다. 이 오차를 절반으로 줄이려면 해시가 400개, 곧 네 배 듭니다.

표준오차 SE0.05
95% 신뢰구간0.402 ~ 0.598
서명 하나 크기400B
문서 전체 서명381.47MB
오차 절반에 필요한 해시400개
모든 짝을 견주면499,999,500,000쌍
해시 하나가 하는 일은 「두 서명의 그 자리가 같으냐」는 동전 던지기 한 번입니다. 합집합에서 맨 앞에 온 원소가 하필 교집합에 속할 확률이 정확히 자카드 유사도라서, 앞면이 나올 확률이 J가 됩니다. 그래서 같았던 개수가 이항분포를 따르고 표준오차가 √(J(1−J)/k)입니다. J가 0.5일 때 J(1−J)가 0.25로 가장 크므로, 유사도를 모른 채 크기를 잡아야 하면 이 최악의 경우로 잡으면 됩니다.

해시를 네 배씩 늘리면

해시 수표준오차95% 반폭서명 크기
16개0.125±24.5%p64B
64개0.0625±12.25%p256B
256개0.03125±6.13%p1KB
1,024개0.01563±3.06%p4KB
4,096개0.00781±1.53%p16KB
16,384개0.00391±0.77%p64KB

오차가 1/√k로만 줍니다. 정확도를 두 배로 올리려면 해시가 네 배, 메모리도 네 배입니다. HyperLogLog가 레지스터를 네 배 늘려야 오차가 절반이 되는 것과 같은 성질로, 표본으로 무엇을 재든 벗어날 수 없는 한계입니다.

이 오차를 지키는 가장 작은 해시 개수를 거꾸로 찾습니다.

J = 0.5에서 필요한 해시625개
J를 모를 때 (최악인 0.5로)625개
그때 서명 하나 크기2.44KB
줄

해시 k개를 b개 밴드 × r줄로 자릅니다. k의 약수로 맞춰집니다.

밴드 나누기20밴드 × 5줄
근사 임계값 (1/b)^(1/r)0.5493
그 지점에서 후보가 될 확률64.2%
확률이 정확히 50%가 되는 유사도0.5087
J = 0.5이 후보로 오를 확률47.01%

S곡선 — 유사도별 후보가 될 확률

자카드 유사도후보 확률　
0.20.64%
0.34.75%
0.418.6%
0.547.01%
0.680.19%
0.797.48%
0.899.96%
0.9100%

한 밴드가 통째로 같을 확률이 Jr이므로, 한 밴드라도 같아 후보로 오를 확률은 1 − (1 − Jr)b입니다. 이 곡선이 임계값 근처에서 급하게 꺾이는 덕분에 모든 짝 499,999,500,000쌍을 견주는 대신 후보로 오른 것만 견주면 됩니다.

흔히 쓰는 임계값 (1/b)1/r은 「반이 걸러지는 지점」이 아닙니다. 이 값을 식에 도로 넣으면 tr = 1/b라 r이 통째로 사라지고 1 − (1 − 1/b)b만 남는데, b가 2면 75%, b가 커지면 1 − 1/e = 63.2%로 내려갈 뿐 늘 6~7할입니다. 지금 설정에서도 64.2%이고, 확률이 정확히 절반이 되는 곳은 0.5087입니다. 이걸 반값으로 알고 b, r을 고르면 헛걸음이 생각보다 많아집니다.
밴드를 늘리면(줄이 줄면) 임계값이 내려가 놓치는 것은 줄지만 헛걸음이 늘고, 줄을 늘리면 반대가 됩니다. 어느 쪽도 공짜가 아니므로, 놓치는 쪽이 아까운 일(중복 제거)에는 밴드를 늘리고 헛걸음이 비싼 일(사람이 확인해야 하는 심사)에는 줄을 늘리는 식으로 고릅니다. 위 칩에서 b×r을 바꿔 가며 곡선이 어디서 꺾이는지 보면 고르기 쉽습니다.
여기 나오는 오차는 해시를 서로 독립인 무작위 순열로 볼 때의 값입니다. 실제 구현은 순열 대신 a·x + b mod p 꼴의 해시 함수를 k개 돌려 쓰는 경우가 많은데, 이들은 서로 완전히 독립이 아니라서 실측 오차가 조금 더 큽니다. 여기 수치는 「이보다 잘 나오기는 어렵다」는 기준선으로 보는 것이 안전합니다.

사용 방법

  1. 1해시 개수 k를 넣습니다. 그대로 서명 길이가 됩니다.
  2. 2재려는 두 문서의 실제 자카드 유사도 J를 넣습니다. 모르면 오차가 가장 큰 0.5로 둡니다.
  3. 3해시 하나를 몇 비트로 담을지, 문서가 몇 개인지 넣으면 메모리 총량이 나옵니다.
  4. 4목표 표준오차를 넣으면 그것을 지키는 가장 작은 해시 개수가 거꾸로 나옵니다.
  5. 5밴드 한 개의 줄 수 r을 고르면 b×r로 갈라져 S곡선과 임계 유사도가 나옵니다.

자주 묻는 질문

표준오차는 √(J(1−J)/k)이며, J는 실제 자카드 유사도, k는 해시 개수입니다. 해시 하나가 「두 서명의 그 자리가 같으냐」는 동전 던지기 한 번이고 앞면이 나올 확률이 정확히 J라서, 같았던 개수가 이항분포 B(k, J)를 따르기 때문입니다. k = 100이고 J = 0.5면 표준오차가 0.05로, 95% 구간이 0.402~0.598입니다.

목표 표준오차를 SE라 하면 k = J(1−J) ÷ SE²입니다. J를 모르면 오차가 가장 큰 J = 0.5로 잡아 k = 0.25 ÷ SE²이며, 오차 1%를 원하면 2500개, 5%면 100개입니다. 문헌에서 흔히 보이는 k = 100~200은 오차 3~5% 수준이고, 중복 문서 걸러내기처럼 유사도의 정확한 값보다 순위가 중요한 일에는 대개 이 정도면 충분합니다.

네 배가 듭니다. 오차가 1/√k로만 줄기 때문에 k를 네 배로 늘려야 √4 = 2배 정확해집니다. 메모리도 그대로 네 배입니다. HyperLogLog가 레지스터를 네 배 늘려야 오차가 절반이 되는 것과 같은 성질로, 표본으로 무엇을 재든 벗어날 수 없는 한계입니다.

한 밴드라도 통째로 같아 후보로 오를 확률이 1 − (1 − J^r)^b이므로, 이 곡선이 원하는 유사도에서 꺾이도록 b와 r을 고릅니다. 임계 유사도는 대략 (1/b)^(1/r)이고, 밴드를 늘리면(줄이 줄면) 임계값이 내려가 놓치는 것은 줄지만 헛걸음이 늘어납니다. 놓치는 쪽이 아까운 일에는 밴드를, 헛걸음이 비싼 일에는 줄을 늘립니다.

아닙니다. 그 지점에서는 이미 63~75%가 후보로 올라옵니다. 임계값을 식에 도로 넣으면 t^r = 1/b라 r이 통째로 사라지고 1 − (1 − 1/b)^b만 남는데, b = 2면 75%, b가 커지면 1 − 1/e = 63.2%로 내려갈 뿐 늘 6~7할입니다. 반값 지점으로 알고 b와 r을 고르면 후보가 예상보다 많이 올라옵니다.

해시 하나를 32비트로 담으면 문서 하나가 k × 4바이트입니다. k = 100이면 400바이트라, 문서 100만 개의 서명이 400MB입니다. 원문이나 슁글 집합을 그대로 들고 있는 것에 비하면 훨씬 가볍고, 문서 길이와 무관하게 이 크기로 고정된다는 것이 요점입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.

알아두면 좋은 점

  • LSH 후보 확률은 Leskovec·Rajaraman·Ullman의 "Mining of Massive Datasets" 3.4.2에 실린 표(해시 100개를 20밴드 × 5줄로 나눈 경우)와 대조해 맞췄습니다. 유사도 0.2에서 0.006, 0.5에서 0.470, 0.8에서 0.9996까지 소수 셋째 자리로 일치하고, 같은 절에 나오는 임계값 0.5493도 확인했습니다.
  • 임계값 (1/b)^(1/r)에서의 후보 확률이 r과 무관하게 1 − (1 − 1/b)^b가 되는 것을 b와 r을 바꿔 가며 확인했습니다. 이 값이 0.632~0.75 범위에 머물러 늘 절반보다 크다는 것, 곧 근사 임계값이 곡선의 반값 지점보다 오른쪽에 선다는 것도 함께 고정했습니다.
  • 표준오차는 이항분포 B(k, J)의 표본비율 표준오차입니다. 해시를 네 배 늘리면 정확히 절반이 되는 것, J = 0.5에서 최대가 되는 것, 목표 오차로 찾은 k가 목표를 지키고 k−1은 못 지키는 것을 테스트로 고정했습니다.
  • 해시를 서로 독립인 무작위 순열로 볼 때의 값입니다. 실제 구현은 a·x + b mod p 꼴의 해시 함수를 k개 돌려 쓰는 경우가 많고 이들은 완전히 독립이 아니라, 실측 오차는 여기 값보다 조금 큽니다. 기준선으로 보는 것이 안전합니다.
  • 밴드 나누기는 k를 b × r로 정확히 갈라야 하므로, 입력한 줄 수가 k의 약수가 아니면 가장 가까운 약수로 맞춥니다.
  • 자카드 유사도 자체를 문자열에서 재려면 텍스트 유사도 계산기를 함께 쓰면 됩니다. 이 계산기는 유사도를 «어떤 크기로 근사할 것인가»만 다룹니다.

함께 보면 좋은 도구

HyperLogLog정밀도 p에서 HyperLogLog의 레지스터 수·표준오차·메모리를 계산하고, 목표 오차에 필요한 p를 거꾸로 찾습니다.블룸 필터원소 수와 목표 오탐률을 넣으면 필요한 비트 배열 크기와 해시 함수 개수를 계산합니다.유사도 비교두 글이 얼마나 비슷한지 편집거리와 단어 겹침으로 각각 점수를 냅니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.

마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.