해밍 거리란?
해밍 거리(Hamming distance)는 길이가 같은 두 문자열에서 같은 위치에 있는 기호가 서로 다른 위치의 개수를 말합니다. 미국의 수학자 리처드 해밍(Richard Hamming)의 이름에서 따온 이 개념은 정보 이론, 부호화 이론, 컴퓨터 과학의 기초가 되는 핵심 개념입니다. 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 치환 횟수를 나타내며, 오류 검출 및 오류 정정 코드에서 폭넓게 활용됩니다.
계산기 사용 방법
비교할 두 문자열을 입력하세요. 1011101 같은 이진수 비트열, DNA 염기 서열, 또는 일반 텍스트 등 무엇이든 가능합니다. 계산기는 두 문자열을 한 글자씩 비교하여 서로 다른 위치가 몇 개인지 세어 줍니다. 두 문자열의 길이가 다를 경우, 더 긴 쪽에 남는 글자는 모두 차이로 계산됩니다.
공식 자세히 보기
두 문자열 a와 b에 대해, 해밍 거리는 모든 위치 i에 대해 \(a_i \neq b_i\)일 때 1, 같을 때 0이 되는 지시 함수를 모두 더한 값입니다.
$$d(a, b) = \sum_{i=1}^{\min(|a|,|b|)} \left[\, \text{A}_i \neq \text{B}_i \,\right] + \Big|\; |\text{A}| - |\text{B}| \;\Big|$$
결과는 항상 0(완전히 동일) 이상, 문자열 길이(모든 위치가 다름) 이하인 음수가 아닌 정수입니다.
예제로 풀어 보기
1011101과 1001001을 비교해 봅시다. 두 문자열을 나란히 맞춰 보면 다음과 같습니다.
10111011001001
3번째 위치(1 vs 0)와 5번째 위치(1 vs 0)에서 값이 다릅니다. 따라서 해밍 거리는 2입니다.
자주 묻는 질문
두 문자열의 길이가 반드시 같아야 하나요? 본래 해밍 거리는 길이가 같은 문자열에서만 정의됩니다. 다만 이 도구는 길이가 다른 경우에도 남는 글자를 각각 불일치로 계산하여 유용한 결과를 제공합니다.
이진수가 아닌 일반 텍스트에도 사용할 수 있나요? 네. 문자, 숫자, 기호 등 어떤 글자든 비교할 수 있습니다.
레벤슈타인 거리와는 무엇이 다른가요? 해밍 거리는 고정된 위치에서의 치환만 계산하지만, 레벤슈타인 거리는 삽입과 삭제까지 허용한다는 점이 다릅니다.
