해밍 거리 계산기

가장 기본이 되는 방법입니다. 두 값을 세로로 나란히 놓고 같은 자리끼리 비교해서, 다른 자리의 개수를 셉니다.

예를 들어 1011101과 1001001을 비교하면 1번째는 1과 1로 같고, 2번째는 0과 0으로 같고, 3번째는 1과 0으로 다르고, 4번째는 1과 1로 같고, 5번째는 1과 0으로 다르고, 6번째와 7번째는 각각 같습니다. 다른 자리는 3번째와 5번째 두 개이므로 해밍 거리는 2입니다.

중요한 것은 두 값의 길이가 반드시 같아야 한다는 점입니다. 길이가 다르면 짝지을 자리가 없어서 해밍 거리 자체가 정의되지 않습니다. 길이가 다른 두 문자열을 비교하고 싶다면 아래에서 설명하는 편집 거리를 씁니다.

두 비트열을 XOR(배타적 논리합)하면 같은 자리는 0, 다른 자리는 1이 됩니다. 그러면 결과에 들어 있는 1의 개수가 곧 해밍 거리입니다. 이 1의 개수를 세는 연산을 popcount(population count)라고 부릅니다.

앞의 예제로 확인해 보면 1011101 XOR 1001001 = 0010100이고, 여기 들어 있는 1은 3번째와 5번째 자리의 두 개입니다. 자리를 하나씩 세어 얻은 값과 정확히 같습니다. 이 계산기가 XOR 카드에 "XOR의 1 개수 = 해밍 거리"라는 줄을 함께 내는 이유가 이것입니다 — 답을 두 경로로 만들어 서로 검산하는 셈입니다.

C·C++의 __builtin_popcount, 자바의 Integer.bitCount, 파이썬의 bin(a ^ b).count("1") 같은 함수가 전부 이 방식입니다. 코딩 테스트에서 해밍 거리 문제가 나오면 대개 이 한 줄로 끝납니다.

다만 언어의 정수 타입으로 비트열 전체를 한 번에 바꾸려 들면 자릿수가 커질 때 조용히 틀립니다. 자바스크립트에서 1이 64개인 비트열을 parseInt로 16진수로 바꾸면 ffffffffffffffff가 아니라 10000000000000000이 나옵니다. 이 계산기는 그래서 정수 변환을 쓰지 않고 4비트씩 끊어서 변환합니다.

해밍 가중치(Hamming weight)는 값 하나에 들어 있는 0이 아닌 자리의 개수입니다. 비트열이라면 1의 개수입니다. 1011101의 해밍 가중치는 5입니다.

해밍 가중치는 사실 해밍 거리의 특수한 경우입니다. 어떤 값과 0으로만 이뤄진 값(0000000) 사이의 해밍 거리가 곧 그 값의 해밍 가중치이기 때문입니다. 이 계산기는 2진·16진 모드에서 두 값의 해밍 가중치를 함께 표시합니다.

코드워드가 여러 개 있을 때, 모든 쌍의 해밍 거리 중 가장 작은 값을 최소 해밍 거리(dmin)라고 합니다. 부호의 성능을 결정하는 값이라 정보처리기사·정보통신기사 시험에 반복해서 나옵니다.

오류 검출 능력은 td ≤ dmin − 1로, 오류 정정 능력은 tc ≤ ⌊(dmin − 1)/2⌋로 씁니다. ⌊ ⌋는 소수점을 버리는 기호입니다. 예를 들어 dmin이 3이면 검출 능력은 2개, 정정 능력은 ⌊2/2⌋ = 1개입니다.

이 두 식이 직관적으로 이해되지 않을 때는 이렇게 생각하면 편합니다. 어떤 코드워드에서 비트가 dmin − 1개까지 바뀌어도 다른 정상 코드워드와 겹치지 않으므로 "뭔가 잘못됐다"는 사실은 알 수 있습니다. 하지만 "원래 무엇이었는지"까지 알아맞히려면 원래 코드워드 쪽이 다른 어떤 코드워드보다 확실히 가까워야 하므로 거리의 절반까지만 가능합니다.

