위키피디어(http://en.wikipedia.org/wiki/Edit_distance)에 정의된 것을 보면,
즉, 두 문자열간의 edit distance는 하나의 문자열을 다른 하나의 문자열로 변환하기 위해 요구되어지는 연산의 수이다. 라고 정의되어 있다.
일반적으로 어떤 Vertex간의 거리는 개념이 일반화가 되어 있어서 쉬우나, 정의를 보지 않고 문자열간의 거리라 함은 이해가 잘 안되기도 한다.
벡터간의 거리는 쉽게 유클리안 거리를 이용하면 되지만...
혹시, 문자열간의 거리도 벡터로 변환 후 유클리안 거리를 이용하나?
답은 정의를 보면 변환하기 위해 요구되어지는 연산의 수가 문자열간의 거리이다.
이때 필요한 연산의 수는 다음과 같이 정의가 된다.
변환(change), 삽입(insertion), 삭제(deletion) 3가지 연산이 필요하다.
change : symbols at corresponding positions are distinct
insertion : a symbol of y is missing in x at a corresponding position
deletion : a symbol of x is missing in y at a correspoinding position.
(in order to transform x into y)
예를 들어,
1. x: "abc" --> y:"abd"
x 문자열을 y 문자열로 변환하기 위해서는 마지막 문자 "c"를 "d"로 바꾸기만 하면 된다.
즉, change 라는 연산 한 번만 발생하기 때문에 x와 y의 거리는 1이다.
2. x: "park" --> y:"spake"
이 문제는 조금 애매하지 않은가? 어떻게 변환을 할지...
그러나, 조금만 생각해보면 x의 1번째 문자 앞에 y의 "s"를 삽입(insertion)하고,
x의 3번째 문자 "r"을 "k"로 변환하고, x의 5번째 문자 "k"를 "e"로 변환을 하면 된다.
1번의 삽입과 2번의 변환이 이루어졌으니, 거리는 3이다.
s p a k e
또 다른 방법으로, x:"p" -> y:"s", x:"a" ->y:"p", x:"r" -> y:"a", y:"e"를 x의 마지막 문자로
삽입하는 경우도 가능하다. 이 경우는 3번의 변환과 1번의 삽입이 이루어졌으니,
거리는 4가 된다.
s p a k e
위 2번 예제에서 최적의 거리는 3이다.
이것이 edit distance이다.
그렇다면, 어떻게 최적의 거리를 찾을 것인가가 문제이다.
그 최적의 거리를 찾기 위해 우리는 Dynamic Programming Method를 사용한다.
물론, 그래프 알고리즘 가운데 다익스트라(Dijstra, 네덜란드인) 알고리즘을 사용해도 되나,
일반적으로 Dynamic Programming Method를 이용한다.
간단하게나마, Dynamic Programming Method를 살펴보자.
실행 시간의 정보를 기록한다는 의미이다. 즉, 중복되는 계산 결과를 기록해서 중복된 계산 결과가 필요한 경우, 최대한 재계산을 피하고자 하는 것이다.
다른 말로 해석하자면, 작은 문제들의 해를 먼저 구하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다.
한마디로, divide-and-conquer 이다. 분할 정복한다는 의미이다.
가장 이해하기 쉬운 것이 재귀호출로 여기면 될 것이다.
아무튼, Dynamic Programming Method 기법을 적용하여 Edit Distance를 구하고자 하는 식은 다음과 같다.
where ∂ (a, b) = 0 if a = b and ∂ (a, b) = 1 otherwise
1) The edges from (i-1, j-1) to (i-1, j) and (i, j-1) have weight 1 and the edge
from (i-1, j-1) to (i, j) has weight ∂ (x[i], y[j])
2) The edit distance between words x and y equals the length of a least weighted path from the source(0, 0), left upper corner, to the sink(m, n), right bottom corner..
부가 설명을 붙이자면, 현재 위치에서 우측<right, (i, j-1)>의 위치에는 가중치 1를 부여하고, 아래측<down, (i-1, j)>도 가중치 1를 부여하나 대각선<diagonal, (i, j)>의 위치는 문자열 x의 i번째 문자와 문자열 y의 j번째 문자가 같다면 0을, 틀리다면 1이라는 가중치를 부여한다.
위 식에서 insertion(삽입), deletion(삭제), change(변환)의 연산이 전부 포함되어져 있다.
만일, EDIT(i, j) 값이 우측(i, j-1) 값이 되면, insert(삽입)이 된다.
또한, EDIT(i, j) 값이 아래측(i-1, j) 값이 되면, deletion(삭제)이 되며, 대각선(i-1, j-1)이 되면 change(변환)이 연산이 된다는 의미이다. 좀 더 풀어서 설명하자면,
insertion(→)은 y의 문자를 x에 삽입한다는 의미이며,
deletion(↓)은 x의 문자를 삭제한다는 의미이며,
change(↘)은 x의 문자와 y의 문자를 교환한다는 의미이다.
이러한 과정을 통해 현재의 가중치를 구하고, source(0,0)에서 sink(m, n)까지 수행하면 Edit Distance를 구할 수 있다. 바로 Edit Distance는 Edit(m, n)이 된다.
Edit Distance를 구하는 pseudo code는 아래와 같다.
{ |x| = m, |y| = n, EDIT is a matrix of integers }
for i := 0 to m do EDIT[i, 0] := i;
for j := 1 to n do EDIT[0, j] := j;
for i := 1 to m do
for j := 1 to n do
EDIT[i, j] = min(EDIT[i-1, j]+1, EDIT[i, j-1]+1, EDIT[i-1, j-1]+∂(x[i], y[j]))
return EDIT[m, n];
위의 예제에서 Edit Distance를 구하기 위해 작성된 Matrix 내용을 보자.
--|---------- --|---------------
a | 0 1 2 3 p | 0 1 2 3 4 5
b | 1 0 1 2 a | 1 1 1 2 3 4
c | 2 1 0 1 r | 2 2 2 1 2 3
| 3 2 1 1 k | 3 3 3 2 2 3
| 4 4 4 3 2 3
이로써, Edit Distance는 x라는 문자열을 y라는 문자열로 변환하기 위해 수행되는 연산의 수가 되면 그 연산은 Dynamic Programming을 통해 구해질 수 있다.
그러나, 우리가 Edit Distance를 구하기 위해 m X n의 matrix를 사용해야 되나? 라는 의문은 갖지 않는가? 희소행렬 (sparse matrix)를 이용해도 충분할텐데 말이다...
그러나, 우리가 Edit Operations을 구하기 위해서는 반드시 m X n의 matrix가 필요하다.
Edit Operations는 Back Tracking을 하면서 optimal path를 구하기 때문이다.
Edit Operations은 이미 위의 2번 예제에서 살펴보았다.
즉, 두 문자열간의 optimal path를 보여주는 과정이다.
연속된 문자들 "- a"는 문자 'a'를 삽입(insertion)한다는 의미이며, "a -"는 'a'를 삭제(deletion)한다는 의미이다. 즉, "- a"는 y의 문자가 "-"에 삽입되어져야 할 자리이며, "a -"는 x의 문자를 삭제해야 한다는 의미이다. 변환(change)는 굳이 작성하지 않아도 된다. 어떻게 보면 x와 y의 문자들을 서로 교환을 해야 된다는 의미인데 굳이 표현할 필요는 없다는 뜻도 된다.
위 2번 예제를 다시 보면,
s p a k e
--> 이것은 "-"의 자리에 y의 문자 's'가 들어올 자리이며, x의 'r', 'k'는 change의 자리라는 의미이다.
즉, Edit Operations은 위와 같은 형태를 만드는 행위라 보면 된다.
이 행위 또한 Edit Distance를 획득하기 위해 만들어진 matrix를 사용해야 하며 위의 의미 그대로 작성하면 된다.
Edit Operations을 구하는 pseudo code는 아래와 같다.
{ |x| = i, |y| = j, EDIT is a matrix of integers( m X n) }
if i = 0 and j = 0, then return
if i = 0, then begin
editoperations(i, j-1);
do insertion;
end
else if j = 0, then begin
editoperations(i,-1 j);
do deletion;
end
else, then begin
min value = min(EDIT[i-1, j]+1, EDIT[i, j-1]+1,
EDIT[i-1, j-1]+∂(x[i], y[j]))
if min value = EDIT[i-1, j-1], + ∂(x[i], y[j]), then begin
editoperations(i-1, j-1);
do susbtitution;
end
else if min value = EDIT[i, j-1] + 1; then begin
editoperations(i, j-1);
do insertion;
end
else, then begin
editoperations(i-1, j);
do deletion;
end
end
이 과정을 수행하면서 다음과 같은 문자열에 대해서 테스트를 해보라.
2. aggccaat acggctca
optimal path는 3~4가지가 나올 수 있다.
그 중 하나의 값을 살펴보면 다음과 같다.
--cohen :: 따라서, Edit Distance는 3이라는 것을 알 수 있다.
a-ggccaat :: 이 Edit Operations을 보면, 1번의 삽입과 1번의 삽입 연산이 수행.
acggctca- :: 따라서, Edit Distance는 2라는 것을 알 수 있다.
위 결과를 보고 짐작할 수 있듯, 삽입은 x의 문자열에서 발생을 하고, 삭제는 y의 문자열에서 발생을 한다.
즉, 의미상 x 문자열이 기준이 된다. x에 y의 문자를 삽입하고, x의 문자를 삭제하고..
예를 들어, mccoh-n은 y의 문자 'e'를 x에 삽입하고자 하는 것이며, --cohen은 x의 문자 'm'과 'c'를 삭제하겠다는 의미이다.
문자열간의 거리를 체크하여 두 문자열간의 유사성을 체크한다는 것은 재미있는 일이다.
검색에서의 사용을 예를 들자면, 두 문서의 제목에 대해서 Edit Distance를 사용하여 유사성을 체크할 수도 있는 일이다.
http://www-scf.usc.edu/~audhkhas/kws_audhkhasi_icassp07.pdf
Video, Image 처리 분야에서도 Edit Distance / Edit Operations을 이용을 많이 하는 것 같다.
자세하게 보지는 않았지만, 2개의 Image간의 유사성을 체크할 수 있지 않을까??
http://www-stat.stanford.edu/~idrori/Vidop.pdf
http://www.micc.unifi.it/publications/2006/BDN06a/bertini-civr06.pdf
한글에 대해서는 어떻게??
한글 검색어 간 유사도를 위한 Levenshtein distance 함수
이 블로그에서 잘 설명이 되어 있으니 참조를 하구...
** 관련 글 **
문장 비교
http://www.cs.umass.edu/~mccallum/courses/cl2006/lect4-stredit.pdf
http://www.cs.ucr.edu/~stelo/cpm/cpm05/cpm05_8_4_Touzet.pdf
http://www.cs.duke.edu/courses/fall05/cps230/L-04.pdf
http://www.aistudy.co.kr/math/shortest_johnsonbaugh.htm
** 소스 **
ED.c'IT > 검색엔진' 카테고리의 다른 글
| Deterministic Skip Lists (DSL) (2) | 2009.05.03 |
|---|---|
| Language Independent Extractive Summarization (TextRank) (1) | 2009.04.24 |
| 2. The term vocabulary and postings lists (2.1 Document delineation and character sequence decoding) (2) | 2009.02.11 |
| 1.4 The extended Boolean model versus ranked retrieval, 1.5 References and further reading (0) | 2008.12.10 |
| 1.3 Processing Boolean queries (0) | 2008.12.10 |
쩐의시대
나답게 살아가고 나답게 살아가자