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