Hamming Distance는 두 데이터 간의 차이를 비트 단위로 측정한다.

Hamming Distance는 같은 길이의 두 문자열(또는 비트열)에서 대응되는 위치에 있는 서로 다른 문자의 개수를 의미한다.

계산 예시

A: 1 0 1 1 0 1
B: 1 0 0 1 1 1
   ─ ─ ✗ ─ ✗ ─

위 예시에서 3번째, 5번째 비트가 다르므로 Hamming Distance = 2

활용 사례

1. 오류 검출 및 수정 (Error Detection & Correction)

• 통신에서 전송된 데이터의 오류 비트 수를 파악
• Hamming Code: 거리가 3 이상이면 1비트 오류 수정 가능
• 거리가 d인 코드는 d-1개의 오류를 검출할 수 있음

2. 유사 이미지 검색 (pHash(perceptual hash)는 같은 사진을 찾는데 유용하다.)

• pHash로 생성된 해시값 간의 Hamming Distance로 유사도 측정
• 거리가 작을수록 이미지가 유사함
• 일반적으로 거리 10 이하면 동일/유사 이미지로 판단

3. DNA 서열 비교

• 같은 길이의 DNA 서열 간 돌연변이 수 측정

4. 머신러닝에서 범주형 데이터 거리

• One-hot 인코딩된 범주형 변수 간 거리 측정

구현

def hamming_distance(a: str, b: str) -> int:
    if len(a) != len(b):
        raise ValueError("길이가 같아야 함")
    return sum(c1 != c2 for c1, c2 in zip(a, b))

# 비트 연산을 이용한 정수 비교 (더 빠름)
def hamming_distance_int(a: int, b: int) -> int:
    return bin(a ^ b).count('1')

Hamming Distance vs Edit Distance (Levenshtein)

구분	Hamming Distance	Edit Distance
길이 제약	같은 길이만 가능	다른 길이 가능
허용 연산	치환만	삽입, 삭제, 치환
시간복잡도	O(n)	O(n*m)
용도	비트열, 고정 길이 해시	문자열 유사도, 오타 교정

참고

• pHash(perceptual hash)는 같은 사진을 찾는데 유용하다.