해밍 거리

블록 부호 이론에서, 해밍 거리(Hamming距離, 영어: Hamming distance)는 곱집합 위에 정의되는 거리 함수이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

해밍 거리

4-bit binary tesseract for finding Hamming distance. Two example distances: 0100→1001 has distance 3; 0110→1110 has distance 1
분류	문자열 유사성
자료 구조	문자열
최악 시간복잡도	${\displaystyle O(n)}$
최선 시간복잡도	${\displaystyle O(1)}$
평균 시간복잡도	${\displaystyle O(n)}$
공간복잡도	${\displaystyle O(n)}$

정의

다음이 주어졌다고 하자.

• 집합 ${\displaystyle S}$
• 자연수 ${\displaystyle n}$

그렇다면, 곱집합 ${\displaystyle S^{n}}$ 위에 다음과 같은 거리 함수를 줄 수 있다.

${\displaystyle \operatorname {d_{H}} (s,t)=|\{i\in \{0,1,\dotsc ,n-1\}\colon s_{i}\neq t_{i}\}|\in \{0,1,\dotsc ,n\}}$

이 거리 함수를 ${\displaystyle S^{n}}$ 위의 해밍 거리라고 한다.

만약 ${\displaystyle (S,+,0)}$가 아벨 군(예를 들어, 유한체)이라고 할 때, ${\displaystyle s\in S^{n}}$의 해밍 무게(영어: Hamming weight)는 영벡터와의 해밍 거리이다.

${\displaystyle \operatorname {d_{H}} ({\vec {0}},s)=|\{i\in \{0,1,\dotsc ,n-1\}\colon s_{i}\neq 0\}|\in \{0,1,\dotsc ,n\}}$

예

• '1011101'과 '1001001'사이의 해밍 거리는 2이다. (1011101, 1001001)
• '2143896'과 '2233796'사이의 해밍 거리는 3이다. (2143896, 2233796)
• "toned"와 "roses"사이의 해밍 거리는 3이다. (toned, roses)

역사

리처드 해밍이 1950년에 해밍 부호와 함께 도입하였다.^[1]