git diff algorithm (myers algorithm) - 2

공간 복잡도를 linear로 개선하는 방법입니다

 

paper를 기준으로 글을 작성했습니다

 

Lemma 3

paper는 어렵게 되어있지만,

D-path는 (0,0)에서 (x,y)인 D/2-path, (x,y)에서 (N,M)인 D-path 두개로 쪼개질 수 있다는 설명입니다

 

알고리즘

Divide and Conquer를 활용하여 iteration한번 당 edit graph의 중간 지점을 찾는 것입니다

space optimized LCS

 

중간 지점을 찾는 방법은,

시작지점에서 1칸 움직이고 끝지점에서 1칸 움직이고를 overlap할 때까지 반복하는 것입니다

(개인적으로는, d를  미리 구한 다음에 시작지점에서 d/2 만큼 반복하고 끝지점에서 d/2만큼 돌린다음에 겹치는 지점을 찾으면  메모리를 더 효율적으로 사용할 수 있을것 같습니다)

 

그림으로 표현하겠습니다

divide and conquer explanation

중간 snake(overlap이라고 되어있는 부분)을 찾습니다

(실제로는 -D부터 D로 탐색하기 때문에 아래쪽에 있는 overlap이 선택됩니다)

노란색 sub region으로 나눠서 다시 똑같은 걸 수행합니다

 

알고리즘은 다음과 같습니다

middle snake algorithm

∆ 가 홀수면 d도 홀수고 ∆ 가 짝수면 d도 짝수이기 때문에

overlap을 어느 구간에서 찾을 수 있을지 정할수있습니다

 

그 옆에 있는 k ∈ [∆ − (D − 1) ,∆ + (D − 1)] 도 살펴보겠습니다

reverse path는 x축으로(왼쪽) 최대 -(D-1)만큼 이동한 상태입니다 (path 1당 가로 또는 세로 한번 이동함)

또한 y축으로도(위쪽) 최대 -(D-1)만큼 이동한 상태입니다

 

따라서 k의 범위가 k ∈ [∆ − (D − 1) ,∆ + (D − 1)] 로 좁혀집니다

극단적으로 예시를 들자면,

그림에서 대각선 경로가 아예 없다고 가정하면 (0,6)에서는 overlap되는지 체크할 필요가 없습니다

왜나하면 reverse path는 5번 움직인 상태인데 (0,6)에 도달할 수 없기 때문입니다

 

시간복잡도

시간복잡도를 살펴보겠습니다

middle snake의 시간복잡도는 O(PD)입니다 (P=N+M)

T(P,D) = αPD + T(P1, [(D+1)/2]) + T(P2, [D/2]) (D>1이고 P1 + P2 ≤ P).

T(P,D) = βPD (D>1)

 

귀납적으로 paper에서는 T(P,D) ≤ 3αPD + βP 라고 정의하고 귀납적으로 증명하고 있습니다

(별로 와닿지는 않네요)

 

[(D+1)/2] ≤ 2D/3 를 쓰면 귀납적으로 증명가능합니다

 

• D = 1일 때, ≤ 3αPD + βP 를 만족
• D = k (k > 1)일 때, T(P, k) ≤ 3αPk + βP 라고 가정
• D = k+1일 때, 주어진 재귀 관계식에 따라
  • T(P, k+1) ≤ αP(k+1) + T(P1, [(k+2)/2]) + T(P2, [(k+1)/2])
  • 귀납적으로 T(P, k+1) ≤ αP(k+1) + 2αP1(k+1) + βP1 + 2αP2(k+1) + βP2
  • P1 + P2 ≤ P이므로 T(P, k+1) ≤ 3αP(k+1) + βP

• 따라서, D = k+1일 때도 T(P, D) ≤ 3αPD + βP 가 성립

(P를 가지고 똑같이 해도 성립합니다)

 

시간복잡도는 greedy 방법과 동일하게 O(D(N+M))입니다

 

공간복잡도

middle snake : O(D)

input : O(N+M)

