위키득계정 ↗
기술

해밍 거리

해밍 거리기술
영문명
Hamming distance
기본 조건
두 문자열의 길이가 같음
계산 대상
같은 위치에서 다른 원소 수
최솟값
같은 문자열이면 0
해밍 거리는 길이가 같은 두 문자열에서 같은 위치의 값이 다른 자리 수다. 이진 문자열에서는 두 비트열을 같게 만들기 위해 바꾸어야 하는 비트 수로 해석한다.

자리별 비교

10110과 10001은 셋째, 넷째, 다섯째 자리에서 달라 해밍 거리가 3이다. 비트의 수치 차이를 일반 정수처럼 계산하는 것이 아니라 각 자리의 일치 여부를 센다.

문자열로 확장

ACGA와 ATGT는 둘째와 넷째 문자만 달라 문자 단위 해밍 거리가 2다. 문자 하나의 내부 비트 표현을 비교하는 거리와 문자 자체의 일치 여부를 비교하는 거리는 다를 수 있다.

삽입과 삭제는 없음

같은 위치를 대응시키므로 기본 정의는 길이가 같은 열에 적용한다. 중간에 문자를 삽입하거나 삭제해 위치를 이동시키는 편집은 허용하지 않는다. 길이가 다른 문자열의 편집 차이를 다루려면 레벤슈타인 거리 같은 다른 기준을 사용할 수 있다.

비트 연산으로 계산

같은 길이의 비트열에 XOR을 적용하면 다른 자리에서만 1이 나온다. 그 결과의 1 개수를 세면 해밍 거리를 얻는다. 실제 계산에서는 비트 폭과 앞쪽 0을 포함하는 표현 조건을 일관되게 정한다.

관련 문서

문자열 / 이진법 / 레벤슈타인 거리 / 배타적 논리합 / 거리 (수학) / 벡터 / 맨해튼 거리