레벤슈타인 알고리즘
알고리즘
Input
문자열 $A,B$ 를 $A=[a_{i}]=(a_{1}, a_{2} , \cdots, a_{n})$ 과 $B=[b_{j}]=(b_{1}, b_{2} , \cdots, b_{m})$ 로 표현하자.
Step 1. 초기화
행렬 $M_{(n+1) \times (m+1)} = [m_{x y }]$ 를 만들고 $M_{11} ← 0$ 을 대입한다. 그리고 $1$행과 $1$열을 다음과 같이 채운다. $$ M_{(i+1) 1} ← i \\ M_{ 1 (j+1)} ← j $$
Step 2. 동적 계획법
for $i = 1, 2, \cdots , n$ and $j=1,2, \cdots , m$
if $a_{i}==b_{j}$
$M_{i,j} ← M_{(i-1)(j-1)}$
else
$M_{i,j} ← \min \left\{ M_{(i-1)(j)}, M_{(i)(j-1)}, M_{(i-1)(j-1)}\right\} + 1 $
Output
$A$, $B$ 의 최소 수정 거리는 $m_{nm}$ 이다.
설명
편집 거리 란 두 문자열 간의 유사성을 보여주는 척도로써 $A$ 에서 $B$ 로 바꾸는데 몇번이나 걸리나를 나타낸다. 그 중에서 레벤슈타인 거리levenstein distance는 삽입insertion, 제거deletion, 교체replace 세가지 편집을 허용하고, 전치transposition는 허용하지 않는다.
예시
예를 들어 ‘cats’ 와 ‘facts’ 라는 문자열이 있다고 하면
- (교체) cats → fats2. (삽입) fats → facts
와 같이 총 두 번 수정되어 수정 거리는 $2$ 임을 알 수 있다.
다만 이러한 수정 거리는 얼마든지 길게 측정될 수 있는데, cats → ats → fats → facts 와 같이 비효율적인 방법도 있기 때문이다. 레벤슈타인 알고리즘은 이러한 수정거리가 가장 작아지도록 구하는 방법이다.
코드
R
위 스크린샷은 아래의 R 코드로 예제를 풀어본 모습이다.
LED<-function(A,B)
{
A<-strsplit(A,'')[[1]]
B<-strsplit(B,'')[[1]]
lA<-length(A)
lB<-length(B)
M<-matrix(NA,ncol=lA+1,nrow=lB+1,dimnames = list(c('',B),c('',A)))
M[1,]<-0:lA
M[,1]<-0:lB
for(i in (1:lB)+1)
{
for(j in (1:lA)+1)
{
if (B[i-1]==A[j-1])
{
M[i,j]<-M[i-1,j-1]
}
else
{
M[i,j]<-min(M[i-1,j-1],M[i,j-1],M[i-1,j])+1
}
}
}
return(list(distance=c(M[lB+1,lA+1]),matrix=M))
}
LED("cats","facts")
파이썬
다음은 같은 코드를 파이썬으로 작성한 것이다.
def ED(a,b) :
a = ":".join(a)
A = a.split(":")
a = len(A)
b = ":".join(b)
B = b.split(":")
b = len(B)
M = [[j for i in range(a+1)] for j in range(b+1)]
M[0] = [i for i in range(a+1)]
for i in (range(1,b+1)) :
for j in (range(1,a+1)) :
if B[i-1]==A[j-1] :
M[i][j] = M[i-1][j-1]
else :
M[i][j] = min(M[i-1][j-1],M[i][j-1],M[i-1][j]) + 1
return M[b][a]