Myers 차이 알고리즘

Myers 차이 알고리즘(MDA)은 두 시퀀스의 최장 공통 부분 시퀀스(LCS) 또는 최소 편집 스크립트(SES)를 찾는 알고리즘이다. 두 시퀀스의 공통 부분 시퀀스는 두 시퀀스에서 동일한 순서로 나타나는 엘리먼트의 시퀀스를 의미한다. 예를 들어 다음과 같은 두 배열이 있다고 가정해 보자.

let firstArray = [1, 2, 3]
let secondArray = [2, 3, 4]

이 두 배열의 공통 부분 시퀀스는 [2]와 [2, 3]이다. 이 경우 최장 공통 시퀀스는 [2, 3]이다. MDA는 두 시퀀스 길이의 합인 N에 대해 O(ND) 시간 복잡도로 이 작업을 수행할 수 있다.

편집 그래프에서 Myers 알고리즘을 사용한 최장 공통 부분 수열 길이 찾기

편집 그래프

MDA는 LCS(최장 공통 부분 수열)/SES(최단 편집 스크립트) 문제를 해결하기 위해 편집 그래프를 사용한다. 아래는 편집 그래프를 나타낸 그림이다:

그래프 상단의 x축은 시퀀스 X를 나타내고, 왼쪽의 y축은 시퀀스 Y를 나타낸다. 따라서 두 시퀀스는 다음과 같다:

X = [A, B, C, A, B, B, A]
Y = [C, B, A, B, A, C]

MDA는 다음과 같은 단계로 편집 그래프를 생성한다:

  1. 시퀀스 X의 요소를 x축에 배치하고, Y의 요소를 y축에 배치한다.
  2. 그리드를 만들고, 그리드의 각 점 (x, y)에 정점을 생성한다. 여기서 x는 [0, N] 범위, y는 [0, M] 범위이다. N은 시퀀스 X의 길이, M은 Y의 길이이다.
  3. x - y = k인 선을 그린다. 이 선을 k-선이라고 부르며, 검은 점선이 이에 해당한다. 분홍색 숫자는 k의 값을 나타낸다.
  4. X[i] = Y[j]인 점 (i, j)를 찾는다. 이 점을 매치 포인트라고 하며, 연두색 점으로 표시된다.
  5. 매치 포인트 (i, j)에서 정점 (i - 1, j - 1)과 정점 (i, j)를 연결한다. 이때 대각선 엣지가 생성된다.

그림의 각 요소는 다음과 같은 의미를 가진다:

참고: 여기서 시퀀스의 시작 인덱스는 0이 아닌 1이다. 따라서 X[1] = A, Y[1] = C이다.

이제 시작점에서 끝점까지의 최단 경로가 무엇인지 논의한다. 그래프의 엣지를 따라 이동할 수 있다. 즉, 그리드의 가로, 세로, 대각선 엣지를 통해 이동할 수 있다.

이동은 편집 스크립트와 호환된다. 삽입 또는 삭제가 그것이다. 편집 스크립트라는 용어는 소개 부분에서 언급한 SES(최단 편집 스크립트)를 의미한다.

다시 본론으로 돌아가자. 이 편집 그래프에서 정점 (i, j)로의 가로 이동은 X의 인덱스 i에서 삭제 스크립트와 호환된다. 정점 (i, j)로의 세로 이동은 Y의 인덱스 j에 있는 요소를 X의 인덱스 i 바로 뒤에 삽입 스크립트와 호환된다. 대각선 이동은 어떨까? 정점 (i, j)로의 대각선 이동은 X[i] = Y[j]를 의미하므로 스크립트가 필요 없다.

다음으로, 비대각선 이동에는 스크립트와 호환되므로 비용 1을 추가한다. 대각선 이동은 스크립트가 필요 없으므로 비용 0이다.

시작점에서 끝점까지의 최단 경로를 탐색할 때의 총 비용은 최장 공통 부분 수열 또는 최단 편집 스크립트의 길이와 동일하다.

따라서 LCS/SES 문제는 시작점에서 끝점까지의 최단 경로를 찾는 것으로 해결할 수 있다.

Myers 알고리즘

위에서 언급했듯이, 최소 편집 스크립트를 찾는 문제는 source (0, 0)에서 sink (N, M)까지 가장 적은 수의 수평 및 수직 간선으로 이루어진 경로를 찾는 문제로 축소할 수 있다. D-path는 source에서 시작해 정확히 D개의 비대각선 간선을 가지거나, 비대각선으로 D번 이동한 경로를 의미한다.

예를 들어, 0-path는 오직 대각선 간선만으로 구성된다. 이는 두 시퀀스가 완전히 동일함을 의미한다.

