해밍 거리
정의
자연수 $n \in \mathbb{N}$ 에 대해, 길이가 $n$인 코드 포인트code point의 집합 $\left\{ 0, 1 \right\}^{n}$ 에서 다음과 같이 정의된 거리 함수 $H$ 를 해밍 거리Hamming distance라 한다1.
$$ H \left( \mathbf{x} , \mathbf{y} \right) = \operatorname{card} \left\{ k : x_{k} \ne y_{k} \right\} $$ 여기서 코드 포인트는 $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ 과 $\mathbf{y} = \left( y_{1} , \cdots , y_{n} \right)$ 로 나타냈고, $\operatorname{card}$ 는 집합의 기수다. 쉽게 말해, 두 코드 포인트를 좌표별로 비교했을 때 서로 다른 좌표의 수다.
설명
해밍 거리는 이산 거리를 제외하곤 가장 간단한 거리 함수로써, 어떻게 보면 이상 거리에서 이루어지는 비교 연산을 각 좌표로 브로드캐스트하는 것으로 볼 수 있다. 당연하지만 같거나 다르기만 하면 사용할 수 있기 때문에 ‘차이’ 내지 ‘괴리’를 비교하는 모든 분야에서 가장 첫번째 후보로써 고려할만하다.
일반화
이진수 $\left\{ 0, 1 \right\}$ 가 아니라 알파벳과 같은 유한집합으로 일반화 되지 못할 이유가 전혀 없다. 또한 순서만 정확히 지킬 수 있고 그 순서대로 비교만 할 수 있다면 행렬, 더 나아가 텐서 등과 같이 다양한 자료형에도 바로 적용가능하다.
R. W. Hamming, “Error detecting and error correcting codes,” in The Bell System Technical Journal, vol. 29, no. 2, pp. 147-160, April 1950, https://doi.org/10.1002/j.1538-7305.1950.tb00463.x ↩︎