편집거리 구하기

편집거리(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이 될 수 있다.

결국 두 단어의 최소 편집 거리는 변경, 추가, 삭제에 의한 결과 중에서 최소값을 사용한다. 그리고 이는 점점 작은 단위로 내려가서 비교하게 되기에 동적계획법으로 풀어낼 수 있다. 이 단계를 추적해보자.더 보기 »편집거리 (단어의 유사도 분석)