해밍 거리 (Hamming Distance)
1. 개요
해밍 거리(Hamming Distance)란 길이가 동일한 두 문자열 또는 이진 시퀀스 사이에서 서로 다른 위치에 있는 요소의 개수를 측정하는 거리 함수이다. 1950년 리처드 해밍(Richard Hamming)에 의해 제안되었으며, 두 데이터가 얼마나 다른지를 수치화하여 데이터 전송 과정에서의 오류 검출 및 정정에 핵심적인 역할을 한다. 해밍 거리를 계산하기 위해서는 반드시 비교 대상이 되는 두 시퀀스의 길이가 동일해야 한다는 전제 조건이 필요하다.
2. 작동 원리 및 계산 방법
해밍 거리는 두 시퀀스를 동일한 인덱스(위치)별로 일대일 대응시켜 비교하며, 값이 서로 다른 지점의 총합을 구하는 방식으로 작동한다.
계산 메커니즘
- 두 문자열 $S_1$과 $S_2$를 준비한다. (단, $|S_1| = |S_2|$)
- 인덱스 $i = 0$부터 $n-1$까지 순회하며 $S_1[i]$와 $S_2[i]$를 비교한다.
- 두 값이 다를 경우 카운트를 1 증가시킨다.
- 최종 카운트 값이 두 시퀀스의 해밍 거리가 된다.
계산 사례 (이진 문자열 비교)
다음은 두 이진 문자열 1011101과 1001001을 비교하는 과정이다.
| 위치 (Index) |
문자열 A |
문자열 B |
일치 여부 |
거리 합산 |
| 0 |
1 |
1 |
일치 |
0 |
| 1 |
0 |
0 |
일치 |
0 |
| 2 |
1 |
0 |
불일치 |
1 |
| 3 |
1 |
1 |
일치 |
1 |
| 4 |
1 |
0 |
불일치 |
2 |
| 5 |
0 |
0 |
일치 |
2 |
| 6 |
1 |
1 |
일치 |
2 |
결과: 두 문자열의 해밍 거리는 2이다.
3. 주요 특징 및 성질
해밍 거리는 수학적으로 메트릭 공간(Metric Space)의 거리 함수 조건을 모두 만족한다.
수학적 성질
- 비음수성 (Non-negativity): $d(x, y) \ge 0$. 거리는 항상 0보다 크거나 같으며, $d(x, y) = 0$인 경우 두 시퀀스는 완전히 동일하다.
- 대칭성 (Symmetry): $d(x, y) = d(y, x)$. $x$에서 $y$로의 거리와 $y$에서 $x$로의 거리는 같다.
- 삼각 부등식 (Triangle Inequality): $d(x, z) \le d(x, y) + d(y, z)$. 임의의 세 시퀀스에 대해 직접적인 거리보다 다른 지점을 거쳐가는 거리의 합이 항상 크거나 같다.
- 시간 복잡도: $O(n)$, 여기서 $n$은 시퀀스의 길이이다. 모든 요소를 한 번씩만 확인하면 되므로 선형 시간에 계산이 완료된다.
- 공간 복잡도: $O(1)$, 추가적인 메모리 할당 없이 카운트 변수만으로 계산 가능하다.
4. [[해밍 코드]]와의 관계
코드워드 집합 내의 임의의 두 코드워드 사이의 최소 해밍 거리를 최소 거리($d_{min}$)라고 한다. 해밍 거리는 [해밍 코드]라는 오류 정정 코드의 이론적 기초가 된다.
- 오류 검출: 전송된 데이터의 해밍 거리가 최소 거리 $d_{min}$보다 작을 때, $d_{min}-1$개의 비트 오류를 검출할 수 있다.
- 오류 정정: 해밍 거리를 이용하여 수신된 잘못된 데이터와 가장 가까운(해밍 거리가 최소인) 유효한 코드워드(Codeword)를 찾아 원래 데이터를 복원한다. 이를 위해 $\lfloor (d_{min}-1)/2 \rfloor$개의 오류를 정정할 수 있다.
- 관계 요약: 해밍 거리가 '차이의 양'을 측정하는 척도라면, 해밍 코드는 이 척도를 이용하여 데이터에 중복 비트를 추가함으로써 오류를 스스로 찾아내고 고치는 알고리즘이다.
5. 활용 분야
- 오류 검출 및 정정 (ECC): 통신 시스템에서 데이터 전송 중 발생하는 비트 반전(Bit Flip) 오류를 감지하고 수정하는 데 사용된다.
- 유전체 서열 분석: 길이가 동일한 두 DNA 서열 간의 돌연변이 발생 지점 수를 계산하여 생물학적 유사성을 분석한다.
- 데이터 중복 제거 및 해싱: Locality Sensitive Hashing(LSH)과 결합하여 고차원 데이터에서 유사한 항목을 빠르게 검색하는 데 활용된다.
- 암호학: 두 암호문 사이의 거리나 키의 차이를 분석하는 차분 공격(Differential Cryptanalysis) 등에 응용된다.
6. 구현 예제 및 최적화 원리
컴퓨터 아키텍처 수준에서 해밍 거리를 가장 효율적으로 계산하는 방법은 XOR 연산과 Popcount를 사용하는 것이다.
XOR 연산 과정 도식:
두 비트 $A$와 $B$에 대하여:
$$A \oplus B = \begin{cases} 0 & \text{if } A = B \\ 1 & \text{if } A \neq B \end{cases}$$
예시: 1011101 $\oplus$ 1001001
1 0 1 1 1 0 1 (S1)
⊕ 1 0 0 1 0 0 1 (S2)
----------------
0 0 1 0 1 0 0 (결과: 서로 다른 위치만 1로 표시됨)
이 결과값에서
1의 개수를 세는 것이 곧 해밍 거리이다.
- XOR ($\oplus$) 연산: 두 비트가 서로 다를 때만
1을 반환하는 특성이 있다.
- Popcount (Population Count): 이진수에서
1의 개수를 세는 연산이다. 현대의 CPU는 POPCNT라는 전용 명령어를 제공하여 매우 빠르게 처리한다.
def hamming_distance(s1, s2):
# 길이가 다를 경우 에러 처리
if len(s1) != len(s2):
raise ValueError("Sequences must have the same length")
# 방법 1: 반복문을 이용한 일반적인 계산
distance = 0
for char1, char2 in zip(s1, s2):
if char1 != char2:
distance += 1
return distance
def hamming_distance_bit(int1, int2):
# 방법 2: 비트 연산을 이용한 최적화 계산 (정수 입력 시)
# 이 함수는 입력된 정수의 전체 비트 길이를 기준으로 계산함
# XOR 연산 후 1의 개수를 세는 방식
xor_result = int1 ^ int2
return bin(xor_result).count('1')
# 테스트 사례
str1 = "1011101"
str2 = "1001001"
print(f"문자열 해밍 거리: {hamming_distance(str1, str2)}") # 출력: 2
num1 = 0b1011101 # 93
num2 = 0b1001001 # 73
print(f"비트 연산 해밍 거리: {hamming_distance_bit(num1, num2)}") # 출력: 2
7. 유사도 측정 지표와의 비교
해밍 거리는 단순하지만 제약 조건(길이 동일)이 엄격하다. 상황에 따라 다른 거리 측정 방식을 선택해야 한다.
| 비교 항목 |
해밍 거리 (Hamming) |
[[레벤슈타인 거리]] (Levenshtein) |
[[자카드 유사도]] (Jaccard) |
| 핵심 개념 |
위치별 불일치 개수 |
편집 횟수 (삽입, 삭제, 교체) |
집합의 교집합/합집합 비율 |
| 길이 제약 |
반드시 동일해야 함 |
달라도 무관함 |
달라도 무관함 |
| 주요 연산 |
교체 (Substitution) |
삽입, 삭제, 교체 |
원소 포함 여부 |
| 시간 복잡도 |
$O(n)$ |
$O(n \times m)$ |
$O(n + m)$ |
| 적합한 사례 |
고정 길이 코드, 비트 비교 |
오타 교정, 자연어 처리 |
문서 유사도, 추천 시스템 |
해밍 거리 vs 레벤슈타인 거리 상세 비교:
- 해밍 거리는 오직 '교체(Substitution)' 연산만을 고려한다. 따라서 두 문자열의 길이가 다르면 정의되지 않는다.
- 레벤슈타인 거리는 교체뿐만 아니라 '삽입(Insertion)'과 '삭제(Deletion)' 연산을 모두 포함한다. 예를 들어, kitten과 sitting을 비교할 때 해밍 거리는 계산할 수 없으나, 레벤슈타인 거리는 삽입/삭제/교체 횟수를 합산하여 거리를 산출한다.
선택 기준:
- 데이터의 길이가 고정되어 있고 단순 치환 오류만 고려한다면 $\rightarrow$ 해밍 거리
- 데이터의 길이가 가변적이며 삽입/삭제가 빈번하다면 $\rightarrow$ 레벤슈타인 거리
- 순서보다는 포함된 요소의 구성 성분이 중요하다면 $\rightarrow$ 자카드 유사도
# 해밍 거리 (Hamming Distance)
## 1. 개요
**해밍 거리(Hamming Distance)**란 길이가 동일한 두 문자열 또는 이진 시퀀스 사이에서 서로 다른 위치에 있는 요소의 개수를 측정하는 거리 함수이다. 1950년 리처드 해밍(Richard Hamming)에 의해 제안되었으며, 두 데이터가 얼마나 다른지를 수치화하여 데이터 전송 과정에서의 오류 검출 및 정정에 핵심적인 역할을 한다. 해밍 거리를 계산하기 위해서는 반드시 비교 대상이 되는 두 시퀀스의 **길이가 동일해야 한다**는 전제 조건이 필요하다.
## 2. 작동 원리 및 계산 방법
해밍 거리는 두 시퀀스를 동일한 인덱스(위치)별로 일대일 대응시켜 비교하며, 값이 서로 다른 지점의 총합을 구하는 방식으로 작동한다.
### 계산 메커니즘
1. 두 문자열 $S_1$과 $S_2$를 준비한다. (단, $|S_1| = |S_2|$)
2. 인덱스 $i = 0$부터 $n-1$까지 순회하며 $S_1[i]$와 $S_2[i]$를 비교한다.
3. 두 값이 다를 경우 카운트를 1 증가시킨다.
4. 최종 카운트 값이 두 시퀀스의 해밍 거리가 된다.
### 계산 사례 (이진 문자열 비교)
다음은 두 이진 문자열 `1011101`과 `1001001`을 비교하는 과정이다.
| 위치 (Index) | 문자열 A | 문자열 B | 일치 여부 | 거리 합산 |
| :--- | :---: | :---: | :---: | :---: |
| 0 | 1 | 1 | 일치 | 0 |
| 1 | 0 | 0 | 일치 | 0 |
| 2 | 1 | 0 | **불일치** | 1 |
| 3 | 1 | 1 | 일치 | 1 |
| 4 | 1 | 0 | **불일치** | 2 |
| 5 | 0 | 0 | 일치 | 2 |
| 6 | 1 | 1 | 일치 | 2 |
**결과:** 두 문자열의 해밍 거리는 **2**이다.
## 3. 주요 특징 및 성질
해밍 거리는 수학적으로 **메트릭 공간(Metric Space)**의 거리 함수 조건을 모두 만족한다.
### 수학적 성질
- **비음수성 (Non-negativity):** $d(x, y) \ge 0$. 거리는 항상 0보다 크거나 같으며, $d(x, y) = 0$인 경우 두 시퀀스는 완전히 동일하다.
- **대칭성 (Symmetry):** $d(x, y) = d(y, x)$. $x$에서 $y$로의 거리와 $y$에서 $x$로의 거리는 같다.
- **삼각 부등식 (Triangle Inequality):** $d(x, z) \le d(x, y) + d(y, z)$. 임의의 세 시퀀스에 대해 직접적인 거리보다 다른 지점을 거쳐가는 거리의 합이 항상 크거나 같다.
### 시간 복잡도
- **시간 복잡도:** $O(n)$, 여기서 $n$은 시퀀스의 길이이다. 모든 요소를 한 번씩만 확인하면 되므로 선형 시간에 계산이 완료된다.
- **공간 복잡도:** $O(1)$, 추가적인 메모리 할당 없이 카운트 변수만으로 계산 가능하다.
## 4. [[해밍 코드]]와의 관계
코드워드 집합 내의 임의의 두 코드워드 사이의 최소 해밍 거리를 **최소 거리($d_{min}$)**라고 한다. 해밍 거리는 [[해밍 코드]](Hamming Code)라는 오류 정정 코드의 이론적 기초가 된다.
- **오류 검출:** 전송된 데이터의 해밍 거리가 최소 거리 $d_{min}$보다 작을 때, $d_{min}-1$개의 비트 오류를 검출할 수 있다.
- **오류 정정:** 해밍 거리를 이용하여 수신된 잘못된 데이터와 가장 가까운(해밍 거리가 최소인) 유효한 코드워드(Codeword)를 찾아 원래 데이터를 복원한다. 이를 위해 $\lfloor (d_{min}-1)/2 \rfloor$개의 오류를 정정할 수 있다.
- **관계 요약:** 해밍 거리가 '차이의 양'을 측정하는 척도라면, 해밍 코드는 이 척도를 이용하여 데이터에 중복 비트를 추가함으로써 오류를 스스로 찾아내고 고치는 알고리즘이다.
## 5. 활용 분야
- **오류 검출 및 정정 (ECC):** 통신 시스템에서 데이터 전송 중 발생하는 비트 반전(Bit Flip) 오류를 감지하고 수정하는 데 사용된다.
- **유전체 서열 분석:** 길이가 동일한 두 DNA 서열 간의 돌연변이 발생 지점 수를 계산하여 생물학적 유사성을 분석한다.
- **데이터 중복 제거 및 해싱:** Locality Sensitive Hashing(LSH)과 결합하여 고차원 데이터에서 유사한 항목을 빠르게 검색하는 데 활용된다.
- **암호학:** 두 암호문 사이의 거리나 키의 차이를 분석하는 차분 공격(Differential Cryptanalysis) 등에 응용된다.
## 6. 구현 예제 및 최적화 원리
### [[XOR 연산]] 최적화 원리
컴퓨터 아키텍처 수준에서 해밍 거리를 가장 효율적으로 계산하는 방법은 **XOR 연산**과 **Popcount**를 사용하는 것이다.
**XOR 연산 과정 도식:**
두 비트 $A$와 $B$에 대하여:
$$A \oplus B = \begin{cases} 0 & \text{if } A = B \\ 1 & \text{if } A \neq B \end{cases}$$
예시: `1011101` $\oplus$ `1001001`
```text
1 0 1 1 1 0 1 (S1)
⊕ 1 0 0 1 0 0 1 (S2)
----------------
0 0 1 0 1 0 0 (결과: 서로 다른 위치만 1로 표시됨)
```
이 결과값에서 `1`의 개수를 세는 것이 곧 해밍 거리이다.
1. **XOR ($\oplus$) 연산:** 두 비트가 서로 다를 때만 `1`을 반환하는 특성이 있다.
2. **Popcount (Population Count):** 이진수에서 `1`의 개수를 세는 연산이다. 현대의 CPU는 `POPCNT`라는 전용 명령어를 제공하여 매우 빠르게 처리한다.
### Python 구현 예제
```python
def hamming_distance(s1, s2):
# 길이가 다를 경우 에러 처리
if len(s1) != len(s2):
raise ValueError("Sequences must have the same length")
# 방법 1: 반복문을 이용한 일반적인 계산
distance = 0
for char1, char2 in zip(s1, s2):
if char1 != char2:
distance += 1
return distance
def hamming_distance_bit(int1, int2):
# 방법 2: 비트 연산을 이용한 최적화 계산 (정수 입력 시)
# 이 함수는 입력된 정수의 전체 비트 길이를 기준으로 계산함
# XOR 연산 후 1의 개수를 세는 방식
xor_result = int1 ^ int2
return bin(xor_result).count('1')
# 테스트 사례
str1 = "1011101"
str2 = "1001001"
print(f"문자열 해밍 거리: {hamming_distance(str1, str2)}") # 출력: 2
num1 = 0b1011101 # 93
num2 = 0b1001001 # 73
print(f"비트 연산 해밍 거리: {hamming_distance_bit(num1, num2)}") # 출력: 2
```
## 7. 유사도 측정 지표와의 비교
해밍 거리는 단순하지만 제약 조건(길이 동일)이 엄격하다. 상황에 따라 다른 거리 측정 방식을 선택해야 한다.
| 비교 항목 | 해밍 거리 (Hamming) | [[레벤슈타인 거리]] (Levenshtein) | [[자카드 유사도]] (Jaccard) |
| :--- | :--- | :--- | :--- |
| **핵심 개념** | 위치별 불일치 개수 | 편집 횟수 (삽입, 삭제, 교체) | 집합의 교집합/합집합 비율 |
| **길이 제약** | **반드시 동일해야 함** | 달라도 무관함 | 달라도 무관함 |
| **주요 연산** | 교체 (Substitution) | 삽입, 삭제, 교체 | 원소 포함 여부 |
| **시간 복잡도** | $O(n)$ | $O(n \times m)$ | $O(n + m)$ |
| **적합한 사례** | 고정 길이 코드, 비트 비교 | 오타 교정, 자연어 처리 | 문서 유사도, 추천 시스템 |
**해밍 거리 vs 레벤슈타인 거리 상세 비교:**
- **해밍 거리**는 오직 **'교체(Substitution)'** 연산만을 고려한다. 따라서 두 문자열의 길이가 다르면 정의되지 않는다.
- **레벤슈타인 거리**는 교체뿐만 아니라 **'삽입(Insertion)'**과 **'삭제(Deletion)'** 연산을 모두 포함한다. 예를 들어, `kitten`과 `sitting`을 비교할 때 해밍 거리는 계산할 수 없으나, 레벤슈타인 거리는 삽입/삭제/교체 횟수를 합산하여 거리를 산출한다.
**선택 기준:**
- 데이터의 길이가 고정되어 있고 단순 치환 오류만 고려한다면 $\rightarrow$ **해밍 거리**
- 데이터의 길이가 가변적이며 삽입/삭제가 빈번하다면 $\rightarrow$ **레벤슈타인 거리**
- 순서보다는 포함된 요소의 구성 성분이 중요하다면 $\rightarrow$ **자카드 유사도**