Git Diff의 심장: Myers diff 알고리즘과 텍스트 변경 추적의 원리

깃(Git)의 git diff나 코드 리뷰 도구의 핵심은 두 텍스트 문서 사이의 변경점을 가장 깔끔하게 찾아내는 것입니다. 원본 문자열 시퀀스 A(길이 N)를 수정된 문자열 시퀀스 B(길이 M)로 변환하기 위해 필요한 최소한의 삽입(Insertion)과 삭제(Deletion) 작업 목록을 찾는 문제를 최단 편집 스크립트(SES, Shortest Edit Script)라고 부릅니다.

이 문제는 원본과 수정본에 모두 순서대로 보존된 가장 긴 공통 요소를 찾는 최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제와 정확히 수학적 쌍대(Dual) 관계를 이룹니다.

1986년 유진 마이어스(Eugene W. Myers)가 발표한 "An O(ND) Difference Algorithm and Its Variations" 논문은 GNU diff와 Git의 기본 엔진으로 채택되었습니다. 마이어스는 문제를 2차원 편집 그래프(Edit Graph) 상에서의 최단 경로 탐색 문제로 모델링했습니다:

• 가로(X축) 이동은 A에서의 삭제 연산에 해당합니다.
• 세로(Y축) 이동은 B에서의 삽입 연산에 해당합니다.
• A[x]와 B[y]의 줄 내용이 동일한 지점에서는 대각선 이동이 허용되며, 대각선 이동은 비용(Cost)이 0입니다.

마이어스는 대각선 k = x - y를 축으로 탐색을 진행하여, 차이점 개수 D가 작을수록 알고리즘이 O((N+M)D)의 압도적인 속도로 최단 경로를 찾아내도록 설계했습니다.

• 줄 단위 Diff: 소스 코드 파일 비교의 표준입니다. 고속으로 연산되지만, 80자짜리 긴 코드 줄에서 변수 이름 하나만 바뀐 경우에도 줄 전체가 삭제 후 추가된 것으로 표시됩니다.
• 단어 단위 Diff: 줄 단위 비교에서 변경이 감지된 청크에 대해 2차로 단어 단위 마이어스 알고리즘을 한 번 더 수행하여, 줄 내부의 구체적인 변경 단어를 하이라이트합니다.
• AST 기반 시맨틱 Diff: 소스 코드의 문법 트리를 비교하여, 단순히 변수명을 리팩토링했거나 함수 위치만 파일 아래로 옮긴 경우 불필요한 변경 노이즈를 걸러냅니다.

// 표준 Unified Diff 포맷 예시:
--- a/calculator.js
+++ b/calculator.js
@@ -10,4 +10,4 @@
 function calculateFinalTotal(price, taxRate) {
-    const shipping = 2500;
+    const shipping = 3000; // 배송비 인상 반영
     return price + (price * taxRate) + shipping;
 }

두 개발자가 공통의 조상 커밋(Base)에서 각자의 브랜치로 분기하여 작업한 뒤 하나로 합칠 때, Git은 단순 2자 비교가 아닌 3-Way Merge를 실행합니다:

1. 조상(Base)과 개발자 A의 변경점(diff(Base, A))을 추적합니다.
2. 조상(Base)과 개발자 B의 변경점(diff(Base, B))을 추적합니다.
3. A가 1015번째 줄을 고치고 B가 8090번째 줄을 고쳤다면, 변경 영역이 겹치지 않으므로 Git이 자동으로 양쪽 변경을 병합합니다.

하지만 두 브랜치가 동일한 줄 번호나 인접한 영역을 서로 다르게 수정했다면, Git은 판단을 유보하고 충돌 마커(<<<<<<< HEAD, =======, >>>>>>>)를 삽입하여 개발자에게 해결을 위임합니다.

브라우저 자바스크립트 엔진에서 수천 줄의 텍스트를 실시간으로 비교할 때 매번 문자열을 직접 비교하면 성능이 저하됩니다. 각 고유한 텍스트 줄을 정수 ID로 해싱(String Interning)한 뒤, 마이어스 그래프 탐색 시 가벼운 정수 배열끼리 비교하면 메모리 소비를 줄이고 연산 속도를 수십 배 향상시킬 수 있습니다. DevUtils Diff Checker를 활용하면 브라우저 안에서 안전하게 텍스트 차이를 비교할 수 있습니다.

// 고속 마이어스 알고리즘을 위한 줄 단위 정수 토큰화 최적화
export function tokenizeLinesToIntegers(rawText) {
    const lines = rawText.split(/\r?\n/);
    const stringPool = new Map();
    const tokenIds = [];
    
    for (const line of lines) {
        if (!stringPool.has(line)) {
            stringPool.set(line, stringPool.size);
        }
        tokenIds.push(stringPool.get(line)); // 무거운 문자열 대신 정수 ID로 매핑
    }
    return { tokenIds, lineCount: lines.length, lines };
}