Git은 어떻게 파일의 변경 사항을 찾아낼까? (Diff 알고리즘)

개발자라면 매일 사용하는 명령어 git diff.

수천 줄의 코드 중에서 정확히 어떤 줄이 추가되고 삭제되었는지 순식간에 찾아내는 것을 보면 신기하지 않나요?

단순히 두 파일을 한 줄씩 비교하는 것일까요? 그랬다면 중간에 한 줄만 추가되어도 그 뒤의 모든 줄이 '변경됨'으로 표시되었을 것입니다.

Git은 Myers Diff Algorithm이라는 똑똑한 방법을 사용하여 '최소한의 변경'을 찾아냅니다.

1. 편집 거리 (Edit Distance)

두 문자열(또는 파일)의 차이를 계산하는 문제는 결국 "A를 B로 바꾸기 위해 필요한 최소 편집 횟수"를 구하는 문제입니다. 이를 편집 거리라고 합니다.

예를 들어 ABC를 ABD로 바꾸려면?

1. C를 삭제하고
2. D를 추가하면 됩니다. (편집 거리 2)

하지만 Git은 단순히 문자 단위가 아니라 줄(Line) 단위로 이 계산을 수행합니다.

2. 최장 공통 부분 수열 (LCS)

Myers 알고리즘의 핵심은 두 파일에서 **공통적으로 존재하는 가장 긴 부분(LCS: Longest Common Subsequence)**을 찾는 것입니다.

LCS를 찾고 나면 나머지는 쉽습니다.

• LCS에 포함되지 않은 A의 부분은 **삭제(-)**된 것입니다.
• LCS에 포함되지 않은 B의 부분은 **추가(+)**된 것입니다.

예를 들어:

• 파일 A: 1 2 3 4
• 파일 B: 1 3 5 4

여기서 LCS는 1 3 4입니다.
따라서 2는 삭제되었고, 5는 추가되었다고 판단할 수 있습니다.

3. Myers 알고리즘의 마법

Eugene W. Myers가 1986년에 발표한 이 알고리즘은 LCS 문제를 그래프 탐색 문제(최단 경로 찾기)로 변환하여 매우 효율적으로 풀어냅니다.

Git은 이 알고리즘을 기본으로 사용하며, 상황에 따라 histogram, patience 같은 다른 알고리즘을 옵션으로 제공하기도 합니다.

결론

우리가 무심코 보는 +와 - 기호 뒤에는 30년 넘게 검증된 우아한 수학적 알고리즘이 숨어 있습니다.

혹시 git diff 결과가 마음에 들지 않거나 너무 복잡하게 나온다면, git diff --algorithm=histogram을 시도해 보세요. 코드의 구조를 더 잘 반영한 결과를 보여줄 수도 있습니다.