간단한 귀납법에 의해, D-path는 (D-1)-path에 비대각선 간선을 추가한 후 대각선 간선(snake)으로 이어지는 형태여야 한다. D의 최소값은 0이며, 이는 두 시퀀스가 동일한 경우이다. 반대로 D의 최대값은 N + M이다. X의 모든 요소를 삭제하고 Y의 모든 요소를 X에 삽입하는 것이 최악의 경우의 편집 스크립트이기 때문이다. D, 즉 최소 편집 스크립트(SES)의 길이를 구하기 위해 0부터 N + M까지 루프를 실행하면 충분하다.

for D in 0...N + M

다음으로, D-path가 k-line에서 가장 멀리 도달할 수 있는 지점을 생각해 보자. 아래와 같이, k-line에서 수평으로 이동하면 (k+1)-line에 도달하고, 수직으로 이동하면 (k-1)-line에 도달한다. 빨간색 분필 선이 이를 보여준다.

따라서 D-path의 끝점은 여러 k-line에 위치할 수 있다. 위에서 언급한 대로 다음 경로((D+1)-path)를 얻기 위해 이 정보가 필요하다. 사실, D-path는 k-line에서 끝나야 하며, 여기서 k는 { -D, -D + 2, ....., D - 2, D } 범위에 속한다. 이는 매우 간단하다. 시작점인 source는 (k=0)-line에 위치한 (0, 0)이다. D는 비대각선 간선의 수이며, 비대각선 이동은 현재 k-line을 (k±1)-line으로 변경한다. 0은 짝수이므로, D가 짝수면 D-path는 (짝수_k)-line에서 끝나고, D가 홀수면 D-path는 (홀수_k)-line에서 끝난다.

검색 루프의 개요는 다음과 같다.

for D in 0...N + M {
    for k in stride(from: -D, through: D, by: 2) {
        // k-line에서 가장 멀리 도달한 D-path의 끝점을 찾는다.
        if furthestReachingX == N && furthestReachingY == M {
            // D-path가 최단 경로이다.
            // D가 최소 편집 스크립트의 길이이다.
            return
        }
    }
}

k-line에서의 D-path는 다음과 같이 분해할 수 있다.

Myers 알고리즘의 핵심은 다음과 같다.

이를 통해 계산량이 줄어든다.

public struct MyersDifferenceAlgorithm<E: Equatable> {
    public static func calculateShortestEditDistance(from fromArray: Array<E>, to toArray: Array<E>) -> Int {
        let fromCount = fromArray.count
        let toCount = toArray.count
        let totalCount = toCount + fromCount
        var furthestReaching = Array(repeating: 0, count: 2 * totalCount + 1)

        let isReachedAtSink: (Int, Int) -> Bool = { x, y in
            return x == fromCount && y == toCount
        }

        let snake: (Int, Int, Int) -> Int = { x, D, k in
            var _x = x
            while _x < fromCount && _x - k < toCount && fromArray[_x] == toArray[_x - k] {
                _x += 1
            }
            return _x
        }

        for D in 0...totalCount {
            for k in stride(from: -D, through: D, by: 2) {
                let index = k + totalCount
            
                // (x, D, k) => k_line에서 스크립트 수가 D인 x 위치
                // 스크립트는 삽입 또는 삭제를 의미한다.
                var x = 0
                if D == 0 { }
                    // k == -D, D는 경계 k_line이 된다.
                    // k == -D일 때, k - 1_line에서 D - 1이 불가능한 경우 Edit Graph에서 오른쪽으로 이동(삭제 스크립트)한다.
                    // k == D일 때, k + 1_line에서 D - 1이 불가능한 경우 Edit Graph에서 아래로 이동(삽입 스크립트)한다.
                    // 가장 멀리 도달한 x 위치가 계산 우선순위가 높다. (x, D - 1, k - 1), (x, D - 1, k + 1)
                else if k == -D || k != D && furthestReaching[index - 1] < furthestReaching[index + 1] {
                    // 초기 x 위치를 얻는다.
                    // D - 1인 k + 1_line에서 가장 멀리 도달한 X 위치를 사용한다.
                    // 즉, (x, D, k)를 (x, D - 1, k + 1) + 아래로 이동 + snake로 얻는다.
                    // Edit Graph에서 아래로 이동하는 것은 삽입 스크립트와 호환된다.
                    x = furthestReaching[index + 1]
                } else {
                    // 초기 x 위치를 얻는다.
                    // D - 1인 k - 1_line에서 가장 멀리 도달한 X 위치를 사용한다.
                    // 즉, (x, D, k)를 (x, D - 1, k - 1) + 오른쪽으로 이동 + snake로 얻는다.
                    // Edit Graph에서 오른쪽으로 이동하는 것은 삭제 스크립트와 호환된다.
                    x = furthestReaching[index - 1] + 1
                }
                
                // snake
                // 대각선 이동은 0 비용으로 수행할 수 있다.
                // `동일` 스크립트가 필요한가?
                let _x = snake(x, D, k)
                
                if isReachedAtSink(_x, _x - k) { return D }
                furthestReaching[index] = _x
            }
        }

        fatalError("Never comes here")
    }
}