Myers Diff 알고리즘

git diff, 코드 리뷰의 변경 줄 표시, 텍스트 에디터의 "변경 사항 추적" 뒤에 숨어 있는 최소 편집 스크립트 탐색 알고리즘

파일 하나를 딱 한 줄만 고쳐도 git diff는 수백 줄짜리 파일에서 바뀐 그 한 줄만 정확히 짚어낸다. 두 텍스트를 통째로 비교하면서도 이렇게 빠르고 정확한 이유는 1986년 Eugene W. Myers가 발표한 "An O(ND) Difference Algorithm" 덕분이다. 이 알고리즘은 두 시퀀스(문자열, 혹은 파일의 줄 배열)를 삽입(insert)과 삭제(delete) 연산만으로 서로 변환하는 최소 개수의 편집 스크립트를 찾는다 — 이때 "같은 내용은 최대한 그대로 두고, 다른 부분만 최소로 건드린다"는 것이 diff의 핵심 목표다.

데모 1 — 줄 단위 텍스트 diff (git diff 스타일)

이전 (old)

이후 (new)

함수 리팩터링 설정 값 변경 주석/오타 수정

왜 "가장 긴 줄을 통째로 지웠다 다시 쓰기"가 아닐까

가장 단순한 diff는 "예전 내용을 전부 지우고 새 내용을 전부 쓴다"이다. 그러나 이건 100줄짜리 파일에서 1줄만 바뀌어도 100줄 전체를 삭제 + 100줄 전체를 삽입으로 보여준다 — 리뷰어 입장에서는 최악이다. 좋은 diff는 바뀌지 않은 줄은 그대로 두고(context), 정말 달라진 부분만 최소한으로 표시해야 한다. 이 "최소 편집 스크립트를 찾는 문제"를 그래프 탐색 문제로 바꾼 것이 Myers의 통찰이다.

편집 그래프 (Edit Graph)

문자열 A(길이 N)를 가로축, B(길이 M)를 세로축으로 하는 (N+1)×(M+1) 격자를 그린다. 격자의 각 점 (x, y)는 "A를 x글자, B를 y글자 처리했다"는 상태다.

오른쪽 이동 (x→x+1) = A의 글자를 삭제
아래쪽 이동 (y→y+1) = B의 글자를 삽입
대각선 이동 (x→x+1, y→y+1, A[x]==B[y]일 때만) = 비용 0인 "일치" — 이를 스네이크(snake)라 부른다

(0,0)에서 (N,M)까지 가는 수많은 경로 중, 대각선(공짜 이동)을 최대한 많이 타면서 오른쪽·아래쪽 이동(편집 1회당 비용 1)을 최소로 쓰는 경로가 바로 최소 편집 스크립트다. 즉 diff 문제 = 이 격자 위의 최단 경로 탐색 문제다.

데모 2 — 편집 그래프와 D-경로 탐색 애니메이션

문자열 A

문자열 B

ABCABBA / CBABAC (Myers 논문 예시) kitten / sitting 가나다라마 / 가다라바

일치 가능 칸(회색 점선 대각선) 이번 라운드 D의 이동+스네이크 최종 최단 경로

핵심 아이디어 — "D번째 라운드"로 프론티어 넓히기

Myers 알고리즘은 편집 횟수 D = 0, 1, 2, … 를 순서대로 늘려가며, "정확히 D번의 편집으로 도달 가능한 가장 먼 지점"을 대각선(k = x - y)마다 하나씩 기록한다. 각 대각선에서 더 멀리 간 지점만 저장하면 되므로(짧은 경로는 이미 나쁜 선택), 라운드마다 대각선 개수(최대 2D+1개)만큼만 계산하면 된다. (N,M)에 도달하는 순간의 D가 바로 최소 편집 횟수다. 이는 마치 BFS가 계층(레벨)을 하나씩 넓혀가며 최단 경로를 찾는 것과 같은 원리다.

점화식

