해밍 거리

해밍 거리

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

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

정의

다음이 주어졌다고 하자.

• 집합 $S$
• 자연수 $n$

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

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

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

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

$\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년에 해밍 부호와 함께 도입하였다.

같이 보기

• 그레이 부호
• 유클리드 거리

외부 링크

• “Hamming distance” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Hamming distance” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• 차재복 (2016년 10월 17일). “해밍중, 해밍 무게, 해밍 최소 무게, 최소 해밍 무게, 해밍 거리, 해밍 최소 거리, 최소 해밍 거리”. 《정보통신기술용어해설》.