편집거리 구하기
편집거리(edit distance)는 단어의 유사도를 측정하는 방법 중 하나이다. 한 단어에서 글자를 추가/제거/교체하여 다른 단어로 바꿀 때 필요한 최소한의 편집 액션의 횟수로 결정한다. computer
라는 단어와 commuter
라는 단어는 매우 유사한데, p -> m
으로 한글자만 변경하면 처음 단어에서 두 번째 단어로 바뀌게 된다. 비슷하게 sport
라는 단어는 sort
라는 단어로 바꾸기 위해서는 p
한글자를 지우면 된다. 혹은 sort
에서 p
한 글자를 추가하면 된다.
단어의 유사도를 측정하는 방법에는 편집 거리외에도 자카드 유사도 등의 여러 방법이 있다.
편집거리는 두 문자열 s1, s2에서 몇 번의 추가/삭제/변경으로 변환할 수 있는가를 나타내는 개념이다. 이러한 변경에는
- 글자를 교환하기
- 글자를 삽입하기
- 글자를 삭제하기
의 세 종류의 변경 연산을 할 수 있다. 이를 이용해서 두 단어 사이의 편집거리를 구하는 재귀 함수를 생각해보자.
d('', '') = 0 -- 빈 문자열은 0번 d(s, '') = d('', s) = |s| -- 빈문자열로 변경하는데는 s의 길이만큼의 삭제필요 d(s1+ch1, s2+ch2) = min( d(s1, s2) + if ch1 = ch2 then 0 else 1, -- 교환 d(s1+ch1, s2) + 1, -- 삽입 d(s2, s2+ch2) + 1 -- 삭제 )
먼저 빈 문자열 두 개 사이의 편집거리는 0이다. 그리고 한글자로 된 문자열과 빈 문자열 간의 편집거리는 당연히 1이다. 그렇다면 빈 문자열과 길이가 n인 문자열의 편집 거리는 n이 된다.
이제 길이가 0이 아닌 두 문자열의 편집거리를 보자. 두 단어 spring
과 print
를 예로 들어보겠다.
- 변경:
sprin
+g
와prin
+t
로 볼 때sprin -> prin
으로 변경한 후g -> t
로 바꾸는 변경을 1회 수행한다. 이 때 편집거리는d(sprin, print) + 1
이 될 수 있다. 만약 마지막 글자가 동일하다면 1이 아닌 0을 더한다. - 추가: 혹은
spring
과print
+t
로 본다면spring -> prin
으로 변경한 후t
를 추가하는 것이므로 편집거리에 1을 더한d(spring, prin) + 1
이 될 수도 있다. - 삭제: 반대로
sprin
+g
와print
로 본다면sprin -> print
로 변경한 후g
를 삭제하는 것이므로d(sprin, print) + 1
이 될 수 있다.
결국 두 단어의 최소 편집 거리는 변경, 추가, 삭제에 의한 결과 중에서 최소값을 사용한다. 그리고 이는 점점 작은 단위로 내려가서 비교하게 되기에 동적계획법으로 풀어낼 수 있다. 이 단계를 추적해보자.
각 단어에 맨 앞에 공백을 추가한 후 각 원래 단어는 글자를 세로로, 목적지가되는 단어는 가로로 배치하면 아래와 같은 표가 나온다.
# | # p r i n t
--------------------
# | 0
s |
p |
r |
i |
n |
g |
이 표의 처음 등장하는 0은 바로 빈 문자열에서 빈 문자열로 바꿀 때의 편집거리이다. 그리고 그 오른쪽으로 빈 문자열에서 각 글자까지의 단어로 변경하는데 필요한 편집거리는 ‘추가’의 케이스만 있으므로 1씩 증가한다.
# | # p r i n t
--------------------
# | 0 1 2 3 4 5 ==> 빈 문자열에서 print를 만드는 과정
s |
p |
r |
i |
n |
g |
이번에는 0의 아래방향을 보자. 이 열에서 표시될 숫자들은 각 칸에서 왼쪽에 있는 단어가 위쪽에 있는 단어가 되기위해 필요한 편집거리이다. 여기서 위쪽의 칸은 빈 문자열이므로, 아래로 내려가면서 s, sp, spr, spri, sprin, spring이 각각 빈 문자열이 되는데 필요한 편집의 횟수를 구하게된다. 이 때 가능한 액션은 한 글자씩 지우는 것이기 때문에 아래와 같이 첫 열이 완성된다.
# | # p r i n t -------------------- # | 0 1 2 3 4 5 s | 1 * p | 2 r | 3 i | 4 n | 5 g | 6
이제 위의 표에서 *
가 위치한 곳을 보자, 여기는 s -> p
로의 편집거리를 쓴다. 여기에는 세 경우가 있다.
s
를 삭제한 후p
를 추가한다. => 1 + 1 (표에서는 왼쪽칸 + 1)p
를 추가한 후s
를 삭제한다. => 1 + 1 (표에서는 위쪽칸 + 1)s -> p
로 치환한다. => 0 + 1 (표에서는 대각선 왼쪽위 + 1)
이 중 최소거리는 1이므로 *
의 자리에는 1이 들어간다. 그 오른쪽으로도 계속 진행한다. 단, 오른쪽으로 진행 시에는 글자를 하나씩 덧붙이는 것이기 때문에 그 결과는 항상 왼쪽칸의 값에 +1한 값이 될 것이다.
# | # p r i n t
--------------------
# | 0 1 2 3 4 5
s | 1 1
p | 2 *
r | 3
i | 4
n | 5
g | 6
두 번째 줄을 계산해보자. sp -> p
로 바꾸는 작업이다. 이는 위의 그림에서 *의 값에 해당한다.
- 먼저 *의 왼쪽에서 오른쪽으로 가면서 1을 더한다. 이는
sp -> #
변경 한 후에p
를 추가하는 것을 말하면 이 때의 편집거리는 3(2 + 1)이다. - 혹은
p
를 삭제한 후s -> p
변환을 한다. 이건 2(1 + 1) 이다. - p가 서로 같으므로 s만 제거하면?
sp -> p
는s -> #
의 편집거리와 동일하다. 따라서 이 경우에는 1이다.
그리고 이 중 가장 작은 값은 1이므로 *
칸에 1을 쓴다. 그리고 그 오른쪽으로는 r, i, n, t
를 붙이는 작업이므로 1씩 증가한다.
# | # p r i n t
--------------------
# | 0 1 2 3 4 5
s | 1 1 2 3 4 5
p | 2 1 2 3 4 5
r | 3 2 1 2 3 4
i | 4
n | 5
g | 6
같은 방식으로 spr
을 p, pr, pri, prin, print
로 변경하는 최소편집거리를 계산하여 다음 줄을 채운다. 당연히 같은 글자가 있으면 왼쪽 위 칸의 값과 같은 값이 최소 거리가 될 것이며, 그렇지 않은 경우에는 왼쪽칸 + 1, 위쪽 칸 + 1, 왼쪽위칸 + 1 한 값 중 가장 작은 값을 쓴다. 이 규칙을 이용해서 나머지 칸을 계속 채워나간다.
# | # p r i n t -------------------- # | 0 1 2 3 4 5 s | 1 1 2 3 4 5 p | 2 1 2 3 4 5 r | 3 2 1 2 3 4 i | 4 3 2 1 2 3 n | 5 4 3 2 1 2 g | 6 5 4 3 2 2
최종적으로 spring -> print
의 최소편집거리는 2로 계산되었고 이 과정을 보면
s
를 삭제 (2행 1열)p, r, i, n
는 그대로 둔다. (-> 6행 5열)g -> t
로 변경 (7행 6열)
이 되는 셈이다.
최소거리로 증가하는 경로를 따를 수 있는 루트가 2개 이상이 경우도 얼마든지 있다.
두 문자열의 길이에 각 1을 더한 곱 만큼 크기의 배열이 필요한데, 어차피 맨 마지막의 두 행만 사용하게 되므로 파이썬으로 구현은 다음과 같이 작성할 수 있다.
def edit_distance(s1, s2):
l1, l2 = len(s1), len(s2)
if l2 > l1:
return edit_distance(s2, s1)
if l2 is 0:
return l1
prev_row = list(range(l2 + 1))
current_row = [0] * (l2 + 1)
for i, c1 in enumerate(s1):
current_row[0] = i + 1
for j, c2 in enumerate(s2):
d_ins = current_row[j] + 1
d_del = prev_row[j + 1] + 1
d_sub = prev_row[j] + (1 if c1 != c2 else 0)
current_row[j + 1] = min(d_ins, d_del, d_sub)
prev_row[:] = current_row[:]
return prev_row[-1]
여러 단어들을 비교할 때 각 단어간의 편집거리를 알면 단어의 유사성을 파악할 수 있다. 구글 검색 등에서 검색어에 오타를 낸 경우에 올바른 단어를 찾아줄 수 있는 것도 보통은 한 글자를 잘못 치거나 덜치거나 더친 경우이기 때문에 편집거리가 1~2로 비교적 짧은 오타단어와 정상단어 사이의 관계를 이용해서 제시할 수 있는 원리이다.
다음은 같은 알고리듬에 대한 Swift4 구현이다.