k = x - y  # 대각선 번호, 범위 -M..N
V[k] = 정확히 D번 편집으로 대각선 k에서 도달 가능한 가장 먼 x

라운드 D에서, 각 대각선 k (= -D, -D+2, …, D) 에 대해:
  V[k+1] > V[k-1] 이면 → 아래로 이동 (삽입), x = V[k+1]
  그 외 → 오른쪽으로 이동 (삭제), x = V[k-1] + 1
  그다음 A[x]==B[y] 인 동안 대각선으로 쭉 전진 (스네이크, 공짜)
  x >= N 이고 y >= M 이면 → D가 정답

라운드 하나당 대각선 O(D)개, 각 대각선의 스네이크 전진까지 합쳐 라운드당 O(N+M), 총 D라운드이므로 전체 시간복잡도는 O((N+M)·D) — 논문 제목의 O(ND)다. 두 파일이 거의 비슷하면(D가 작으면) 파일 크기 N, M이 아무리 커도 diff는 매우 빠르다. 반대로 편집 거리 계산에 흔히 쓰이는 전체 DP 표(O(N·M)) 방식은 항상 표 전체를 채워야 해서, 두 파일이 살짝만 달라도 느리다 — 이것이 diff에 Myers 방식을 쓰는 실질적인 이유다.

구현 (JavaScript)

// O((N+M)·D) 시간 — a, b는 배열(문자 배열 또는 줄 배열)
function shortestEdit(a, b) {
  const N = a.length, M = b.length, MAX = N + M || 1;
  const v = new Array(2 * MAX + 1).fill(0);
  const trace = [];
  for (let d = 0; d <= MAX; d++) {
    trace.push(v.slice());               // 역추적용 스냅샷
    for (let k = -d; k <= d; k += 2) {
      let x;
      if (k === -d || (k !== d && v[MAX+k-1] < v[MAX+k+1]))
        x = v[MAX + k + 1];        // 아래로: 삽입
      else
        x = v[MAX + k - 1] + 1;    // 오른쪽: 삭제
      let y = x - k;
      while (x < N && y < M && a[x] === b[y]) { x++; y++; } // 스네이크
      v[MAX + k] = x;
      if (x >= N && y >= M) return { trace, d };  // 도착 = 최소 편집 횟수 d
    }
  }
}

어디에 쓰일까

git diff / git log -p — 기본 diff 알고리즘이 Myers (--diff-algorithm=myers가 기본값, patience/histogram도 선택 가능)
GNU diff / diff3 / patch — 유닉스 diff 유틸리티의 핵심 알고리즘
코드 리뷰 도구 — GitHub·GitLab의 PR "Files changed" 탭에서 변경된 줄만 강조
텍스트 에디터의 변경 추적 — VS Code의 "Timeline"/"Compare with" 뷰, Google Docs 제안 모드
구조화된 diff — React의 Virtual DOM diff(가상 DOM)도 "무엇이 바뀌었는지 최소로 찾는다"는 같은 철학을 트리에 적용한 것

다른 diff 방식과 비교

방식	기준	특징
Myers (O(ND))	편집 그래프 최단 경로	git 기본값. 변경이 적을수록 빠름. 가끔 사람이 보기엔 어색한 매칭 발생 가능
Patience diff	고유하게 한 번만 등장하는 줄을 앵커로	코드 블록이 옮겨졌을 때 더 직관적인 결과 (git에서 옵션으로 제공)
Histogram diff	Patience + 빈도 기반 휴리스틱	git의 실제 기본 후보로 많이 쓰임, patience보다 빠름
편집 거리 DP	O(N·M) 전체 표	편집 거리 페이지 참고 — 거리 값은 같지만 항상 표 전체를 채워야 함

※ 데모 1은 줄 단위로, 데모 2는 문자 단위로 같은 shortestEdit 함수를 그대로 재사용한다 — Myers 알고리즘은 "비교 가능한 원소의 배열"이면 무엇이든 다룰 수 있기 때문이다.