깃에서 변경 내용을 어떻게 추적할까 궁금해져 찾아봤습니다
String A,B가 다음과 같이 주어져있다고 합시다
A = abcabba and B = cbabac
A에서 문자를 삭제하거나 추가해서 B가 되었다고 했을 때,
[삭제+추가]가 최소가 되는 방법을 찾는 알고리즘 입니다
이를 shortest edit script(SES)이라고합니다
위 문제를 다르게 생각할 수 있습니다
x축은 A, y축은 B입니다
오른쪽으로 이동하면 문자를 삭제한다는 뜻이고,
왼쪽으로 이동하면 문자를 추가한다는 뜻입니다
대각선 방향은 문자가 서로 같아 삭제 또는 추가를 하지 않아도 된다는 것을 의미합니다
Greedy Algorithm
SES를 찾는 방법을 생각해봅시다.
그 전에 두가지 lemma가 필요합니다
paper에서 diagonal k는 x-y=k를 만족하는 (x,y)점들의 집합이라고 정의합니다
그리고 D-path는 edit graph가 D만큼의 경로를 가진다는 것을 의미합니다
예를들어, A=B라면 문자를 추가 또는 삭제할 필요가 없으므로 0-path 입니다
1. D-path가 주어졌을때 가장 끝점 (N,M)은 diagonal k ∈ { −D, −D + 2, . . . D − 2, D }에 있다 (A의 길이를 N, B의 길이를 M이라고 정의하겠습니다)
paper는 어렵게 설명되어 있지만, 0-path부터 차근차근 생각하면 쉽게 이해할 수 있습니다
0-path라면 N=M일 수 밖에 없으므로 (N,M)으로 가능한 diagonal k는 {0} 밖에 없다
1-path는 대각선 이동 외 가로로 한번 또는 새로로 한번 이동했다는 의미 입니다
(N,M)으로 가능한 diagonal k는 {-1,1}입니다
조금 확장해봅시다
D-path는 [가로이동 + 세로이동 = D] 입니다
대각선 이동 외 가로로 D번 이동하고 세로로 0번 이동하면 N-M = D
대각선 이동 외 가로로 D-1번 이동하고 세로로 1번 이동하면 N-M = D-2
...
대각선 이동 외 가로로 1번 이동하고 세로로 D-1번 이동하면 N-M = -D+2
대각선 이동 외 가로로 0번 이동하고 세로로 D번 이동하면 N-M = -D
2. D-path는 D-1-path 및 1-path로 분해될 수 있다. 이때 두가지 옵션 중 하나로 분해된다
- diagonal k − 1 에 있는 (D−1)-path 에서 오른쪽으로 1칸 이동하고 snake(대각선으로 갈 수 있으면 대각선으로 최대한 갔다는 뜻)
- diagonal k + 1 에 있는 (D−1)-path 에서 아래로 1칸 이동하고 snake
위 그림을 보면 쉽게 이해할 수 있습니다
어떤 점이 오른쪽으로 한칸 이동하면 k++, 아래로 이동하면 k--입니다
따라서 D-path를 (D−1)-path 와 1-path로 분해할 때,
D-path인 지점과 (D−1)-path의 두 점의 k 차이가 2이상나면 1-path로 연결할 수 없습니다
위 두가지 lemma로 SES를 찾는 알고리즘을 보겠습니다
V_d[k]의 의미는 (D,K) = (d,k) 인 end point에서의 x좌표입니다 (y 좌표는 k를 알기 때문에 복구 가능)
V를 한개만 할당하면 최소 d를 찾을 수 있습니다.
하지만, 복구가 불가능합니다
따라서 효율적인 공간복잡도 사용을 위해,
처음에는 D를 찾고 그 다음, SES를 찾는 방법을 택할 수있습니다
D를 먼저 찾아봅시다
def min_D(A, B):
N, M = len(A), len(B)
MAX = N + M
V = [0] * (2 * MAX + 1)
for D in range(MAX+1): # (0~M+N)
for k in range(-D, D + 1, 2):
# V[k]의 인덱스를 V 배열의 중간으로 맞추기 위해 + MAX를 더함
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 x >= N and y >= M:
return D
# 두 문자열 예제
A = "abcabba"
B = "cbabac"
print(min_D(A, B))
d를 바탕으로 SES를 구해봅시다
def min_D(A, B):
N, M = len(A), len(B)
MAX = N + M
V = [0] * (2 * MAX + 1)
for D in range(MAX+1): # (0~M+N)
for k in range(-D, D + 1, 2):
# V[k]의 인덱스를 V 배열의 중간으로 맞추기 위해 + MAX를 더함
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 x >= N and y >= M:
return D
# 두 문자열 예제
A = "abcabba"
B = "cbabac"
print(min_D(A, B))
def backtrack(A, B, V, MAX):
N, M = len(A), len(B)
D = MAX
k = N - M # 마지막 지점의 k 값
result = []
print(V)
for D in range(MAX,0,-1):
x = V[D][k + MAX]
y = x - k
print(x,y)
# 1. 대각선 이동 (일치 구간 추적)
while x > 0 and y > 0 and A[x-1] == B[y-1]:
result.append(f" {A[x-1]}") # 일치하는 문자 기록 (대각선 이동)
x, y = x - 1, y - 1
if V[D-1][k + MAX - 1] + 1 == x: # 왼쪽에서 온 경우
prev_k = k-1
result.append(f" -{A[x - 1]}")
else: # 위에서 온 경우
prev_k = k+1
result.append(f" +{B[y - 1]}")
# 이전 경로로 이동
k = prev_k
# 결과 경로를 역순으로 출력
return ''.join(result[::-1])
def min_D(A, B):
N, M = len(A), len(B)
MAX = N + M + 1 # 최대 경로 길이
V = [0] * (2 * MAX + 1) # V 배열의 크기를 -MAX ~ +MAX로 설정
for D in range(MAX):
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
while x < N and y < M and A[x] == B[y]:
x, y = x + 1, y + 1
V[k + MAX] = x
if x >= N and y >= M:
return D
def greedy_myers(A, B):
N, M = len(A), len(B)
MAX = min_D(A, B) # 최적 경로 길이 계산
V = [[0] * (2 * MAX + 1) for _ in range(MAX + 1)] # 2D V 배열 생성
# 최적 경로 탐색
for D in range(1, MAX + 1):
for k in range(-D, D + 1, 2):
if k == -D or (k != D and V[D-1][k - 1 + MAX] < V[D-1][k + 1 + MAX]): # 아래로 한칸
x = V[D-1][k + 1 + MAX]
else: # 오른쪽 한칸
x = V[D-1][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[D][k + MAX] = x
# SES 경로 추적
return backtrack(A, B, V, MAX)
def greedy_myers(A, B):
N, M = len(A), len(B)
MAX = min_D(A,B)
V = [[0]* (2 * MAX + 1) for _ in range(MAX+1)]
for D in range(1, MAX+1):
for k in range(-D, D + 1, 2):
# V[k]의 인덱스를 V 배열의 중간으로 맞추기 위해 + MAX를 더함
if k == -D or (k != D and V[D-1][k - 1 + MAX] < V[D-1][k + 1 + MAX]): # 오른쪽으로 한 칸
x = V[D-1][k + 1 + MAX]
else: # 아래로 한 칸
x = V[D-1][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[D][k + MAX] = x
# V[D]를 구했으니 역추적으로 실제 path를 찾아야합니다
return backtrack(A, B, V, MAX)
# 두 문자열 예제
A = "abcabba"
B = "cbabac"
print(greedy_myers(A, B)) # -a -b c -a b +a b a +c
A = "abc"
B = "yabc"
print(greedy_myers(A, B)) # +y a b c시간복잡도는 O((M+N)D), 공간복잡도는 O(D**2)입니다
다음 글에서는 공간복잡도를 linear로 줄일 수 있는 방법을 알아보겠습니다
틀린 부분 있으면 말씀해주세요
http://www.xmailserver.org/diff2.pdf
https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
'알고리즘' 카테고리의 다른 글
| z-function (0) | 2024.12.27 |
|---|---|
| git diff algorithm (myers algorithm) - 2 (0) | 2024.10.06 |
| Segment tree : Lazy Propagation (range MAX update) (0) | 2024.06.06 |
| 패턴매칭 - KMP(Knuth–Morris–Pratt algorithm) 알고리즘 (0) | 2024.04.16 |
| 한붓그리기(Eulerian Trail) - Hierholzer’s Algorithm (0) | 2024.04.14 |