생새우초밥집
수학, 물리학, 통계학 블로그
레벤슈타인 알고리즘 Levenstein's Algorithm


문자열 $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$ 을 대입한다.


Step 2.

$m_{(i+1) 1} = i$ 그리고 $m_{ 1 (j+1)} = j$ 을 대입한다.


Step 3. $i = 1, 2, \cdots , n$ 그리고 $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 $ 을 대입한다.


Step 4.

$A$,$B$ 의 최소 수정 거리는 $m_{nm}$ 이다.


수정 거리Edit Distance란 두 문자열 간의 유사성을 보여주는 척도로써 $A$ 에서 $B$ 로 바꾸는데 몇번이나 걸리나를 나타낸다. 사용할 수 있는 수정 방법은 삽입Insertion, 제거Deletion, 교체Replace 세가지 뿐으로 전치Transposition는 허용하지 않는다. 예를 들어 'cats' 와 'facts' 라는 문자열이 있다고 하면

1. (교체) cats → fats

2. (삽입) fats → facts

와 같이 총 두 번 수정되어 수정 거리는 $2$ 임을 알 수 있다.


다만 이러한 수정 거리는 얼마든지 길게 측정될 수 있는데, cats → ats → fats → facts 와 같이 비효율적인 방법도 있기 때문이다. 레벤슈타인 알고리즘Levenstein's Algorithm은 이러한 수정거리가 가장 작아지도록 구하는 방법이다.



위 스크린샷은 아래의 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]



  Comments,   0  Trackbacks
댓글 쓰기