SimHash 지문·해밍거리 계산기

문서를 64비트 지문 하나로 줄여 닮음을 재는 방법입니다. 문서를 토막으로 쪼개 토막마다 해시를 내고, 비트 자리마다 1이면 +가중치, 0이면 −가중치를 더한 뒤 부호만 남겨 지문을 만듭니다. 닮은 문서는 지문도 닮으므로 다른 비트의 개수(해밍 거리)로 비슷한 정도를 잽니다.

MinHash는 자카드 유사도를, SimHash는 코사인 유사도를 잽니다. SimHash는 가중치를 부호로 더해 비트를 정하므로 자주 나오는 낱말이 지문을 더 세게 끌어당깁니다. 「어떤 낱말이 들어 있느냐」가 아니라 「어떤 낱말이 얼마나 자주 나오느냐」로 닮음을 보는 셈이라, 같은 낱말을 쓰지만 빈도가 다른 두 글을 다르게 봅니다.

구글이 웹 문서 80억 개를 다룬 논문(Manku·Jain·Das Sarma, WWW 2007)에서 64비트 지문에 k = 3을 쓴 데서 왔습니다. 그 규모와 그 토막 방식에서 놓침과 헛걸음이 가장 견딜 만했다는 뜻이지, 모든 데이터에 맞는 상수가 아닙니다. 임계값을 올리면 놓치는 중복이 줄고 엉뚱한 쌍을 중복으로 보는 헛걸음이 늘며, 내리면 반대가 됩니다.

되짚을 수 있지만 어디까지나 추정입니다. SimHash의 비트 하나는 임의의 초평면으로 벡터를 갈랐을 때 어느 쪽인지에 해당하고, 두 벡터가 이루는 각이 θ일 때 한 비트가 다를 확률이 θ/π입니다. 그래서 64비트 중 d개가 다르면 코사인 유사도가 대략 cos(π·d/64)입니다. 이 도구는 그 추정값과 실제 코사인 유사도를 나란히 보여 줍니다.

64비트는 표본으로 적기 때문입니다. 비트마다 다를 확률이 θ/π라는 것은 평균 이야기이고, 64번 던진 결과가 그 평균에서 몇 개쯤 벗어나는 것은 자연스럽습니다. 게다가 해시 비트는 진짜 무작위 초평면이 아니라 해시 함수가 흩뿌린 결과일 뿐입니다. 지문 길이를 늘리면 추정이 촘촘해지지만 비교 비용도 함께 커집니다.

짧은 글이나 한글에는 글자 n-gram이 낫습니다. 낱말로 쪼개면 토막이 몇 개 안 나와 지문이 크게 흔들리고, 한글은 조사가 붙어 「날씨가」와 「날씨는」이 서로 다른 토막이 되기 때문입니다. 긴 영문 문서라면 낱말 단위로도 충분합니다.

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