(7,4) 해밍 부호는 dmin이 3이라 오류를 2개까지 검출하고 1개까지 정정합니다. 패리티 비트 하나만 붙인 단순 패리티 검사는 dmin이 2라 오류 1개를 검출할 수 있을 뿐 정정은 하지 못합니다.

두 문자열이 얼마나 다른지 재는 척도라는 점은 같지만, 허용하는 연산이 다릅니다. 해밍 거리는 치환만 셉니다. 편집 거리(레벤슈타인 거리)는 삽입·삭제·치환을 모두 셉니다.

그래서 해밍 거리는 길이가 같은 두 값에서만 정의되고, 편집 거리는 길이가 달라도 계산됩니다. 101과 1011의 해밍 거리는 정의되지 않지만 편집 거리는 1입니다(끝에 1을 하나 삽입).

길이가 같은 경우에도 두 값이 항상 일치하지는 않습니다. 다만 편집 거리는 해밍 거리보다 크지 않다는 관계는 항상 성립합니다 — 치환만 쓰는 방법도 편집 방법 중 하나이기 때문입니다.

어느 쪽을 써야 할지 헷갈린다면 기준은 간단합니다. 자리가 밀릴 수 있는 상황(오탈자, 문장 비교)이면 편집 거리, 자리가 고정된 상황(비트열, 고정 길이 코드, 해시)이면 해밍 거리입니다.

오류 검출·정정: 통신이나 저장 장치에서 비트가 뒤집혔는지 확인하고, 어느 비트가 뒤집혔는지 찾아 되돌립니다. 해밍 부호·CRC·ECC 메모리가 모두 이 개념 위에 있습니다.

해시 유사도: 지각 해시(pHash)나 SimHash처럼 "비슷한 입력은 비슷한 해시를 낸다"는 성질을 갖는 해시에서, 두 해시의 해밍 거리가 작으면 원본이 비슷하다고 봅니다. 이미지 중복 검출이나 문서 유사도 판정에 쓰입니다. 이 경우 비트 기준 거리가 필요하므로 16진 모드에서 비트 기준 값을 봐야 합니다.

생물정보학: 길이가 같은 DNA·단백질 서열에서 몇 개 위치가 다른지 세는 데 그대로 쓰입니다. ACGTACGT와 ACGTAAGT는 6번째 한 자리만 다르므로 해밍 거리가 1입니다.

코딩 테스트: 백준 3449번(해밍 거리)이나 LeetCode 461번(Hamming Distance)처럼 정의를 그대로 구현하는 문제가 자주 출제됩니다. 이 계산기는 개념 확인과 검산에 쓰시고, 문제 풀이 자체는 직접 하시길 권합니다.

텍스트 모드는 문자를 사용자가 눈으로 인지하는 단위(그래핌)로 셉니다. 그래서 👍는 1자, 가족 이모지 👨‍👩‍👧‍👦도 1자입니다. 프로그래밍 언어에서 흔히 쓰는 문자열 길이로 재면 각각 2와 11이 나오는데, 이 계산기는 그렇게 세지 않습니다.

더 조심해야 하는 것은 한글의 유니코드 정규화 형식입니다. "가족"은 완성형(NFC)으로도 자모 분리형(NFD)으로도 저장될 수 있고, 화면에서는 완전히 똑같이 보입니다. 그런데 정규화를 끄고 비교하면 두 글자가 전부 다르다고 나옵니다 — 해밍 거리 2입니다.

이 계산기는 NFC 정규화를 기본으로 켜 두고, 정규화를 끈 상태에서 두 값의 형식이 다르면 그 사실을 따로 경고합니다. 정규화가 적용된 경우에는 "NFC 정규화 적용됨"이라고 화면에 남깁니다 — 입력한 것과 다른 값이 계산됐다면 그 사실이 보여야 하기 때문입니다.