해밍 거리
1. 개요
해밍 거리는 동일한 길이의 두 문자열 간의 서로 다른 기호의 수를 측정하는 거리 척도이다. 집합 S와 자연수 n에 대해 정의되며, 곱집합 S^n 위의 거리 함수로 표현된다. 해밍 거리는 오류 검출 및 정정에 사용되며, 부호 이론에서 최소 해밍 거리는 오류 검출 및 오류 정정 부호의 중요한 개념을 정의하는 데 사용된다. 통신에서 신호 거리로도 사용되며, 유전적 거리를 측정하는 데에도 활용된다.
-
문자열 유사도 -
자카드 지수
자카드 지수는 유한 표본 집합 간의 유사성을 측정하는 지표로, 교집합 크기를 합집합 크기로 나누어 0과 1 사이의 값을 가지며 컴퓨터 과학 등 다양한 분야에서 활용된다. -
정육면체 -
카바
카바는 사우디아라비아 메카에 있는 이슬람교의 가장 신성한 장소로, 이슬람 이전부터 아랍인들의 성역이었으며 무함마드에 의해 이슬람의 중심 성지가 되었고, 아브라함과 이스마엘이 건설했다는 기록이 있는 '검은 돌'을 포함한 여러 유물이 있는 곳이며, 하즈와 움라 순례의 중심지이다. -
정육면체 -
입방정계
입방정계는 단순 입방, 체심 입방, 면심 입방의 세 가지 브라베 격자를 가지며, 다양한 결정 구조를 포함하여 물질의 특성을 결정하는 중요한 요소이다. -
부호 이론 -
선형 부호
선형 부호는 유한체 위의 벡터 공간의 부분 공간으로, 데이터 전송 및 오류 정정을 위해 사용되며, 길이, 차원, 최소 거리에 따라 표기되고, 부호어, 생성 행렬, 패리티 검사 행렬 등의 개념을 갖는다. -
부호 이론 -
리드 솔로몬 부호
리드 솔로몬 부호는 어빙 S. 리드와 구스타브 솔로몬이 개발한 오류 정정 부호로, 통신 및 데이터 저장 시 오류를 정정하기 위해 잉여 정보를 추가하며, 바코드, CD, DVD, 데이터 전송 등 다양한 분야에서 활용되고, 특히 버스트 오류에 강하고 다양한 디코딩 알고리즘을 통해 오류 정정 능력을 향상시킬 수 있다.
2. 정의
다음이 주어졌다고 하자.
* 집합
* 자연수
그렇다면, 곱집합 위에 다음과 같은 거리 함수를 줄 수 있다.
:
이 거리 함수를 위의 해밍 거리라고 한다.
만약 가 아벨 군(예를 들어, 유한체)이라고 할 때, 의 해밍 무게(Hamming weight영어)는 영벡터와의 해밍 거리이다.
:
두 개의 동일한 길이의 기호 문자열 간의 해밍 거리는 해당 기호가 다른 위치의 수이다.
3. 성질
고정된 길이 n에 대해 해밍 거리는 길이 n의 단어 집합(해밍 공간이라고도 함)에 대한 거리이며, 비음수성, 대칭성, 두 단어의 해밍 거리가 두 단어가 동일할 때만 0이 된다는 조건과 삼각 부등식을 충족한다. 실제로 세 단어 a, b, c를 고정하면, a의 i번째 글자와 c의 i번째 글자 사이에 차이가 있을 때마다, a의 i번째 글자와 b의 i번째 글자 사이에 차이가 있거나, b의 i번째 글자와 c의 i번째 글자 사이에 차이가 있어야 한다. 따라서 a와 c 사이의 해밍 거리는 a와 b 사이의 해밍 거리와 b와 c 사이의 해밍 거리의 합보다 크지 않다. 두 단어 a와 b 사이의 해밍 거리는 적절한 − 연산자를 선택했을 때 a − b의 해밍 가중치로 볼 수도 있으며, 이는 두 정수의 차이가 수직선에서 0으로부터의 거리로 볼 수 있는 것과 유사하다.
이진 문자열 a와 b의 경우, 해밍 거리는 a XOR b의 1의 개수(개체수)와 같다. 해밍 거리가 있는 길이 n 이진 문자열의 거리 공간은 해밍 큐브로 알려져 있다. 이는 하이퍼큐브 그래프에서 정점 간의 거리 집합과 거리 공간으로서 동일하다. 또한 길이 n의 이진 문자열을 문자열의 각 기호를 실수 좌표로 취급하여 의 벡터로 볼 수 있다. 이러한 임베딩을 사용하면 문자열은 n차원 하이퍼큐브의 정점을 형성하며, 문자열의 해밍 거리는 정점 사이의 맨해튼 거리와 동일하다.
4. 예
* 1011101과 1001001 사이의 해밍 거리는 2이다.
* 2143896과 2233796 사이의 해밍 거리는 3이다.
* toned와 roses 사이의 해밍 거리는 3이다.
기호는 문자, 비트 또는 십진수 등 여러 가지가 될 수 있다. 예를 들어, 다음 문자열 간의 해밍 거리는 다음과 같다.
* karolin과 kathrin 사이는 3이다.
* karolin과 kerstin 사이는 3이다.
* kathrin과 kerstin 사이는 4이다.
* 0000과 1111 사이는 4이다.
* 2173896과 2233796 사이는 3이다.
5. 오류 검출 및 정정
부호 이론에서 최소 해밍 거리(dmin으로 표시)는 오류 검출 및 오류 정정 부호와 같은 몇 가지 필수 개념을 정의하는 데 사용된다. 특히, 부호 C의 임의의 두 부호어 간의 최소 해밍 거리가 k+1 이상인 경우에만 이 부호는 k 오류 검출 부호라고 한다.
예를 들어, "000"과 "111"의 두 부호어로 구성된 부호를 생각해 보자. 이 두 단어 간의 해밍 거리는 3이므로, 이 부호는 k=2 오류 검출 부호이다. 이는 1비트 또는 2비트가 뒤집히면 오류를 감지할 수 있음을 의미한다. 3비트가 뒤집히면 "000"은 "111"이 되고 오류를 감지할 수 없다.
부호 C는 기본 해밍 공간 H의 모든 단어 w에 대해, w와 c 간의 해밍 거리가 최대 k인 부호어 c (C에서)가 최대 하나 존재하는 경우 k-오류 정정 부호라고 한다. 즉, 임의의 두 부호어 간의 최소 해밍 거리가 2k+1 이상인 경우 부호는 k-오류 정정 부호이다. 이는 또한 서로 다른 부호어를 중심으로 하는 반경 k의 모든 닫힌 구가 서로 소라는 기하학적 의미로 이해된다. 이 맥락에서 이러한 구는 해밍 구라고도 한다.
예를 들어, 두 부호어 "000"과 "111"로 구성된 동일한 3비트 부호를 생각해 보자. 해밍 공간은 000, 001, 010, 011, 100, 101, 110 및 111의 8개 단어로 구성된다. 부호어 "000"과 단일 비트 오류 단어 "001", "010", "100"은 모두 "000"에 대한 해밍 거리가 1 이하이다. 마찬가지로, 부호어 "111"과 단일 비트 오류 단어 "110", "101" 및 "011"은 모두 원래의 "111"에서 1 해밍 거리 내에 있다. 이 부호에서 단일 비트 오류는 항상 원래 부호에서 1 해밍 거리 내에 있으며, 부호는 1-오류 정정이 가능합니다. 즉, k=1이다. "000"과 "111" 간의 해밍 거리가 3이고, 이들이 부호의 전체 부호어 집합을 구성하므로 최소 해밍 거리는 3이며, 이는 2k+1 = 3을 만족한다.
따라서 부호어 간의 최소 해밍 거리 d를 가진 부호는 최대 d-1개의 오류를 감지할 수 있으며 ⌊(d-1)/2⌋개의 오류를 정정할 수 있다. 후자는 부호의 포장 반경 또는 오류 정정 능력이라고도 한다.
6. 응용
해밍 거리는 1950년 리처드 해밍이 오류 감지 및 오류 정정 코드라는 논문에서 소개한 개념이다. 해밍 가중치 분석은 정보 이론, 부호 이론, 암호학 등 여러 분야에서 사용된다.
해밍 거리는 통신에서 고정 길이 이진 단어에서 뒤집힌 비트 수를 세어 오류를 추정하는 데 사용되며, 신호 거리라고도 불린다. 크기가 q ≥ 2 인 알파벳에 대한 q-ary 문자열의 경우, 해밍 거리는 q-ary 대칭 채널에 적용된다. 반면 리 거리는 위상 편이 변조처럼 ±1의 오류를 고려하여 동기화 오류에 취약한 채널에 사용된다. 또는 일 때는 또는 의 모든 요소 쌍이 1만큼 차이가 나기 때문에 두 거리가 일치하지만, 가 더 크면 거리가 달라진다.
해밍 거리는 계통학에서 유전적 거리를 측정하는 데에도 사용된다.
그러나 길이가 다른 문자열을 비교하거나, 단순한 글자 대치뿐 아니라 삽입, 삭제까지 고려해야 할 때는 레벤슈타인 거리와 같이 더 정교한 지표가 적합하다.
7. 역사
해밍 거리는 1950년 리처드 해밍이 그의 논문 《오류 감지 및 오류 정정 코드》에서 해밍 부호와 함께 도입하였다. 해밍 가중치 분석은 정보 이론, 부호 이론, 암호학을 포함한 여러 분야에서 사용된다.
통신에서 고정 길이 이진 단어에서 반전된 비트 수를 오류 추정치로 계산하는 데 사용되며, 때때로 신호 거리라고도 불린다. 크기가 q ≥ 2인 알파벳에 대한 q-ary 문자열의 경우, 해밍 거리는 q-ary 대칭 채널의 경우에 적용되는 반면, 리 거리는 위상 편이 변조 또는 일반적으로 ±1의 오류를 고려하기 때문에 동기화 오류에 취약한 채널에 사용된다. q = 2 또는 q = 3인 경우, \mathbb{Z}/2\mathbb{Z} 또는 \mathbb{Z}/3\mathbb{Z}의 모든 요소 쌍은 1만큼 다르기 때문에 두 거리가 일치하지만, 더 큰 q에서는 거리가 다르다.
해밍 거리는 계통학에서 유전적 거리를 측정하는 데에도 사용된다.
그러나 길이가 다른 문자열을 비교하거나, 단순한 대치뿐만 아니라 삽입 또는 삭제도 예상되는 문자열을 비교하려면 레벤슈타인 거리와 같은 더 정교한 지표가 더 적합하다.
8. 알고리즘 예제 (Python)
python
def hamming_distance(string1: str, string2: str) -> int:
"""두 문자열 간의 해밍 거리를 반환한다."""
if len(string1) != len(string2):
raise ValueError("문자열의 길이가 같아야 한다.")
dist_counter = 0
for n in range(len(string1)):
if string1[n] != string2[n]:
dist_counter += 1
return dist_counter
```
더 짧은 표현:
```python
sum(char1 != char2 for char1, char2 in zip(string1, string2, strict=True))
```
파이썬 3으로 구현된 함수 `hamming_distance()`는 두 개의 길이가 같은 문자열(또는 다른 반복 가능한 객체) 간의 해밍 거리를 계산한다. 이는 두 입력의 해당 위치 간의 불일치 및 일치를 나타내는 부울 값의 시퀀스를 생성한 다음, 각각 1과 0으로 해석되는 True 및 False 값의 시퀀스를 합산하여 수행된다.
```python
def hamming_distance(s1: str, s2: str) -> int:
"""길이가 같은 시퀀스 간의 해밍 거리를 반환한다."""
if len(s1) != len(s2):
raise ValueError("길이가 다른 시퀀스에는 정의되지 않는다.")
return sum(char1 != char2 for char1, char2 in zip(s1, s2))
```
[https://docs.python.org/3/library/functions.html#zip zip()] 함수는 두 개의 길이가 같은 컬렉션을 쌍으로 병합한다.
9. 알고리즘 예제 (C)
c
int hamming_distance(unsigned x, unsigned y)
{
int dist = 0;
// ^ 연산자는 다른 비트만 1로 설정합니다.
for (unsigned val = x ^ y; val > 0; ++dist)
{
// 그런 다음 피터 베그너 방식으로 1로 설정된 비트를 계산합니다.
val = val & (val - 1); // val의 최하위 1을 0으로 설정합니다.
}
// 다른 비트의 수를 반환합니다.
return dist;
}
```
이 C 함수는 두 정수 간의 해밍 거리를 계산한다. (이진 값, 즉 비트 시퀀스로 간주). 이 함수의 실행 시간은 입력에 있는 비트 수가 아닌 해밍 거리에 비례한다. 두 입력의 비트 XOR 연산을 한 뒤, 베그너(Wegner)의 알고리즘을 사용하여 결과의 해밍 가중치(0이 아닌 비트 수)를 찾는다. 이 알고리즘은 최하위 0이 아닌 비트를 반복적으로 찾아 지운다. 일부 컴파일러는 사용 가능한 경우 특수 프로세서 하드웨어를 사용하여 이를 계산할 수 있는 `__builtin_popcount` 함수를 지원한다.
더 빠른 방법은 모집단 수 (popcount) 어셈블리 명령을 사용하는 것이다. GCC 및 Clang과 같은 특정 컴파일러는 내장 함수를 통해 이를 사용할 수 있다.
```c
// 32비트 정수의 해밍 거리
int hamming_distance32(unsigned int x, unsigned int y)
{
return __builtin_popcount(x ^ y);
}
// 64비트 정수의 해밍 거리
int hamming_distance64(unsigned long long x, unsigned long long y)
{
return __builtin_popcountll(x ^ y);
}
```
Peter Wegner영어가 1960년에 발표한 알고리즘이다.