diff 도구는 어떻게 변경사항을 찾아내는가, LCS 알고리즘 해부
두 텍스트를 붙여넣으면 어떤 줄이 지워지고 어떤 줄이 추가됐는지 색깔로 표시해 주는 diff 도구는 마법처럼 보이지만, 사실은 대학교 알고리즘 수업에서 배우는 고전적인 동적계획법(DP) 문제 하나로 동작합니다. 바로 LCS(Longest Common Subsequence, 최장 공통 부분수열)입니다. 텍스트 diff 체커의 실제 소스 코드를 뜯어보면서, diff가 "같은 부분"과 "달라진 부분"을 어떻게 구분하는지, 그리고 왜 3000줄이라는 제한이 걸려 있는지까지 원리부터 확인합니다.
1. diff의 근본 문제: "같은 부분"을 먼저 찾아야 "다른 부분"이 보인다
직관적으로는 두 텍스트를 한 줄씩 나란히 비교하면 될 것 같지만, 중간에 한 줄만 추가되거나 삭제돼도 그 뒤 모든 줄의 위치가 밀리기 때문에 단순 줄 번호 비교로는 실패합니다. 그래서 diff 알고리즘은 반대로 접근합니다. 먼저 두 텍스트에 순서를 유지한 채 공통으로 등장하는 가장 긴 줄 시퀀스(LCS)를 찾고, 그 LCS에 포함되지 않는 줄만 "추가" 또는 "삭제"로 분류합니다. LCS에 속한 줄은 위치가 밀리더라도 순서만 같으면 "동일한 줄"로 인정됩니다.
2. 실제 코드로 확인: DP 테이블과 역추적
텍스트 diff 체커의 lcs(a, b) 함수는 두 줄 배열 a, b를 받아 (m+1)×(n+1) 크기의 2차원 배열 dp를 만듭니다. dp[i][j]는 "a의 앞 i줄과 b의 앞 j줄 사이 LCS 길이"를 의미하며, 두 줄이 같으면 대각선 값에 1을 더하고, 다르면 위쪽·왼쪽 중 큰 값을 그대로 가져오는 방식으로 표를 채웁니다. 표를 다 채운 뒤에는 오른쪽 아래 모서리에서 왼쪽 위로 역추적하면서 값이 같은 경로는 "동일", 위쪽으로만 꺾이면 "삭제", 왼쪽으로만 꺾이면 "추가"로 분류합니다. 이 방식은 반드시 줄(line) 단위로만 동작합니다 — 텍스트를 split('\n')으로 잘라 배열로 만든 뒤 그 배열 원소 단위로 비교하기 때문에, 한 줄 안에서 단어 몇 개만 바뀐 경우에도 그 줄 전체가 "삭제 후 추가"로 표시됩니다.
3. 왜 3000줄 제한이 걸려 있는가
DP 테이블 크기는 (원본 줄 수+1)×(수정본 줄 수+1)입니다. 두 텍스트가 각각 3,000줄이면 테이블 셀 수는 약 900만 개(3,001×3,001)에 달합니다. 이는 시간·공간 복잡도가 모두 O(m×n)인 고전 LCS 구현의 근본적인 한계로, 줄 수가 늘어날수록 필요한 메모리가 제곱으로 커집니다. 이 도구가 MAX_LINES = 3000으로 상한을 걸어두고 이를 넘으면 비교를 거부하는 것은 임의의 제약이 아니라, 브라우저 탭 하나의 메모리 안에서 2차원 배열을 안전하게 다루기 위한 직접적인 결과입니다.
4. git이 쓰는 Myers 알고리즘과 무엇이 다른가
git의 기본 git diff도 사실 줄 단위로 비교합니다 — "git은 문자 단위, 이 도구는 줄 단위"라는 통념은 정확하지 않습니다. 진짜 차이는 두 가지입니다. 첫째, git은 Myers 알고리즘이라는 더 정교한 방식으로 최단 편집 스크립트(Shortest Edit Script)를 찾는데, 이는 실제 변경분(D)의 크기에 비례해 동작해 변경이 적은 대용량 파일에서 훨씬 빠릅니다. 반면 이 도구의 O(m×n) DP는 파일 크기 자체에만 비례하므로 대용량 파일에서 불리합니다. 둘째, git은 --word-diff, --color-words 옵션으로 단어·문자 단위까지 내려갈 수 있지만, 이 도구는 줄 단위 비교만 지원하며 별도의 단어·문자 모드가 없습니다. 또한 둘 다 기본적으로 "이동(rename/move) 감지"는 하지 않습니다 — 어떤 줄이 삭제된 위치와 다른 위치에 그대로 다시 나타나도, "이동"이 아니라 "삭제"와 "추가"가 각각 별도로 표시됩니다.
5. 3줄짜리 예시로 보는 실제 매칭
원본과 수정본이 다음과 같다고 가정하면, LCS는 1번째·3번째 줄(사과, 바나나)이고 2번째 줄만 교체됩니다.
| 원본 | 수정본 | diff 결과 |
|---|---|---|
| 사과 | 사과 | 동일 |
| 딸기 | (없음) | 삭제(빨강) |
| (없음) | 포도 | 추가(초록) |
| 바나나 | 바나나 | 동일 |
"딸기"와 "포도"는 같은 위치에서 일어난 변경처럼 보이지만, LCS 관점에서는 서로 아무 관계도 아닌 독립적인 삭제 1건, 추가 1건입니다. 이 결과는 상단 통계 영역에 추가/삭제/동일 줄 수로도 표시됩니다. 다른 형식의 diff가 필요하다면 구조화된 데이터는 JSON diff나 CSV diff 체커처럼 형식에 맞춘 전용 도구를 쓰는 편이 더 정확합니다.
6. 문장 유사도까지 알고 싶다면
diff는 "정확히 어느 줄이 바뀌었는가"를 보여주지만, "두 문서가 전체적으로 얼마나 비슷한가"라는 질문에는 다른 지표가 필요합니다. 표절 검사나 번역 검토처럼 전체 유사도 점수가 필요하다면 텍스트 유사도 체커를 함께 활용하는 것을 권장합니다.
자주 묻는 질문
Q. LCS 알고리즘은 항상 사람이 보기에 "자연스러운" diff 결과를 만들어 주나요?
아닙니다. LCS는 수학적으로 "가장 긴 공통 부분수열"을 찾을 뿐이며, 동일한 최대 길이의 LCS가 여러 개 존재할 경우 어떤 것을 선택하느냐에 따라 결과가 달라질 수 있습니다. 대부분의 경우 직관과 일치하지만, 반복되는 줄이 많은 텍스트에서는 예상과 다른 매칭이 나올 수 있습니다.
Q. 같은 줄인데 대소문자만 다르면 "변경"으로 표시되나요?
기본값으로는 변경으로 표시됩니다. 텍스트 diff 체커의 "대소문자 무시" 옵션을 켜면 비교 직전에 두 배열을 모두 소문자로 변환해 비교하므로 대소문자 차이만 있는 줄은 동일로 처리됩니다.
Q. 3000줄이 넘는 텍스트는 아예 비교할 수 없나요?
네, 이 도구는 O(m×n) 메모리 한계 때문에 원본이나 수정본 중 하나라도 3,000줄을 넘으면 비교를 진행하지 않고 경고 메시지를 표시합니다. 더 큰 파일은 텍스트를 나눠서 구간별로 비교하거나, git 같은 전문 버전관리 도구를 사용하는 것이 안전합니다.
Q. 한 줄 안에서 단어 몇 개만 바뀐 경우도 감지할 수 있나요?
이 도구는 줄 단위로만 비교하므로, 한 줄 안의 부분 변경은 그 줄 전체가 "삭제+추가"로 표시됩니다. 어느 단어가 바뀌었는지까지 강조하려면 word-diff를 지원하는 git이나 전용 코드 비교 도구가 필요합니다.