레벤슈타인 거리

레벤슈타인 거리(Levenshtein Distance)는 특정 문자열 A와 B가 있을 때, 문자열 A에 대해서 최소한의 삽입, 삭제, 수정(수정을 삽입과 삭제로 나눌 필요가 없다고 가정) 연산을 수행해서 문자열 B로 만들 수 있을 때 그 수행 횟수를 의미한다. 이것은 편집 거리라고도 한다.

레벤슈타인 거리 알고리즘의 출처

흔히 레벤슈타인 거리 알고리즘이라고 하지만, 레벤슈타인 거리를 구하는 알고리즘은 레벤슈타인 본인이 만든 것이 아니다. 레벤슈타인은 그의 논문 <Levenshtein, V. I. “Binary coors capable or ‘correcting deletions, insertions, and reversals.” Soviet physics-doklady. Vol. 10. No. 8. 1966.> 에서 문자열의 오류를 정량적으로 정의하는 개념으로 레벤슈타인 거리를 제안하고 문자열 오류를 극복할 수 있는 부호화 기법에 대해 논할 뿐, 레벤슈타인 거리 자체를 효율적으로 계산할 수 있는 알고리즘은 제시하지 않는다.

그 후 레벤슈타인 거리를 구하는 알고리즘이 여러 논문에서 제시되었다. 그 최초의 DP 해법 알고리즘은 <Wagner, Robert A., and Michael J. Fischer. “The string-to-string correction problem.” Journal of the ACM (JACM) 21.1 (1974): 168-173.>에서 제시한다.

바그너-피셔 알고리즘

바그너-피셔 알고리즘은 아래와 같은 슈도코드로 묘사할 수 있다.

# Wagner–Fischer (Levenshtein distance) pseudocode
# A length m, B length n

function levenshtein(A, B):
    m ← length(A)
    n ← length(B)

    create array dp[0..m][0..n]

    # base cases: empty prefixes
    for i ← 0 to m:
        dp[i][0] ← i
    for j ← 0 to n:
        dp[0][j] ← j

    # fill table
    for i ← 1 to m:
        for j ← 1 to n:
            if A[i-1] == B[j-1]:
                cost ← 0
            else:
                cost ← 1

            dp[i][j] ← min(
                dp[i-1][j]   + 1,      # delete from A
                dp[i][j-1]   + 1,      # insert into A
                dp[i-1][j-1] + cost    # substitute (or match if cost=0)
            )

    return dp[m][n]

위 알고리즘의 시간복잡도는 O(mn)이며, 공간복잡도는 최적화 시에 O(min(m, n))임을 쉽게 알아볼 수 있다.

바그너-피셔 알고리즘의 원리

바그너-피셔 알고리즘은 Trace라는 개념을 제시한다. Trace는 문자열 A와 B의 인덱스를 앞에서부터 소비해 나가며 각 단계에서 어떤 인덱스 쌍을 사용했는지를 기록한 것이다. 바그너-피셔 알고리즘은 Trace를 직접 계산하는 대신, Trace경로의 최소 비용만 계산한다. 이것은 바그너-피셔 알고리즘이 아래와 같은 전제를 가지고 있다는 의미이다.

특정 문자열의 최소 Trace 비용 구하기 문제는 레벤슈타인 거리 구하기와 동치이다.

또한 바그너-피셔 알고리즘이 DP구조를 가졌다는 점에서 아래와 같은 가정도 있다.

특정 문자열의 최소 비용 Trace는 특정 문자열의 접두어의 최소 비용 Trace로부터 구해낼 수 있다.

이 때 Trace를 쉽게 이해하기 위해서 그것과 동치인 문자열 정렬 과정을 아래와 같이 생각하자.

원본 문자열 A, B가 아래와 같이 주어진다.

   A: "ABC"
   B: "AXBXBC"

문자열 A, B의 사이에 공백을 넣어서 같은 길이로 만든다. 단, 두 결과문자열의 같은 칸에 공백이 올 수는 없다. 아래에서는 공백을 밑줄 문자로 표시했다.

   A': "A_B\_\_C"
   B': "AXBXBC"

문자열 A’, B’의 인덱스에 대해서 아래와 같은 규칙을 적용해서 총 비용을 계산한다.

  • 두 칸의 문자가 같되 공백이 아니면 0, 두 칸의 문자가 다르면 1

우리는 이 공백을 넣은 문자열이 여러 종류가 존재할 수 있음을 알고, 최소 비용을 가진 문자열은 그 길이도 최소임을 생각해 볼 수 있다. 이제 처리한 문자열 A’ B’를 가지고 B를 만드는 법을 생각해 볼 수 있다.

A’, B’의 각 인덱스의 문자 a, b에 대해서 결과 문자열을 아래 작업의 출력물로 구성

  1. a == b일 경우 a를 출력
  2. a가 공백 문자인 경우 b를 출력(삽입)
  3. b가 공백문자인 경우 무시 (삭제)
  4. a와 b가 공백이 아니면서 서로 다른 문자인 경우 b를 출력 (대치)

DP 알고리즘이 이 정렬 중 최소 비용인 것을 찾아내는 것이라고 생각하면 DP의 각 상태전이가 삽입, 삭제, 대치 중 어떤 것에 연관되는지 생각하기가 좀 더 쉬워진다. 위의 슈도코드에서 dp[i][j]칸이 의미하는 바는 A[i], B[j]까지를 사용한 두 접두어로 만들 수 있는 가장 낮은 비용의 정렬상태라고 할 수 있다. 문제에서 A[i]와 B[j]까지의 접두어를 모두 사용한 상태가 가지는 이전 상태는 3가지이다.

  • A[i - 1]와 B[j - 1]까지를 사용한 상황에서 한 번에 두 문자를 모두 사용하는 상태(두 문자가 같으면 비용 추가가 없고, 다르면 1의 비용이 추가된다.) 이 전이는 작업이 없는 상태와 대치를 의미한다.
  • A[i - 1]와 B[j]까지를 사용한 상황에서 A[i]만 추가로 사용하는 상황. 비용은 1이 추가된다. 이 전이는 삭제가 된다.
  • A[i]와 B[j - 1]까지를 사용한 상황에서 B[j]만 추가로 사용하는 상황. 비용은 1이 추가된다. 이 전이는 삽입이 된다.

DP의 상태정의에서 dp[i][j]가 마지막 인덱스가 동시에 소진되는 방식으로 도달한 상태라고 생각해서는 안 된다는 점이 중요하다. 앞서 말한대로 dp[i][j]는 단지 그 두 접두어의 정렬의 최소 비용 혹은 편집 시퀸스의 최소 비용이다. 위의 슈도코드에서 dp[i][j]칸들 중 일부에 초기값으로 저장한 값들이 바로 해당 문자 인덱스까지 모두 사용했을 때의 최소 정렬 비용 혹은 최소 편집 시퀀스 비용이라는 점도 기억해야 한다.

정리

바그너-피셔 알고리즘은 DP의 상태 정의와 레벤슈타인 거리 개념 사이의 연결이 직관적으로 드러나지 않아 이해가 어려운 알고리즘이다. 그러나 문자열 정렬과 편집 시퀀스의 관계를 생각해보면 조금 더 이해하기 쉽다.