편집거리 구하기

편집거리(edit distance)는 단어의 유사도를 측정하는 방법 중 하나이다. 한 단어에서 글자를 추가/제거/교체하여 다른 단어로 바꿀 때 필요한 최소한의 편집 액션의 횟수로 결정한다.  computer라는 단어와 commuter라는 단어는 매우 유사한데, p -> m으로 한글자만 변경하면 처음 단어에서 두 번째 단어로 바뀌게 된다. 비슷하게 sport라는 단어는 sort라는 단어로 바꾸기 위해서는 p 한글자를 지우면 된다. 혹은 sort에서 p한 글자를 추가하면 된다.

단어의 유사도를 측정하는 방법에는 편집 거리외에도 자카드 유사도 등의 여러 방법이 있다.

편집거리는 두 문자열 s1, s2에서 몇 번의 추가/삭제/변경으로 변환할 수 있는가를 나타내는 개념이다. 이러한 변경에는

1. 글자를 교환하기
2. 글자를 삽입하기
3. 글자를 삭제하기

의 세 종류의 변경 연산을 할 수 있다. 이를 이용해서 두 단어 사이의 편집거리를 구하는 재귀 함수를 생각해보자.

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를 예로 들어보겠다.

1. 변경: sprin + g 와 prin + t로 볼 때 sprin -> prin으로 변경한 후 g -> t로 바꾸는 변경을 1회 수행한다. 이 때 편집거리는 d(sprin, print) + 1이 될 수 있다. 만약 마지막 글자가 동일하다면 1이 아닌 0을 더한다.
2. 추가: 혹은 spring과 print + t로 본다면 spring -> prin으로 변경한 후 t를 추가하는 것이므로 편집거리에 1을 더한 d(spring, prin) + 1이 될 수도 있다.
3. 삭제: 반대로 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로의 편집거리를 쓴다. 여기에는 세 경우가 있다.

1. s를 삭제한 후 p를 추가한다. => 1 + 1 (표에서는 왼쪽칸 + 1)
2. p를 추가한 후 s를 삭제한다. => 1 + 1 (표에서는 위쪽칸 + 1)
3. 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. 먼저 *의 왼쪽에서 오른쪽으로 가면서 1을 더한다. 이는 sp -> # 변경 한 후에 p를 추가하는 것을 말하면 이 때의 편집거리는 3(2 + 1)이다.
2. 혹은 p를 삭제한 후 s -> p 변환을 한다. 이건 2(1 + 1) 이다.
3. 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로 계산되었고 이 과정을 보면

1. s를 삭제 (2행 1열)
2. p, r, i, n는 그대로 둔다. (-> 6행 5열)
3. 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 구현이다.