[python] 해밍 거리 (Hamming Distance) - 동적 계획법

해밍 거리 (Hamming Distance)

해밍 거리는 문자열 사이의 거리를 정의하는 가장 심플한 방법입니다.

 

동적 프로그래밍에서 Edit distance를 배울 때 같이 익히는 거리 계산법 중 하나인데요.

 

해밍거리는 문자열에 포함된 문자를 앞에서부터 하나씩 비교하여 몇 개나 다른가를 출력하는 거리 함수 입니다.

 

예제를 살펴보겠습니다 

 

123456789 vs 023456789   =>  1개의 문자열이 다름 (0과 1)

ILOVEYOU  vs  YLOVEIOU   =>  2개의 문자열이 다름 (I &  Y의 위치가 다름)

 

보시다시피 간단한 거리 계산 방법입니다.

 

이를 파이썬의 scipy 패키지를 이용하여 구현해보겠습니다.

 

# 해밍 거리 활용 예제

from scipy.spatial import distance

sample_string1 = list('iloveyou')
sample_string2 = list('yloveiou')  # y와 i의 위치 변경

print('First sample string --> ', sample_string1)  
print('Second sample string --> ', sample_string2)
# --- 출력물 ----
# First sample string -->  ['i', 'l', 'o', 'v', 'e', 'y', 'o', 'u']
# Second sample string -->  ['y', 'l', 'o', 'v', 'e', 'i', 'o', 'u']
# --------------


# 해밍거리 계산
distance.hamming(sample_string1, sample_string2) * len(sample_string1)

# ---- 출력물 ----- 
# [output] 2.0

 

해밍 거리의 단점

해밍 거리는 쉽고 빠른 거리계산 방법이지만, 문자열을 해밍 거리로 계산하면, 우리가 직관적으로 인식하는 것보다 거리 차이가 많이 나는 경우가 종종 생깁니다.

 

예를 들면, 

'ILOVEYOU' 라는 문자열과 'LOVEYOU' 라는 문자열은 I 하나만 빠진 것임에도 불구하고, 해밍 거리가 8입니다.

왜냐하면  전체 문자열에서 다르기 때문이죠 

I와 L이 다르고,  (ILOVEYOU  vs  LOVEYOU)

L과 O가 다르고  (ILOVEYOU  vs  LOVEYOU)  

... (이하 생략)

 

모든 문자열에서 다르기 때문에 해밍거리는 +1씩 카운팅이 됩니다.

 

이를 극복할 수 있는 거리 계산법중 하나가 바로 편집 거리입니다.

 

편집 거리는 다음 포스팅에서 설명하겠습니다.