[Python] 해밍 거리(Hamming distance) 이해 및 구현하기

해밍 거리(Hamming Distance)는 리차드 웨슬리 해밍이라는 수학자가 만든 같은 크기를 가진 데이터를 놓고, 같은 위치에 있는 값들끼리 비교를 하는 매우 직관적인 알고리즘이다.

 

해밍 거리를 만든 리차드 웨슬리 해밍(Richard Wesley Hamming, 1915년 2월 11일~1998년 1월 7일) 

 

해밍거리 예시

"머신러닝"과 "머신건"이 얼마나 유사한지 해밍 거리로 비교를 해보자.

 

머	신	러	닝
머	신	건
O	O	X	X

위와 같이 총 2개가 유사하고, 2개는 다르기에 둘간의 거리는 즉 2가 된다. 여기서 머신건은 3글자이고 머신러닝은 4글자이기 때문에 부족한 글자는 공백으로 치환을 하고 계산을 해야 한다. 계산을 할 때 공백을 추가하지 않을 경우 에러가 발생된다.

 

글자수가 다를 경우 에러 화면

Traceback (most recent call last):
  File "E:/Python/Post/similar/hamming.py", line 9, in <module>
    print('b-c=>', 1-distance.hamming(b,c))
  File "E:\Python\Post\venv\lib\site-packages\scipy\spatial\distance.py", line 797, in hamming
    raise ValueError('The 1d arrays must have equal lengths.')
ValueError: The 1d arrays must have equal lengths.

 

해밍거리는 2가 나왔지만, 우리가 유사도를 구하고 싶을 때에는 퍼센트 형태로 값이 나와야 한다. 한마디로 0~1 사이의 값이 나와야 유사도를 제대로 구할 수 있을 것이다. 

 

위의 계산에서는 최종 연산에서 글자수를 나누면 된다. 2개가 일치하고, 글자수는 4개이기 때문에 유사도는 50%가 된다.

 

 

파이썬 해밍거리 소스

import numpy as np
from scipy.spatial import distance

a = np.array(["파","이","썬"])
b = np.array(["파","이","선"])
c = np.array(["파","",""])

print('scipy a-b=>', distance.hamming(a,b))
print('scipy b-c=>', distance.hamming(b,c))
print('scipy a-c=>', distance.hamming(a,c))

 

위의 결과를 우리가 예상하기로는 a와 b는 2개가 맞기 때문에 0.66이 나와야 되고, b와 c를 계산한 것과 a와 c를 계산하는 경우 "파"라는 한글자만 맞기 때문엥 0.33을 예상할 수 있을 것이다.

 

a-b=> 0.3333333333333333
b-c=> 0.6666666666666666
a-c=> 0.6666666666666666

 

하지만 값은 우리가 생각하는 것과 정반대로 나왔는데 이유는 거리가 가까울수록 유사하다 판단을 하기 때문이다. 즉 여기서 구한 방식은 distance를 구한거지 해밍 유사도가 아니기 때문에 가까울수록 유사도가 높다라고 판단할 수 있다. 

 

결국 이 소스에서 유사도로 반영하라면 1-최종결과로 계산값을 보정하면, 유사도가 된다.

 

보정한 코드

print('scipy a-b=>', 1-distance.hamming(a,b))
print('scipy b-c=>', 1-distance.hamming(b,c))
print('scipy a-c=>', 1-distance.hamming(a,c))

a-b=> 0.6666666666666667
b-c=> 0.33333333333333337
a-c=> 0.33333333333333337

위와 같이 보정 이후 정상적으로 유사도 값이 나오는 것을 확인할 수 있다.

 

해밍코드를 scipy 패키지를 써서 구현해봤지만 고작 이 간단한 알고리즘을 위해서 scipy를 쓰는 것도 낭비일 수 있다. 그래서 한번 직접 function을 만들어봐서 동일한지 확인해보도록 한다.

 

User Function

def hamming_dist(array_a, array_b):
    count = 0
    for i in range(len(array_a)):
        if array_a[i] == array_b[i]:
            count += 1
    return count / len(array_a)
    
    
print('user function a-b=>', hamming_dist(a,b))
print('user function b-c=>', hamming_dist(b,c))
print('user function a-c=>', hamming_dist(a,c))

위와 같이 코드가 총 5줄 짜리로 간단하게 구현이 되었다. 게다가 유사도를 구하기 위해 1에서 값을 뺄 필요 없이 그냥 호출만 하게 되었다.

 

전체 소스

import numpy as np
from scipy.spatial import distance


def hamming_dist(array_a, array_b):
    count = 0
    for i in range(len(array_a)):
        if array_a[i] == array_b[i]:
            count += 1
    return count / len(array_a)


a = np.array(["파","이","썬"])
b = np.array(["파","이","선"])
c = np.array(["파","",""])

print('scipy a-b=>', 1-distance.hamming(a,b))
print('scipy b-c=>', 1-distance.hamming(b,c))
print('scipy a-c=>', 1-distance.hamming(a,c))


print('user function a-b=>', hamming_dist(a,b))
print('user function b-c=>', hamming_dist(b,c))
print('user function a-c=>', hamming_dist(a,c))

 

참고자료

https://en.wikipedia.org/wiki/Richard_Hamming