diff 는 어떻게 바뀐 줄을 찾아낼까?

Git PR 의 빨강·초록 줄, IDE 의 conflict marker, diff 명령의 +/- 가 모두 같은 질문에 답한다 —"이 두 텍스트는 무엇이 다른가, 가장 적은 편집 단계로 설명하면?" 답을 구하는 게 의외로 어렵다. 이 가이드는 diff 알고리즘의 핵심 (LCS / Myers), 왜 줄 이동이 -와 + 두 줄로 나뉘는지, unified vs context 패치 형식, 그리고 word-level intra-line diff 의 동작을 정리한다.

핵심 문제 — Longest Common Subsequence (LCS)

두 시퀀스 A 와 B 가 있을 때, 두 시퀀스에 공통으로 등장하는 가장 긴 부분 시퀀스 를 찾는 문제. "부분 시퀀스" 는 순서를 유지하되 연속일 필요 없음.

A = A B C B D A B
B = B D C A B A

LCS = B C B A    (또는 B D A B)
길이 = 4

LCS 가 찾히면 diff 는 자동 결정:

LCS 에 포함된 글자 → 변경 없음 (context)
A 에만 있는 글자 → 삭제 (-)
B 에만 있는 글자 → 추가 (+)

diff 의 목표 = "최소 편집 거리" = "최대 LCS". 두 표현은 동치.

Naive LCS — O(N × M) 동적 계획법

교과서적 DP. N × M 표 채움:

dp[i][j] = LCS 길이 (A[0..i], B[0..j])

if A[i] == B[j]:
  dp[i][j] = dp[i-1][j-1] + 1
else:
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

시간·공간 모두 O(N × M). 두 파일 각 10,000 줄이면 1 억 개 셀 — 실용 X. Linux kernel 같은 대규모 파일에는 부적합.

Myers algorithm — diff 의 실질 표준 (1986)

Eugene Myers 가 1986 년 발표. 시간 O(ND) — N = 두 입력 길이 합, D = 편집 거리. 변경이 적을수록 빠름 — 대부분의 실제 diff 는 D ≪ N (한 commit 의 변경 라인은 보통 수십 줄).

핵심 아이디어 — edit graph 의 최단 경로:

            B 의 글자 →
          ┌──────────────
        A │
        의 │  (i, j) 점에서:
        글 │    오른쪽 = B[j] 추가 (+)
        자 │    아래   = A[i] 삭제 (-)
        ↓ │    대각선 = 글자 일치 (공짜)

(0, 0) → (N, M) 까지의 최단 경로 = 최소 편집. 대각선이 "공짜" (cost 0) 라서 최대한 대각선을 타려는 BFS. D-step 마다 도달 가능한 furthest 거리만 추적해서 메모리 O(D²) 또는 더 효율적 O(N + D²).

Git / Mercurial / GNU diffutils / VS Code 모두 Myers (또는 Myers + 후처리 heuristic) 사용. 텍스트 비교 도 같은 알고리즘 라이브러리.

왜 라인 이동이 - + 두 줄로 보이나

Myers 의 기본 출력은 이동 인식 X. "라인 5 가 라인 50 으로 옮겨감" 을 표현하는 단일 op 가 없다. 대신:

-라인 5 (삭제)
...
+라인 5 (라인 50 위치에 추가)

이동 인식은 후처리 — Git 의 --color-moved 옵션이 diff 후 같은 내용 - / + 페어를 찾아 별색 표시.

Unified vs context — 패치 형식 두 가지

Unified diff (현대 표준)

--- a/file.txt
+++ b/file.txt
@@ -3,5 +3,6 @@
 unchanged line 3
-removed line 4
+added line 4
+added line 5
 unchanged line 6
 unchanged line 7
 unchanged line 8

--- / +++ — 파일 경로
@@ -3,5 +3,6 @@ — hunk 헤더. "원본 line 3 부터 5 줄, 새 line 3 부터 6 줄"
- / + 줄 + context 줄 (기본 3 줄)

Git diff·GitHub PR·email 패치 모두 unified.

Context diff (1985, 옛 형식)

*** file.txt.orig
--- file.txt.new
***************
*** 3,7 ****
  unchanged line 3
! removed line 4
  unchanged line 6
  unchanged line 7
  unchanged line 8
--- 3,8 ----
  unchanged line 3
! added line 4
! added line 5
  unchanged line 6
  unchanged line 7
  unchanged line 8

