해밍 거리(Hamming Distance)란? 개념부터 구현과 실무 활용까지

Hamming Distance는 길이가 같은 두 시퀀스를 비교하여 서로 다른 값을 가진 위치의 개수를 계산하는 거리 척도입니다.

단순하지만 알고리즘, 오류 검출, 코딩 이론, 네트워크, 바이너리 데이터 비교, 일부 머신러닝 문제에서 널리 사용됩니다.

핵심 아이디어

karolin
kathrin

위치별로 비교하면:

k a r o l i n
k a t h r i n
    ↑ ↑ ↑

서로 다른 위치가 3개이므로:

Hamming Distance = 3

고전적인 정의에서는 두 입력의 길이가 같아야 합니다.

수학적 정의

길이가 n인 두 시퀀스 x, y에 대해:

H(x, y) = Σ [x[i] ≠ y[i]]

같으면 0, 다르면 1을 더합니다.

알고리즘

1. 두 입력의 길이가 같은지 확인합니다.
2. distance = 0으로 시작합니다.
3. 모든 위치를 순회합니다.
4. 값이 다르면 distance를 증가시킵니다.
5. 결과를 반환합니다.

function hammingDistance(a, b):
    if length(a) != length(b):
        error

    distance = 0

    for i from 0 to length(a) - 1:
        if a[i] != b[i]:
            distance++

    return distance

TypeScript 구현

function hammingDistance(a: string, b: string): number {
  if (a.length !== b.length) {
    throw new Error("Inputs must have the same length.");
  }

  let distance = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      distance++;
    }
  }

  return distance;
}

시간 및 공간 복잡도

Time Complexity: O(n)
Space Complexity: O(1)

각 위치를 한 번씩 확인하고 추가적인 큰 자료구조를 사용하지 않습니다.

정수와 XOR

두 정수의 비트를 비교할 때는 XOR가 매우 유용합니다.

1010
XOR
1110
----
0100

XOR 결과의 각 1은 원래 두 수에서 서로 다른 비트 위치를 의미합니다.

따라서:

Hamming Distance = (x XOR y)의 1 비트 개수

Brian Kernighan 방법:

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    value &= value - 1;
    distance++;
  }

  return distance;
}

value & (value - 1)은 반복할 때마다 하나의 set bit를 제거합니다.

실제 활용

오류 검출과 오류 정정 코드

전송된 데이터가 얼마나 변경되었는지 판단하는 데 중요한 개념입니다.

디지털 시스템과 네트워크

두 비트 패턴 사이의 차이를 빠르게 계산할 수 있습니다.

컴퓨터 비전

Binary Descriptor로 표현된 이미지 특징을 비교할 때 자주 사용됩니다.

머신러닝

Binary Feature Vector나 범주형 데이터의 간단한 거리 척도로 사용할 수 있습니다.

A = [1, 0, 1, 1, 0]
B = [1, 1, 1, 0, 0]

Distance = 2

Hamming Distance와 Levenshtein Distance의 차이

Hamming Distance는 같은 위치끼리만 비교하며 일반적으로 입력 길이가 같아야 합니다.

Levenshtein Distance는 다음 연산을 고려합니다.

• Insert
• Delete
• Replace

예를 들어 cat과 cats는 길이가 다르기 때문에 고전적인 Hamming Distance를 적용할 수 없지만 Levenshtein Distance는 1입니다.

언제 사용해야 할까?

다음 조건에서 적합합니다.

• 두 시퀀스의 길이가 같다.
• 위치가 중요하다.
• 불일치 개수만 필요하다.
• 바이너리 데이터를 다룬다.
• 단순하고 빠른 거리 계산이 필요하다.

삽입과 삭제까지 고려해야 한다면 Levenshtein Distance가 더 적합합니다.

자주 나오는 인터뷰 문제

두 정수 x, y가 있을 때 x를 y로 바꾸기 위해 변경해야 하는 비트의 수를 구하라는 문제입니다.

1. x XOR y
2. 결과의 1 비트 개수 계산

예:

1 = 0001
4 = 0100
XOR = 0101

따라서 Hamming Distance는 2입니다.

정리

Hamming Distance는 길이가 같은 두 시퀀스에서 서로 다른 위치의 개수입니다.

문자열에서는 단순한 선형 순회로, 정수에서는 XOR + set-bit counting으로 구현할 수 있습니다. 단순성과 효율성 때문에 알고리즘, 네트워크, 코딩 이론, 데이터 처리, 컴퓨터 비전 및 기술 면접에서 계속 사용됩니다.