Levenshtein distance

Levenshtein distance, 혹은 Edit distance로 불리는 알고리즘은 하나의 string을 다른 string으로 바꾸는데 필요한 최소 연산 횟수를 구하는 알고리즘이다.

이 때 연산이란 삽입(add), 삭제(delete), 수정(replace) 세 가지의 종류를 의미한다.

 

Levenshtein distance의 점화식은 다음과 같다.

a, b는 각 string을 의미하며

lev_a,b(i, j)는 a의 [0, i] substring에서 b의 [0, j] substring까지의 최소 연산 회수 계산 값을 의미한다.

 

위 수식을 이해하기 위해 몇 가지 케이스에서 점화식에 어떻게 적용되는지 살펴보자.

 

1. i = 0이거나 j = 0인 경우

간단하게 i=0인 경우를 살펴보자.

[0, 0] substring은 ''이니, b의 [0, j] substring까지의 연산 횟수는 단순히 j가 된다. (ex. '' -> 'abc'의 최소 연산 횟수는 3이다.)

이것이 'lev(i,j) = max(i,j)    if min(i,j)=0'의 의미이다.

 

다음으로 i, j가 0이 아닌 케이스를 나눠 살펴보자.

 

2. 마지막 글자가 같은 경우

예시: aba -> aca

이 경우 aba -> aca와 ab -> ac의 결과 값이 같음을 알 수 있다.

따라서 lev(3,3) = lev(2,2)가 된다.

이는 수식에서 lev(i, j) = lev(i-1, j-1)인 경우이다. (a_i = b_j이므로 +1 생략)

 

3. 마지막 글자가 다른 경우

3-1. 삽입

예시: aa -> bbc

aa -> bb의 값을 알고 있을 때 c를 삽입하는 연산을 한 번 더 하면 결과를 얻을 수 있다.

따라서 lev(2,3) = lev(2,2) + 1인 경우이며, 수식에서 lev(i, j) = lev(i, j-1) + 1인 경우이다.

3-2. 삭제

예시: abc -> de

ab -> de의 값을 알고 있을 때 abc에서 c를 삭제하는 연산을 한 번 더 하면 된다.

따라서 lev(3,2) = lev(2,2) + 1인 경우이며, lev(i, j) = lev(i-1, j) + 1인 경우이다.

3-3. 수정

예시: abc -> def

ab -> de의 값을 알고 있을 때 c를 f로 수정하는 연산을 한 번 더 하면 된다.

따라서 lev(3,3) = lev(2,2) + 1, 즉 lev(i, j) = lev(i-1, j-1) + 1인 경우이다.

 

일반화시키면 삽입, 삭제, 수정 중 최소값을 사용하는 것이 수식의 'lev(i, j) = min{...' 부분으로 표현되는 것이다.

 

위 수식을 코드로 표현하자면 다음과 같다.