이 아티클이 마음에 드신다면 구현을 통해 Git의 내부를 설명하는 책을 출간했습니다: Git 구축하기.
프로그래머라면 아마도 Git과 같은 버전 관리 시스템을 사용하면서 많은 시간을 Diff를 살펴보는 데 할애할 것입니다. 진행 중인 커밋되지 않은 작업을 확인하고, 단일 커밋에서 변경된 내용을 확인하고, 병합을 수행하기 전에 두 브랜치를 비교하는 등 다양한 용도로 사용합니다. Diff는 소프트웨어에서 변경된 내용을 이해하는 언어입니다.
Diff는 사람들이 읽을 수 있을 뿐만 아니라 버전 관리 시스템에서 변경 사항을 자동화하는 데 사용됩니다. 다른 사람에게 diff를 이메일로 보내면, 그 사람은 패치 또는 git apply 명령을 사용하여 작업 복사본에 병합할 수 있습니다. git merge는 두 개 이상의 변경 이력을 조정하고 병합하여 하나의 트리를 생성해야 하며, 종종 동일한 파일 내의 변경 사항을 조정합니다. git add --patch를 사용하면 전체 파일을 인덱스에 추가하지 않고 작업 복사본 파일에서 개별 변경 사항을 선택할 수 있으며, 사용자가 diff를 읽고 git이 이를 인덱스된 파일 버전에 선택적으로 적용하는 작업이 모두 포함됩니다. 또한 일부 버전 관리 시스템은 각 커밋에 대한 모든 코드의 스냅샷을 저장하는 대신 버전 간의 차이점을 프로젝트 기록을 저장하는 주요 방법으로 사용합니다.
따라서 Diff는 버전 관리의 핵심이지만 어떻게 생성되는지 잘 생각해보지 않았을 수도 있습니다. Diff를 읽으면 어떤 것을 변경 사항으로 표시해야 하는지 분명해 보이는 경우가 많습니다. 파일에 새 함수를 삽입하거나, 중복된 함수를 삭제하거나, 섹션을 다시 작성하는 것이 무엇을 의미하는지에 대한 직관적인 정신 모델이 있습니다. 하지만 변경에는 눈에 보이는 것보다 훨씬 더 많은 것이 있으며, 다양한 결과를 만들어내는 여러 가지 방법이 있습니다.
Diff를 계산하는 방법과 이를 수행하는 함수를 작성하는 방법에 대해 잠시 생각해 보세요. Diff 프로그램은 변경된 부분만 표시하고 동일한 부분은 표시하지 않는다는 것을 눈치채셨을 것입니다. 파일에서 어떤 부분이 변경되지 않았는지 어떻게 확인할 수 있을까요? 두 버전 간에 차이점을 찾았다면 각 버전에서 텍스트가 다시 일치하는 다음 줄을 어떻게 찾을 수 있을까요? 보기보다 더 복잡합니다!
이 글 시리즈에서는 Git에서 사용하는 기본 diff 알고리즘에 대해 안내해드리려고 합니다. 이 알고리즘은 유진 마이어스(Eugene W. Myers)가 개발했으며, 원본 논문은 온라인에서 확인할 수 있습니다. 이 논문은 매우 짧지만 수학적으로 매우 밀도가 높고 작동을 증명하는 데 초점을 맞추고 있습니다. 이 글에서는 알고리즘이 실제로 무엇을 하고 어떻게 작동하는지에 대한 자세한 설명을 통해 엄밀하지는 않지만 보다 직관적으로 설명할 것입니다.
이 첫 번째 글에서는 알고리즘이 달성하고자 하는 기본 모델을 설명하고 한 버전에서 다른 버전으로 이동하기 위한 가장 간단한 편집 집합이 어떻게 작동하는지에 대한 예제를 살펴봅니다.
백서의 예제를 사용하려면 두 문자열의 차이를 계산하고 싶다고 가정해 보겠습니다:
- a = ABCABBA
- b = CBABAC
"차이"란 문자열 a를 문자열 b로 변환하는 편집 시퀀스를 의미합니다. 이러한 시퀀스 중 하나는 단순히 a의 각 문자를 삭제한 다음 b에 각 문자를 삽입하거나 일반적인 차이 표기법을 사용하는 것입니다:
- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C그러나 이것은 우리에게 많은 것을 알려주지 않기 때문에 좋은 품질의 차이점이라고 생각하지 않습니다. 소스 코드를 변경하면 일반적으로 파일의 많은 부분이 수정되지 않은 상태로 남기 때문에 삽입되거나 삭제된 코드 섹션을 확인하고 싶습니다. 전체 파일이 제거되고 새 버전으로 대체되는 것을 보여주는 Diff는 우리에게 큰 도움이 되지 않습니다.
이 두 문자열의 더 나은 차이점은 다음과 같습니다:
- A
- B
C
+ B
A
B
- B
A
+ C이렇게 하면 B를 생성하기 위해 A를 가장 적게 변경하므로 실제로 변경된 내용을 더 잘 시각화할 수 있습니다. 이 방법만이 유일한 해결책은 아니며, 예를 들어 다음과 같은 방법도 유효합니다:
1. - A 2. - A 3. + C
- B + C - A
C B B
- A - C - C
B A A
+ A B B
B - B - B
A A A
+ C + C + C하지만 모두 최소한의 편집만 가능하며, 이 경우에는 5번만 편집할 수 있습니다. 흥미로운 점은 문자열 사이에서 동일하다고 간주하는 섹션과 편집을 수행하는 순서가 다르다는 것입니다. Diff를 보면 변경된 내용만 표시한다고 직관적으로 생각할 수 있지만, 이 예제는 두 파일 간의 차이에 대해 다양한 해석이 가능하다는 것을 보여줍니다.
따라서 diff 알고리즘의 목적은 특정 바람직한 속성을 가진 diff를 생성하기 위한 전략을 제공하는 것입니다. 일반적으로 Diff는 가능한 한 작게 생성하는 것이 좋지만 다른 고려 사항도 있습니다. 예를 들어, 무언가를 변경할 때 그 반대의 경우가 아니라 삭제 후 삽입을 보는 데 익숙할 것입니다. 즉, 위의 솔루션 3보다는 솔루션 2를 더 선호할 것입니다. 또한 전체 코드 블록을 변경할 때는 여러 개의 삭제와 삽입이 서로 섞여 있는 것이 아니라 전체 청크가 삭제된 후 새 코드가 삽입되는 것을 보고 싶을 것입니다.
Good: - one Bad: - one
- two + four
- three - two
+ four + five
+ five + six
+ six - three또한 코드 구조에 대한 아이디어에 따라 삭제되거나 삽입된 코드가 표시되기를 원할 수도 있습니다. 예를 들어 메서드를 삽입하는 경우 해당 메서드의 끝이 이전 메서드의 끝이 아니라 새로운 메서드로 간주되기를 원할 수 있습니다:
+ Good
class Foo
def initialize(name)
@name = name
end
+
+ def inspect
+ @name
+ end
end- Bad
class Foo
def initialize(name)
@name = name
+ end
+
+ def inspect
+ @name
+ end
end마이어스의 알고리즘은 이러한 전략 중 하나에 불과하지만, 속도가 빠르며 대부분의 경우 좋은 품질의 차이를 생성합니다. 이 알고리즘은 변경하기 전에 동일한 줄을 최대한 많이 소비하여 '잘못된 끝' 문제를 피하고, 선택지가 주어졌을 때 삽입보다 삭제를 선호하여 삭제가 먼저 나타나도록 하는 욕심을 부림으로써 이러한 작업을 수행합니다.
마이어스 논문은 최단 편집 스크립트(SES)를 찾는 것이 그래프 검색으로 모델링될 수 있다는 아이디어에 기반하고 있습니다. a = ABCABBA, b = CBABAC라는 두 문자열을 가지고 a에서 b로 이동할 수 있는 모든 방법을 그래프로 만들어 봅시다.
아래 표시된 그리드의 (x, y) 좌표는 편집 과정의 단계에 해당하며, (0,0)에는 문자열 a가 있으므로 편집을 시작하지 않은 상태입니다. 오른쪽으로 이동(x 증가)하는 것은 a에서 문자를 삭제하는 것에 해당하며, 예를 들어 (1,0)으로 이동하면 a에서 첫 번째 A를 삭제한 것입니다. 아래쪽으로 이동(y 증가)하는 것은 b에서 문자를 삽입하는 것에 해당하며, 예를 들어 (1,0)에서 (1,1)로 이동하면 b에서 첫 번째 C를 삽입하므로 편집된 문자열은 CBCABBA가 됩니다. (4,3)의 위치에서 ABCA를 CBA로 변환했지만, 여전히 BBA를 BAC로 변환해야 합니다. 오른쪽 아래 위치(7,6)는 문자열 a를 문자열 b로 완전히 변환하는 위치에 해당합니다.
오른쪽과 아래쪽으로 이동하는 것뿐만 아니라 일부 위치에서는 대각선으로 이동할 수도 있습니다. 이는 두 문자열의 위치 인덱스에 동일한 문자가 있을 때 발생합니다. 예를 들어 a의 세 번째 문자와 b의 첫 번째 문자가 모두 C이므로 위치 (2,0)는 (3,1)로 이어지는 대각선을 갖습니다. 이는 두 문자열에서 동일한 문자를 사용하며 아무것도 삭제하거나 삽입하지 않는 경우에 해당합니다.
A B C A B B A
o-----o-----o-----o-----o-----o-----o-----o 0
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 1
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 2
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 3
| | \ | | | \ | \ | |
B | | \ | | | \ | \ | |
| | \ | | | \ | \ | |
o-----o-----o-----o-----o-----o-----o-----o 4
| \ | | | \ | | | \ |
A | \ | | | \ | | | \ |
| \ | | | \ | | | \ |
o-----o-----o-----o-----o-----o-----o-----o 5
| | | \ | | | | |
C | | | \ | | | | |
| | | \ | | | | |
o-----o-----o-----o-----o-----o-----o-----o 6
0 1 2 3 4 5 6 7마이어스 알고리즘의 기본 개념은 매우 간단합니다. 가능한 한 적은 수의 이동으로 (0,0)에서 (7,6)(오른쪽 아래)으로 이동하는 것입니다. "이동"이란 오른쪽으로 한 걸음(a에서 삭제) 또는 아래쪽으로 한 걸음(b에서 삽입)을 이동하는 것입니다. A에서 B로 이동하기 위해 취할 수 있는 최대 이동 수는 두 문자열의 길이를 합친 13개입니다.
그러나 대각선 경로를 걷는 것은 변경에 해당하지 않기 때문에 자유롭기 때문에 대각선 이동 횟수를 최대화하고 오른쪽/아래로 이동하는 횟수를 최소화하고자 합니다. 위의 예는 실제로 5번만 편집하면 A에서 B로 이동할 수 있음을 보여주며, 마이어스는 그 경로를 찾기 위한 전략을 제공합니다.
알고리즘이 어떻게 작동하는지에 대한 직관을 키우기 위해 그래프를 살펴봅시다. 오른쪽 아래 위치로 가는 최단 경로를 찾기 위해 (0,0)에서 끝까지 도달하는 경로를 찾을 때까지 가능한 모든 경로를 차례로 탐색해 보겠습니다. 이 과정을 따라가는 동안 위의 그리드를 잘 보관해 두는 것이 좋습니다.
초기 위치를 (0,0)에 기록하는 것으로 시작하겠습니다.
0,0이 위치에서 아래쪽으로 이동하여 (0,1)에 도달하거나 오른쪽으로 이동하여 (1,0)에 도달하는 두 가지 옵션이 있습니다.
0,0 --- 1,0
|
|
0,1이제 (0,1)을 생각해 봅시다. 여기서 아래로 이동하면 (0,2)에 도달하지만, 거기에서 (1,3), (1,3)에서 (2,4)까지 대각선이 있고 대각선 이동은 자유이므로 (0,1)에서 아래로 이동하면 단 한 번의 이동 비용으로 (2,4)에 도달한다고 말할 수 있습니다. 따라서 (0,1)에서 (2,4)로의 이동을 한 걸음으로 표시하겠습니다.
(0,1)에서 오른쪽으로 이동하면 (1,1)이 되고, 거기에서 다시 (2,2)까지 대각선이 있습니다. 이 두 이동을 모두 걸음에 표시해 봅시다.
0,0 --- 1,0
|
|
0,1 --- 2,2
|
|
2,4이제 (0,0)에서 오른쪽으로 이동하여 (1,0)으로 이동한 다른 분기를 고려해 봅시다. (1,0)에서 아래로 이동하면 (1,1)이 되고, 방금 알아낸 것처럼 (2,2)가 됩니다. (1,0)에서 오른쪽으로 이동하면 (2,0)이 되고, (3,1)과 대각선인 (2,0)이 됩니다. 다시 한 번 이 두 단계를 모두 기록하겠습니다.
(2,2)를 (0,1)이 아닌 (1,0)을 통해 방문한 것으로 기록하는 이유는 조금 후에 명확해질 것입니다. 직관적인 이해를 돕기 위해 오른쪽으로 먼저 이동한다는 것은 삭제를 먼저 수행한다는 의미이며, 일반적으로 삭제가 삽입보다 먼저 표시되기를 원한다는 점을 고려하세요.
0,0 --- 1,0 --- 3,1
| |
| |
0,1 2,2
|
|
2,4이제 그래프를 두 수 깊이까지 완전히 탐색했으며 세 번째 수에서 시작할 수 있습니다. (2,4)에서 아래로 이동하면 (2,5)가 되고, 거기에서 (3,6)으로 가는 대각선이 있습니다. (2,4)에서 오른쪽으로 이동하면 (3,4)가 되고, 여기서 다시 대각선이 (4,5)로 이동합니다.
0,0 --- 1,0 --- 3,1
| |
| |
0,1 2,2
|
|
2,4 --- 4,5
|
|
3,6다음으로 (2,2)를 고려합니다. 거기에서 오른쪽으로 이동하면 앞서 본 것처럼 (3,2)로 이동하고 거기에서 대각선을 따라 (5,4)로 이동합니다. 그러나 아래로 이동하면 (2,3)으로 이동하고 거기에서 대각선이 없는 새로운 상황이 발생합니다. 이제 범용 그래프 검색을 수행한다면 (2,4)에서 오른쪽으로 이동한 결과와 (2,2)에서 아래로 이동한 결과, 즉 두 가지를 모두 기록해야 합니다:
0,0 --- 1,0 --- 3,1
| |
| |
0,1 2,2 --- 5,4
| \
| \
2,4 - 2,3
| \
| 4,5
3,6그러나 우리가 살펴보고 있는 특정 그래프의 구조는 특정 편집 후 도달할 수 있는 최적의 위치를 저장하는 것으로 충분하다는 것을 의미합니다. 위의 기록은 두 번 삽입한 다음 삭제(아래로 두 번, 오른쪽으로 두 번)하면 (4,5)가 되는 반면, 먼저 삭제한 다음 두 번 삽입하면 (2,3)이 되는 것을 보여줍니다. 따라서 (4,5) 결과를 유지하고 (2,3)은 버리므로 어떤 순서로든 한 번 삭제하고 두 번 삽입하면 (4,5)가 가장 좋은 위치에 도달할 수 있음을 나타냅니다.
0,0 --- 1,0 --- 3,1
| |
| |
0,1 2,2 --- 5,4
|
|
2,4 --- 4,5
|
|
3,6마지막으로 깊이 2 스캔에서 (3,1)을 방문합니다. 거기에서 아래로 이동하면 (3,2)가 되고, (5,4)와 대각선으로 이어지므로 다시 (2,2)에서 오른쪽으로 이동하는 것이 아니라 (3,1)에서 아래로 이동하는 것으로 기록할 것입니다. (3,1)에서 오른쪽으로 이동하면 (5,2)와 대각선인 (4,1)이 됩니다.
다음은 세 번의 이동 후 완성된 기록입니다:
0,0 --- 1,0 --- 3,1 --- 5,2
| | |
| | |
0,1 2,2 5,4
|
|
2,4 --- 4,5
|
|
3,6지금쯤이면 요령을 익혔을 테니 나머지 동작을 따라 해보겠습니다. (3,6)에서 아래로 이동할 수 없고, 거기에서 오른쪽으로 이동하면 (4,6)이 나오는데, (4,5)에서도 아래쪽으로 이동할 수 있으므로 그렇게 표시하겠습니다. (4,5)의 오른쪽은 (5,5)입니다.
0,0 --- 1,0 --- 3,1 --- 5,2
| | |
| | |
0,1 2,2 5,4
|
|
2,4 --- 4,5 --- 5,5
| |
| |
3,6 4,6(5,2)에서 아래로 이동하면 (7,5)가 되고, (5,2)에서 오른쪽으로 이동하면 (7,3)이 되므로 스캔의 네 번째 행이 완성됩니다.
0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3
| | |
| | |
0,1 2,2 5,4 --- 7,5
| |
| |
2,4 --- 4,5 5,5
| |
| |
3,6 4,6이제 다섯 번째 행을 시작합니다. a에서 b까지 5개의 편집만 필요한 차이가 있다는 것을 알고 있으므로, 이 행은 오른쪽 아래 위치인 (7,6)을 찾을 것으로 예상합니다.
(4,6)에서 아래쪽에는 아무것도 없고, 그 오른쪽에는 (5,6)이 있으며, 이 역시 (5,5)에서 아래쪽입니다. (5,5)의 오른쪽은 (6,5)입니다.
0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3
| | |
| | |
0,1 2,2 5,4 --- 7,5
| |
| |
2,4 --- 4,5 5,5 --- 6,5
| | |
| | |
3,6 4,6 5,6마지막으로, (7,5)에서 아래로 이동하면 (7,6)이 최종 위치가 됩니다! 이것은 오른쪽, 오른쪽, 오른쪽, 아래, 아래, 오른쪽으로 이동하여 도달 한 (6,5)보다 확실히 낫기 때문에 이동 추적에서 이를 대체합니다.
0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3
| | |
| | |
0,1 2,2 5,4 --- 7,5
| | |
| | |
2,4 --- 4,5 5,5 7,6
| | |
| | |
3,6 4,6 5,6두 개의 문자열이 주어지면 두 문자열 사이의 편집 공간을 나타내는 그래프를 통해 최단 경로를 찾는 것이 알고리즘의 기본 개념입니다. 그래프를 통해 가능한 모든 경로를 폭 넓게 먼저 탐색하고 최종 위치에 도달하면 바로 중단합니다.
다음 글에서는 마이어스가 실제로 이 프로세스를 어떻게 표현하는지 살펴보고, 이를 코드로 구현하는 방법을 살펴보겠습니다.