해밍 거리
길이가 같은 두 문자열 사이의 해밍 거리(Hamming distance)는 동일한 위치에 있는 문자들이 서로 다른 위치의 개수를 나타내는 척도이다.
쉽게 말하면, 해밍 거리는 한 문자열을 다른 문자열로 바꾸기 위해 필요한 최소 치환(substitution) 횟수를 의미한다. 이 거리는 문자의 삽입이나 삭제는 허용하지 않고, 문자 치환만 고려한다.
길이가 \( n \)인 두 문자열 \( s \)와 \( t \)가 주어졌을 때, 해밍 거리 \( D_H(s,t) \)는 다음과 같이 정의된다.
$$ D_H(s, t)=\sum_{i=1}^{n}\delta(s_i,t_i) $$
여기서 \( s_i \)와 \( t_i \)는 각각 문자열 \( s \)와 \( t \)의 \( i \)번째 문자를 의미하며, 함수 \( \delta(s_i,t_i) \)는 두 문자가 서로 다르면 1을, 같으면 0을 반환한다.
따라서 해밍 거리는 길이가 같은 문자열에 대해서만 정의된다.
예제
다음 두 문자열을 살펴보자.
$$ s=\text{"karbon"} $$
$$ t=\text{"carbon"} $$
두 문자열은 첫 번째 문자(k와 c)만 다르다. 따라서 해밍 거리는 다음과 같다.
$$ D_H(s,t)=1 $$
예제 2
다음은 해밍 거리가 2인 영어 단어의 예이다.
$$ s=\text{"thing"} $$
$$ t=\text{"thank"} $$
이 두 단어는 두 위치에서 서로 다르다.
- 세 번째 문자: i → a
- 다섯 번째 문자: g → k
따라서 두 단어 사이의 해밍 거리는 2이다.
해밍 거리가 유도하는 거리 위상
해밍 거리는 길이가 같은 모든 문자열 \( x \), \( y \), \( z \)에 대해 다음 세 가지 기본 성질을 만족한다.
- 비음수성
$$ D_H(x,y)\ge0 \quad\text{and}\quad D_H(x,y)=0\ \text{if and only if}\ x=y $$
해밍 거리는 서로 다른 위치의 개수를 세는 값이므로 항상 0 이상이다. 또한 두 문자열이 완전히 같을 때에만 거리가 0이 된다.
- 대칭성
$$ D_H(x,y)=D_H(y,x) $$
문자열 \( x \)에서 \( y \)까지의 거리와 \( y \)에서 \( x \)까지의 거리는 항상 같다. 서로 다른 위치의 개수는 비교하는 순서에 영향을 받지 않기 때문이다.
- 삼각부등식
$$ D_H(x,z)\le D_H(x,y)+D_H(y,z) $$
세 문자열 \( x \), \( y \), \( z \)에 대해 \( x \)와 \( z \) 사이의 차이는 반드시 \( x \)와 \( y \), 또는 \( y \)와 \( z \) 사이의 차이 가운데 적어도 하나에 포함된다. 따라서 직접 거리는 두 부분 거리의 합보다 커질 수 없다.
이 세 가지 성질을 모두 만족하므로, 해밍 거리는 일정한 길이를 가진 문자열들의 집합 위에 거리공간을 정의한다.
거리공간에서는 거리 개념을 이용해 점들 사이의 가까움을 정의할 수 있으며, 이를 바탕으로 하나의 위상을 구성할 수 있다.
따라서 해밍 거리는 거리 위상(metric topology)을 유도한다.
길이가 \( n \)인 문자열 \( x \)와 반지름 \( r \)에 대해, 중심이 \( x \)이고 해밍 거리가 \( r \)보다 작은 모든 문자열의 집합을 열린 공(open ball), 또는 근방 \( B \)라고 한다.
$$ B(x,r)=\{y\mid D_H(x,y)
이러한 열린 공들은 거리 위상의 기저(basis)를 이루며, 모든 열린집합은 열린 공들의 임의의 합집합으로 표현할 수 있다.
참고. 길이가 \( n \)인 모든 이진 문자열(또는 기호 문자열)의 집합은 유한 집합이다. 따라서 이 집합에서 해밍 거리가 유도하는 위상은 이산위상(discrete topology)이 된다. 즉, 각 문자열 하나만으로 이루어진 집합도 열린집합이면서 동시에 닫힌집합이다. 이는 충분히 작은 반지름(예를 들어 \( r=1 \))을 선택하면 각 문자열만을 포함하는 열린 공을 만들 수 있기 때문이다.
따라서 길이가 같은 유한한 문자열들의 집합에서는 해밍 거리가 생성하는 거리 위상이 곧 이산위상이 된다.
예제
길이가 3인 다음 이진 문자열들의 집합을 생각해 보자.
$$ X=\{000,001,011,110,111\} $$
반지름 \( r=2 \)인 경우의 열린 공은 다음과 같이 정의된다.
$$ B(x,r)=\{y\mid D_H(x,y)<2\} $$
즉, 중심 문자열과 한 위치 이하에서만 다른 문자열들이 하나의 열린 공을 이룬다.
- \(000\)을 중심으로 하는 열린 공
$$ B(000,2)=\{000,001\} $$ - \(001\)을 중심으로 하는 열린 공
$$ B(001,2)=\{001,000,011\} $$ - \(011\)을 중심으로 하는 열린 공
$$ B(011,2)=\{011,001,111\} $$ - \(110\)을 중심으로 하는 열린 공
$$ B(110,2)=\{110,111\} $$ - \(111\)을 중심으로 하는 열린 공
$$ B(111,2)=\{111,011,110\} $$
이 열린 공들은 반지름 \( r=2 \)에서 생성되는 거리 위상의 기저를 이룬다. 이들의 합집합을 이용하면 위상의 모든 열린집합을 만들 수 있다.
참고. 열린 공에서는 경계가 포함되지 않으므로 다음과 같이 "2보다 작은" 부등식을 사용한다. $$ B(x,r)=\{y\mid D_H(x,y)<2\} $$ 반대로 닫힌 공(closed ball)은 경계를 포함하므로 다음과 같이 정의된다. $$ C(x,r)=\{y\mid D_H(x,y)\le2\} $$
예를 들어 \( B(000,2) \)와 \( B(110,2) \)의 합집합은 다음과 같다.
$$ B(000,2)\cup B(110,2) $$
\( B(000,2)=\{000,001\} \), \( B(110,2)=\{110,111\} \)이므로
$$ B(000,2)\cup B(110,2)=\{000,001\}\cup\{110,111\} $$
즉,
$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$
이 집합 역시 열린집합이 된다.
결론적으로 해밍 거리는 문자열 집합 위에 자연스러운 거리 위상을 정의하며, 각 열린집합은 열린 공들의 합집합으로 표현된다. 이러한 성질은 정보 이론, 부호 이론(coding theory), 오류 검출 및 오류 정정, 그리고 계산이론 등 다양한 분야에서 중요한 역할을 한다.
