두 글을 비교하는 프로그램은 "무엇이 바뀌었나"를 사람처럼 읽고 판단하지 않습니다. 대신 두 목록 사이에서 가장 적은 수의 삭제와 추가로 한쪽을 다른 쪽으로 바꾸는 방법을 찾습니다. 이 글은 diff 가 그 답을 어떻게 계산하는지, 그리고 결과가 가끔 사람의 기대와 다르게 나오는 이유를 설명합니다.
비교의 단위: 줄, 단어, 글자
diff 는 먼저 텍스트를 토큰의 목록으로 나눕니다. 전통적인 diff 와 git 은 한 줄을 하나의 토큰으로 봅니다. 그래서 한 줄 안에서 글자 하나만 바뀌어도 그 줄 전체가 "삭제 1줄 + 추가 1줄"로 나옵니다.
줄 단위 비교는 빠르고 코드 리뷰에 잘 맞지만, 긴 문단이 한 줄로 이어진 문서에서는 어디가 바뀌었는지 찾기 어렵습니다. 그래서 많은 도구가 두 단계로 비교합니다.
- 줄 단위로 비교해 바뀐 줄을 찾는다.
- 바뀐 줄끼리 짝을 지어, 그 안을 다시 단어나 글자 단위로 비교한다.
이 사이트도 같은 방식을 씁니다. 줄 안 비교 단위는 단어, 어절(띄어쓰기 기준), 글자 중에서 고를 수 있습니다.
최장 공통 부분 수열(LCS)
diff 의 수학적 핵심은 최장 공통 부분 수열(Longest Common Subsequence, LCS)입니다. 부분 수열은 순서를 지키면서 일부 원소를 골라낸 것입니다. 예를 들어 ABCABBA 와 CBABAC 의 공통 부분 수열 가운데 가장 긴 것은 길이 4 이며, CABA 나 BABA 가 그 예입니다.
LCS 에 들어간 원소는 "그대로 남은 것"이고, 나머지는 "삭제된 것"(왼쪽에만 있음)이나 "추가된 것"(오른쪽에만 있음)입니다. LCS 가 길수록 삭제와 추가가 적어집니다. 두 목록의 길이를 N, M 이라 하고 LCS 의 길이를 L 이라 하면, 필요한 삭제와 추가의 합 D 는 다음과 같습니다.
D = (N - L) + (M - L)위 예에서는 N=7, M=6, L=4 이므로 D = 3 + 2 = 5 입니다. 이 D 를 편집 거리(삽입·삭제만 허용한 경우)라고 부르고, 삭제·추가 목록을 편집 스크립트라고 합니다.
편집 그래프와 Myers 알고리즘
LCS 를 교과서 방식(동적 계획법)으로 구하면 N×M 크기의 표가 필요합니다. 1만 줄끼리 비교하면 1억 칸이라 느리고 메모리도 많이 듭니다. 1986년 Eugene W. Myers 는 논문 "An O(ND) Difference Algorithm and Its Variations"에서 더 빠른 방법을 제시했고, 이것이 오늘날 GNU diff 와 git 의 기본 알고리즘의 바탕이 됐습니다.
Myers 는 비교를 격자 위의 최단 경로 찾기로 바꿉니다.
- 왼쪽 위 (0,0)에서 오른쪽 아래 (N,M)까지 갑니다.
- 오른쪽으로 한 칸 = 왼쪽 텍스트의 원소 하나 삭제, 아래로 한 칸 = 오른쪽 텍스트의 원소 하나 추가. 비용은 1입니다.
- 두 원소가 같은 칸에서는 대각선으로 공짜로 이동할 수 있습니다. 이렇게 이어지는 대각선 구간을 snake라고 부릅니다.
비용이 가장 적은 경로가 곧 가장 짧은 편집 스크립트입니다. Myers 알고리즘은 "비용 0으로 갈 수 있는 가장 먼 곳", "비용 1로 갈 수 있는 가장 먼 곳"… 을 차례로 넓혀 가다가 끝점에 닿으면 멈춥니다. 각 단계에서 대각선마다 가장 멀리 간 위치 하나만 기억하면 되므로, 걸리는 시간은 대략 (N+M)×D 에 비례합니다. 두 텍스트가 거의 같으면 D 가 작아서 매우 빠르고, 완전히 다르면 느려집니다.
선형 메모리와 middle snake
경로를 되짚으려면 단계마다 기록을 남겨야 해서 메모리가 D² 에 비례해 늘어날 수 있습니다. Myers 는 같은 논문에서 앞에서 찾아 나가는 탐색과 뒤에서 거꾸로 찾아오는 탐색을 동시에 진행해, 둘이 만나는 대각선 구간(middle snake)을 찾는 변형도 제시했습니다. 그 지점을 기준으로 문제를 두 개의 작은 문제로 나누어 되풀이하면, 메모리는 입력 크기에 비례하는 만큼만 씁니다.
너무 비쌀 때: 근사 휴리스틱
두 입력이 수만 줄이고 서로 많이 다르면 D 도 커져서 (N+M)×D 가 수십억에 이를 수 있습니다. GNU diff 는 이런 경우를 대비해, 탐색 단계가 일정 한도를 넘으면 지금까지 가장 멀리 나아간 대각선에서 문제를 잘라 버리는 휴리스틱을 둡니다. 결과는 여전히 올바른 편집 스크립트지만 가장 짧다는 보장은 없습니다. GNU diff 의 --minimal 이나 git 의 --minimal 옵션은 시간이 더 걸리더라도 최소 결과를 찾게 합니다.
최소가 늘 읽기 좋은 것은 아니다
편집 거리가 같은 경로가 여러 개일 수 있습니다. 예를 들어 코드에 함수를 하나 추가하면 닫는 중괄호 } 나 빈 줄이 여러 곳에 있으므로, 알고리즘이 "새 함수의 }"를 "기존 함수의 }"와 짝지어 버릴 수 있습니다. 결과는 최소지만 사람이 보기에는 어색합니다. git 이 들여쓰기를 보고 경계를 옮기는 휴리스틱을 기본으로 쓰고, patience·histogram 같은 다른 알고리즘을 제공하는 이유입니다. 자세한 비교는 diff 알고리즘 비교에서 다룹니다.
이 도구에서는
이 사이트의 비교 엔진은 Myers 알고리즘의 선형 메모리 변형을 자바스크립트로 구현했고, 입력이 크면 GNU diff 와 같은 방식의 근사 분할로 넘어갑니다. 계산은 Web Worker 에서 돌기 때문에 큰 파일을 넣어도 화면이 멈추지 않습니다. 줄 단위 결과가 나오면 바뀐 줄끼리 내용이 비슷한 것을 짝지어 "수정"으로 표시하고, 그 안을 선택한 단위(단어·어절·글자)로 한 번 더 비교해 강조합니다.
직접 두 텍스트를 넣고 줄 안 비교 단위를 바꿔 가며 결과가 어떻게 달라지는지 텍스트 비교기에서 확인해 보세요. 결과를 git 형식으로 읽는 법은 unified diff 읽는 법을 참고하면 됩니다.