recursion stack : O(logD)

 

따라서 O(N+M)입니다

코드

이제 코드를 보겠습니다

def middle_snake(A,B,N,M):
    MAX = (M+N+1)//2
    V = [0] * (2 * MAX + 1)
    V_r = [N] * (2 * MAX + 1) # V_reverse
    delta = N-M
    is_delta_odd = delta%2==1
    is_delta_even =delta%2==0
    
    for D in range(MAX+1):
        for k in range(-D,D+1,2): # 정방향 탐색
            if k == -D or (k != D and V[k - 1 + MAX] < V[k + 1 + MAX]):  # 오른쪽으로 한 칸
                x = V[k + 1 + MAX]
            else:  # 아래로 한 칸
                x = V[k - 1 + MAX] + 1
            y = x - k
            
            # snake
            while x < N and y < M and A[x] == B[y]:
                x, y = x + 1, y + 1

            V[k + MAX] = x

            if is_delta_odd and delta-(D-1)<=k<=delta+(D-1) and x>=V_r[k-delta+MAX]:
                snake_length = x - V_r[k-delta+MAX]
                return [2*D-1,x-snake_length,y-snake_length,snake_length] # D의 크기, (x,y)좌표, snake 길이
            
        for k in range(-D,D+1,2): # 역방향 탐색
            if k==D or (k!=-D and V_r[k-1+MAX] < V_r[k+1+MAX]): # 위쪽으로 한칸
                x = V_r[k-1+MAX]
            else:  # 왼쪽으로 한칸
                x = V_r[k+1+MAX]-1
            y = x - k - delta
            while x > 0 and y > 0 and A[x-1] == B[y-1]:
                x, y = x - 1, y - 1

            V_r[k + MAX] = x

            if is_delta_even and -D <= k + delta <= D and V[k+delta+MAX]>=x:
                return [2*D,x,y,V[k+delta+MAX]-x] # D의 크기, (x,y)좌표, snake 길이
            

def LCS(A,B,N,M):
    ret = []
    if N==0:
        for i in range(M):
            ret.append(f' +{B[i]}')
        return ret
    elif M==0:
        for i in range(N):
            ret.append(f' -{A[i]}')
        return ret

    D,x,y,snake_length = middle_snake(A,B,N,M) # D의 크기, (x,y)좌표, snake 길이

    ret += LCS(A[:x],B[:y],x,y)
    
    for i in range(x,x+snake_length):
        ret.append(f' {A[i]}')
    ret += LCS(A[x+snake_length:],B[y+snake_length:],N-(x+snake_length),M-(y+snake_length))
    return ret

    
# 두 문자열 예제
A = "abcabba"
B = "cbabac"
print(LCS(A, B, len(A), len(B))) #  [' +c', ' -a', ' b', ' -c', ' a', ' b', ' -b', ' a', ' +c']

A = "abc"
B = "yabc"
print(LCS(A, B, len(A), len(B))) #  [' +y', ' a', ' b', ' c']

paper에서는 LCS에서 output[]으로만 되어있어 snake인지 추가인지 삭제인지 알 수 없습니다

그래서 [IF D > 1] 부분을 제거하고 다르게 구현했습니다

더 최적화를 하려면 A[x:] 같은 부분을 없애고 좌표로 처리하게 하고 ret를 함수 밖에 정의해서 ret를 LCS가 반환하지 않게 구현하면 될것같습니다

또한 V를 동적으로 할당하면 조금 더 메모리를 효율적으로 사용가능할것같습니다

 

 

4c. An O( (M + N) lg(M + N) + D**2 ) Worst-Case Variation

suffix tree를 쓰면 시간복잡도가 위와 같아 두 문자의 차이가 작을 때 유용합니다

하지만 coefficient가 크고, 공간복잡도가 높기 때문에 실제로는 안쓴다고 합니다

 

 

 

 

 

틀린 부분 있으면 댓글 부탁드립니다

 

 

http://www.xmailserver.org/diff2.pdf