구역마다 원본·새 두 블록 분리 노출. 사람 가독성 ↑ 하지만 길어짐. 현재는 거의 사용 X.

Diff 적용 (patch)

패치 파일은 적용 가능한 텍스트 변환 명령. patch 또는git apply 가 hunk 헤더의 라인 번호와 context 줄을 비교해 위치 정합 후 적용. context 가 부분 일치면 fuzz match ( 앞뒤 N 줄 시도) — 실패하면 .rej 파일 생성.

Diff 패치 가 두 텍스트에서 unified patch 생성 — 적용은 시스템의 patch 명령 또는 git apply.

Granularity — line / word / char 단위

diff 의 기본 단위는 "라인". 그러나 한 줄 안에서 일부 단어만 바뀐 경우 line diff 는 전체 줄을 - / + 두 줄 로 표시. 가독성 ↓.

해결 — 줄이 바뀐 곳을 다시 단어 또는 글자 단위로 diff:

Line diff:
- The quick brown fox jumps
+ The quick red fox runs

Intra-line word diff:
The quick [brown→red] fox [jumps→runs]

GitHub PR 의 빨강·초록 강조가 이 방식. 텍스트 비교 도 word / char 모드 + intra-line highlight 지원.

JSON diff — 구조 인식

텍스트 diff 는 JSON 의 의미 무지. {"a":1,"b":2} 와 {"b":2,"a":1} 가 다른 라인. 의미상 동일.

JSON diff 는 트리 구조 비교:

객체 키는 순서 무관
변경된 경로 (예: users[2].email) 명시
type 변경 (number → string) 도 인식

JSON 비교 가 정확히 이 동작. API 응답 비교·schema diff 에 적합.

최적화 후 처리 — heuristic

Myers 의 raw 결과가 항상 사람 가독성 ↑ 는 아님. Git 은 후처리 heuristic 으로 더 자연스러운 diff 를 만든다:

indent heuristic — 같은 들여쓰기 라인을 묶어서 다음 함수 시작이 자연스럽게 보이게
compaction — 빈 줄·중복 패턴을 위/아래 어디로 이동할지 결정해 의미 단위 단절
patience diff — Bram Cohen 의 알고리즘. 유일한 일치 라인을 anchor 로 잡고 그 사이만 LCS. 함수 정의가 같이 있는 코드에 효과 ↑

Git 의 diff.algorithm 옵션으로 myers (기본) / patience / histogram / minimal 선택 가능.

흔한 함정

1. CRLF vs LF 줄바꿈

Windows 의 \r\n vs Unix 의 \n — 한 쪽에서 받은 파일이 모든 줄 변경으로 표시. git config core.autocrlf 또는 .gitattributes 로 정합.

2. trailing whitespace

탭/스페이스 혼용·끝 공백 차이로 false-diff. diff -w / git diff -w 로 whitespace 무시. 텍스트 비교 도 ignoreWhitespace 옵션.

3. 매우 큰 파일

Myers 가 O(ND) 라도 두 파일이 완전히 다르면 D ≈ N → O(N²) 폭주. Git 은 임계값 (수만 줄) 초과 시 hash 기반 빠른 diff 또는 binary 취급으로 fallback.

4. minify 코드 diff

한 줄이 수천 글자인 minified JS. line diff 는 "한 줄 통째로 변경" 만 표시. 의미 X. minify 전 source 로 diff 또는 char-level.

5. 바이너리 파일

diff 알고리즘은 텍스트 가정. PDF / image / DB dump 는 byte diff 가 의미 없음. Git 은 자동 감지 (NULL byte 또는 magic numbers) 후 "Binary files differ" 만 표시.

참고 자료

Myers, E. (1986). "An O(ND) Difference Algorithm" — 원조 논문 PDF
GNU diffutils unified format — 매뉴얼
Patience diff — Bram Cohen 의 블로그
Git diff algorithm options — git-scm.com

요약

diff 의 핵심 = LCS (longest common subsequence). 최대 LCS = 최소 편집.
Naive DP 는 O(N × M) — 대규모 X. Myers O(ND) 가 1986 년 이후 표준.
기본 단위는 라인. 라인 이동은 - + 두 op 로 분해. 후처리 heuristic 으로 이동 감지·시각화.
Unified diff = 현대 표준. Context 는 옛 형식.
intra-line word/char diff 가 가독성 ↑ — GitHub PR / IDE 표준.
JSON 처럼 구조화 데이터는 텍스트 diff X — 트리 비교.
실험 — 텍스트 비교 / JSON 비교 / Diff 패치.