편집거리 (단어의 유사도 분석)

편집거리 구하기

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이 아닌 두 문자열의 편집거리를 보자. 두 단어 springprint를 예로 들어보겠다.

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

이번에는 0의 아래방향을 보자. 여기서는 왼쪽끝에 있는 글자까지의 단어가 빈 문자열이 되기 까지의 편집거리이다. 따라서 s는 한 번의 삭제, sp는 두 번의 삭제가 일어난다. 이 때 sp는 한 번 삭제하면 s가 되므로 s -> #의 편집거리인 1에 1을 더한 값이다. 이런식으로 첫 열을 완성할 수 있다.

# | #  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씩 증가한 값이 들어간다. (이들 칸에서도 사실 위와 같은 과정을 통해서 값을 구한다) 그 결과는 아래와 같고, 이를 통해 s -> print는 6회의 편집거리를 갖는다는 것을 알 수 있다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
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가 서로 같으므로 sp -> ps -> #의 편집거리와 동일하다. 이 경우에는 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

같은 방식으로 sprp, 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로 비교적 짧은 오타단어와 정상단어 사이의 관계를 이용해서 제시할 수 있는 원리이다.

(추가) 아래는 Swift3로 구현한 편집거리 계산 함수이다. 2차원 배열을 사용했고, 특정 인덱스의 글자를 뽑아내기 위해서 String 타입을 확장했다.

http://swiftlang.ng.bluemix.net/#/repl/579e9ca06563d8d9272a3ac6