Edit Distance

편집 거리(Edit Distance) 알고리즘에 대해 알아보고 Python으로 Edit Distance 알고리즘을 구현해본다.

‘KITTEN’과 ‘SITTING’ 문자열 비교

편집 거리(Edit Distance)는 어떤 문자열을 다른 문자열로 바꾸기 위해 필요한 연산의 최소 횟수를 뜻한다. 한 문자열에 대해 삽입, 삭제, 변경의 연산을 몇 번에 걸쳐 바꿀 수 있는지를 기준으로 두 비교 대상의 유사도를 판단한다.

‘KITTEN’과 ‘SITTING’을 비교한다고 했을 때, 편집 거리를 구하는 과정은 아래와 같이 2차원 배열을 통해 확인할 수 있다. 비교 대상 문자열을 두 축에 두고 공집합에서 부터 ‘S’, ‘SI’, ‘SIT’, …, ‘SITTING’ 문자와 {}, ‘K’, ‘KI’, …, ‘KITTEN’ 문자열을 차례대로 비교해 나간다.

첫번째 행과 열에는 아래와 같이 공집합과 비교하기 때문에 삽입 연산이 이뤄져야 하므로 문자열의 길이와 같다.

이어서 두번째 행과 열의 값을 채워넣을 때에는 세 가지 상태값에 따라 값이 정해진다.

1. D[i – 1][j]에서 A[i]를 변형할 때 A[1, i – 1]은 B[1, j]와 동일하게 변형되어 있으므로 A[i]는 삭제되어야 한다.
2. D[i][j – 1]에서 B[j]를 변형할 때 A[1, i]는 B[1, j – 1]과 동일하게 변형되어 있으므로 여기에 B가 한 글자 증가하게 되면, A의 뒤에 B[j]를 삽입해야 한다.
3. D[i – 1][j – 1]에서 A[i]와 B[j]를 변형할 때 A[i]와 B[j]의 값이 같다면 A를 추가적으로 변형할 필요가 없다. 대신 A[i]와 B[j]가 다르다면 A[i]를 B[j]로 수정하는 연산이 필요하다.

점화식으로 나타내면 다음과 같고,

$$ D[i][j] = min \begin{cases} D[i-1][j-1] + 1 \quad (\text{if } A[j] \text{ != } B[j])\ D[i][j] + 1 \ D[i][j-1] + 1 \end{cases} $$

배열을 모두 채우면 아래와 같은 결과를 얻을 수 있다.

소스코드

Python으로 위 철차를 구현하면 다음과 같다.

def print_mat_2d(mat):
  for i in range(len(mat)): print(mat[i])

#A,B = input(),input()
A,B = "kitten","sitting"
la,lb = len(A),len(B)

d=[[0 for _ in range(int(lb+1))] for _ in range(int(la+1))]
for i in range(1,la+1): d[i][0]=i
for i in range(1,lb+1): d[0][i]=i

for i in range(1,la+1):
  for j in range(1,lb+1):
    d[i][j] = d[i-1][j-1] if A[i-1] == B[j-1] else min(min(d[i-1][j-1],d[i][j-1]),d[i-1][j-1])+1

print_mat_2d(d)
print("Edit distance of '"+A+"' and '"+B+"' is", d[la][lb])

print_mat_2d 함수는 디버깅을 위해 추가한 함수.