두 개의 파일 비교

"Diff"는 변경의 공용어입니다. 그것들은 소스 코드, 산문, 데이터 세트와 같은 것의 두 버전 사이에 무엇이 이동했는지 알려주는 간결한 이야기이며, 모든 것을 다시 읽도록 강요하지 않습니다. 그 몇 가지 기호(+, -, @@) 뒤에는 최적성, 속도 및 인간의 이해를 균형있게 맞추는 알고리즘, 휴리스틱 및 형식의 깊은 스택이 있습니다. 이 기사는 diff에 대한 실용적인 알고리즘-워크플로 둘러보기입니다: 어떻게 계산되는지, 어떻게 형식화되는지, 병합 도구가 어떻게 사용하는지, 더 나은 검토를 위해 어떻게 조정하는지. 그 과정에서 우리는 1차 자료와 공식 문서에 주장을 근거를 둘 것입니다. 왜냐하면 공백이 계산되는지 여부와 같은 사소한 세부 사항이 정말로 중요하기 때문입니다.

"diff"란 실제로 무엇인가

공식적으로 diff는 삽입과 삭제를 사용하여 "오래된" 시퀀스를 "새로운" 시퀀스로 변환하는 최단 편집 스크립트(SES)를 설명합니다(때로는 삭제+삽입으로 모델링할 수 있는 대체도 포함). 실제로 대부분의 프로그래머 대상 diff는 줄 지향이며 가독성을 위해 선택적으로 단어나 문자로 구체화됩니다. 표준 출력은 컨텍스트 와 통합 형식입니다. 후자—코드 검토에서 일반적으로 보는 것—는 간결한 헤더와 "덩어리"로 출력을 압축하며, 각 덩어리는 변경 사항 주변의 컨텍스트 이웃을 보여줍니다. 통합 형식은 -u/--unified를 통해 선택되며 패치 적용을 위한 사실상의 표준입니다. patch는 일반적으로 컨텍스트 줄의 이점을 활용합니다 변경 사항을 강력하게 적용하기 위해.

GNU diff 설명서는 노이즈를 줄이고 신호를 더 많이 원할 때 사용하는 스위치를 목록으로 제공합니다—공백 무시, 정렬을 위한 탭 확장, 또는 더 느리더라도 "최소" 편집 스크립트 요청 (옵션 참조). 이러한 옵션은 두 파일이 다르다는 것의 의미를 바꾸지 않습니다. 알고리즘이 더 작은 스크립트를 얼마나 공격적으로 검색하는지와 결과가 인간에게 어떻게 제시되는지를 바꿉니다.

LCS에서 마이어스까지: diff 계산 방법

대부분의 텍스트 diff는 최장 공통 부분 수열(LCS) 추상화에 기반합니다. 고전적인 동적 프로그래밍은 LCS를 O(mn) 시간과 공간에서 해결하지만, 큰 파일에는 너무 느리고 메모리를 많이 사용합니다. 히르쉬버그의 알고리즘 은 분할 정복을 사용하여 선형 공간(여전히 O(mn) 시간)에서 최적의 정렬을 계산하는 방법을 보여주었으며, 이는 실용적인 diff 구현에 영향을 미친 기본적인 공간 절약 기술입니다.

속도와 품질을 위한 돌파구는 유진 W. 마이어스의 1986년 알고리즘이었습니다. 이 알고리즘은 O(ND) 시간(N ≈ 총 줄 수, D ≈ 편집 거리)과 거의 선형 공간에서 SES를 찾습니다. 마이어스는 "편집 그래프"에서 편집을 모델링하고 가장 멀리 도달하는 경계를 따라 진행하여 줄-diff 설정에서 빠르고 최소에 가까운 결과를 산출합니다. 이것이 많은 도구에서 "마이어스"가 기본값으로 남아 있는 이유입니다.

또한 헌트-시만스키 계열도 있습니다. 이는 몇 개의 위치만 일치할 때 LCS를 가속화하며(일치 항목을 미리 인덱싱하고 증가하는 부분 수열을 추적함으로써), 역사적으로 초기 diff 변형과 관련이 있습니다. 이러한 알고리즘은 트레이드오프를 조명합니다: 드문 일치 항목이 있는 입력에서는 하위 2차적으로 실행될 수 있습니다. 이론과 구현을 연결하는 실무자 개요는 닐 프레이저의 노트를 참조하십시오.

"최적"이 읽기 어려울 때: 인내와 히스토그램 전략

마이어스는 최소 편집 스크립트를 목표로 하지만, "최소" ≠ "가장 읽기 쉬움"입니다. 재정렬되거나 복제된 큰 블록은 순수한 SES 알고리즘을 어색한 정렬로 속일 수 있습니다. 브램 코헨에게 귀속되는 인내 diff를 입력하십시오: 정렬을 안정화하기 위해 독특하고 빈도가 낮은 줄에 고정하며, 종종 인간이 더 깨끗하다고 느끼는 diff를 생성합니다—특히 함수가 이동하거나 블록이 재구성된 코드에서. 많은 도구는 "인내" 옵션(예:diff.algorithm)을 통해 이를 노출합니다.

히스토그램 diff 는 빈도 히스토그램으로 인내를 확장하여 발생 빈도가 낮은 요소를 더 잘 처리하면서도 빠르게 유지합니다( JGit에서 대중화됨). --histogram이 시끄러운 파일에 대해 더 명확한 덩어리를 생성하는 것을 발견했다면, 그것은 의도된 것입니다. 최신 Git에서는 알고리즘을 전역적으로 또는 호출별로 선택할 수 있습니다:git config diff.algorithm myers|patience|histogram 또는 git diff --patience.

단어 수준의 명확성, 공백 제어 및 이동된 코드 강조

줄 diff는 간결하지만 사소한 편집을 가릴 수 있습니다. 단어 수준 diff (--word-diff)는 전체 줄 삽입/삭제로 검토를 넘치게 하지 않고 줄 내 변경 사항을 색칠합니다—산문, 긴 문자열 또는 한 줄짜리에 적합합니다.

재포맷 후 공백이 diff를 압도할 수 있습니다. Git과 GNU diff 모두 공백 변경을 무시하도록 다양한 정도로 허용하며, GNU diff의 공백 옵션 (-b, -w, -B)은 포맷터가 실행될 때 도움이 됩니다. 정렬 노이즈 대신 논리적 편집을 보게 될 것입니다.

코드가 통째로 이동할 때 Git은 --color-moved로 이동된 블록을 강조 할 수 있으며, "이동됨"과 "수정됨"을 시각적으로 구분하여 검토자가 이동이 의도하지 않은 편집을 숨기지 않았는지 감사하는 데 도움이 됩니다. diff.colorMoved를 통해 영구적으로 만드십시오.

병합 서비스의 Diff: 양방향 대 삼방향 및 diff3

양방향 diff는 정확히 두 버전을 비교합니다. 양쪽이 동일한 기본 줄을 편집했는지 알 수 없으므로 종종 과도하게 충돌합니다. 삼방향 병합(최신 VCS에서 사용)은 공통 조상에서 각 측으로의 diff를 계산한 다음 두 변경 세트를 조정합니다. 이는 극적으로 가짜 충돌을 줄이고 더 나은 컨텍스트를 제공합니다. 여기의 고전적인 알고리즘 핵심은 diff3이며, "O"(기본)에서 "A" 및 "B"로의 변경 사항을 병합하고 필요한 경우 충돌을 표시합니다.

학술 및 산업계의 연구는 병합 정확성을 공식화하고 개선하기 위해 계속됩니다. 예를 들어, 검증된 삼방향 병합은 충돌 없는 의미론적 개념을 제안합니다. 일상적인 Git에서 최신 ort 병합 전략 은 diff 및 이름 바꾸기 감지를 기반으로 하여 놀라움이 적은 병합을 생성합니다. 사용자를 위한 주요 팁은 다음과 같습니다: merge.conflictStyle=diff3로 충돌에서 기본 줄을 표시하고, diff를 작게 유지하기 위해 자주 통합하십시오.

이름 바꾸기 감지 및 임계값

전통적인 diff는 콘텐츠 주소 지정이 파일을 블롭으로 취급하기 때문에 이름 바꾸기를 "볼" 수 없습니다. 삭제와 추가만 볼 수 있습니다. 이름 바꾸기 감지 휴리스틱 은 추가/제거된 쌍 간의 유사성을 비교하여 그 격차를 메웁니다. Git에서는 -M/--find-renames[=<n>](기본값은 약 50% 유사성)를 통해 활성화하거나 조정합니다. 더 시끄러운 이동에는 값을 낮추십시오. 후보 비교를 제한 할 수 있습니다 diff.renameLimit(및 병합 중 merge.renameLimit )으로. 이름 바꾸기를 통해 기록을 추적하려면 git log --follow -- <path>를 사용하십시오. 최신 Git은 병합 중에 폴더 이동을 전파하기 위해 디렉토리 이름 바꾸기 감지 도 수행합니다.

바이너리 및 델타 diff: rsync, VCDIFF/xdelta, bsdiff

텍스트만 변경되는 것은 아닙니다. 바이너리의 경우 일반적으로 델타 인코딩이 필요합니다—소스에서 대상을 재구성하기 위해 복사/추가 지침을 내보냅니다. rsync 알고리즘 은 네트워크를 통해 블록을 정렬하기 위해 롤링 체크섬을 사용하여 효율적인 원격 차이 계산을 개척하여 대역폭을 최소화했습니다.

IETF는 ADD, COPY 및 RUN의 바이트코드를 설명하는 일반 델타 형식인 VCDIFF(RFC 3284)를 표준화했습니다. xdelta3 와 같은 구현은 바이너리 패치에 사용합니다. 실행 파일의 압축 패치에는 bsdiff 가 접미사 배열과 압축을 통해 매우 작은 델타를 생성하는 경우가 많습니다. 패치 크기가 중요하고 생성이 오프라인으로 이루어질 수 있을 때 선택하십시오.

소스 코드를 넘어서는 텍스트 diff: 퍼지 매칭 및 패치 적용

동시 편집이나 약간 잘못 정렬된 컨텍스트에 직면했을 때 강력한 패치 적용이 필요한 경우—편집기나 협업 시스템을 생각해보십시오— diff-match-patch를 고려하십시오. 이는 마이어스 스타일의 차이 계산과 Bitap 퍼지 매칭을 결합하여 거의 일치하는 항목을 찾고 "최선의 노력"으로 패치를 적용하며, diff 전 속도 향상과 diff 후 정리 기능으로 최소성을 약간 희생하여 더 나은 인간 출력을 제공합니다. 연속 동기화 루프에서 diff와 퍼지 패치를 결합하는 방법에 대해서는 프레이저의 차등 동기화를 참조하십시오.

구조화된 데이터 diff: 테이블 및 트리

CSV/TSV의 줄 diff는 한 셀의 변경이 전체 줄 편집처럼 보일 수 있기 때문에 취약합니다. 테이블 인식 diff 도구(daff) 는 데이터를 행/열로 처리하여 특정 셀을 대상으로 하는 패치를 내보내고 추가, 삭제 및 수정을 명확하게 하는 시각화를 렌더링합니다( R 비네트참조). 빠른 확인을 위해 특수 CSV 차이 도구는 셀별 변경 및 유형 이동을 강조 표시할 수 있습니다. 알고리즘적으로 이국적이지는 않지만 실제로 관심 있는 구조를 비교하여 검토 신호를 높입니다.

실용적인 Git diff 조정: 검토자 체크리스트

• 올바른 알고리즘 선택: 마이어스(기본값)로 시작하고, 재정렬이나 시끄러운 블록이 출력을 혼란스럽게 하는 경우 --patience 를 시도하거나, 반복적인 텍스트에서 빠르고 읽기 쉬운 diff를 원하면 --histogram 을 시도하십시오. git config diff.algorithm …로 기본값을 설정하십시오.
• 노이즈 줄이기: 스타일 전용 편집의 경우 공백 플래그(-b, -w, --ignore-blank-lines)를 사용하여 실질적인 변경 사항에 집중하십시오. Git 외부에서는 GNU diff의 공백 제어를 참조하십시오.
• 줄 안 보기: --word-diff 는 긴 줄과 산문에 도움이 됩니다.
• 이동된 코드 감사: --color-moved (또는 diff.colorMoved)는 "이동됨"과 "수정됨"을 구분합니다.
• 이름 바꾸기 처리: 리팩토링을 검토할 때 -M 을 추가하거나 유사성 임계값(-M90%, -M30%)을 조정하여 이름 바꾸기를 포착하십시오. 기본값은 약 50%임을 기억하십시오. 깊은 트리의 경우 diff.renameLimit을 설정하십시오.
• 이름 바꾸기를 통해 기록 추적: git log --follow -- <path>.

병합이 실제로 diff를 어떻게 소비하는지(그리고 그렇지 않을 때 해야 할 일)

병합은 두 개의 diff(BASE→OURS, BASE→THEIRS)를 계산하고 둘 다 BASE에 적용하려고 시도합니다. ort 와 같은 전략은 이름 바꾸기 감지(디렉토리 규모 이동 포함)와 휴리스틱을 통합하여 충돌을 최소화하기 위해 이를 대규모로 조정합니다. 충돌이 발생하면 --conflict=diff3 는 의도를 이해하는 데 매우 중요한 기본 컨텍스트로 마커를 풍부하게 합니다. Pro Git의 고급 병합 에 대한 장에서는 해결 패턴을 안내하고, Git 문서에는 -X ours 및 -X theirs와 같은 노브가 나열되어 있습니다. 반복되는 충돌에 대한 시간을 절약하려면 rerere 를 활성화하여 해결책을 기록하고 재생하십시오.

파일을 넘어서: 원격 및 증분 시나리오

네트워크를 통해 큰 자산을 동기화하는 경우 로컬 diff보다 rsync 세계에 더 가깝습니다. Rsync는 원격으로 일치하는 블록을 발견하기 위해 롤링 체크섬을 계산한 다음 필요한 것만 전송합니다. 패키지된 델타의 경우 VCDIFF/xdelta 는 표준 바이트코드와 성숙한 도구를 제공합니다. 인코더와 디코더를 모두 제어할 때 선택하십시오. 그리고 패치 크기가 가장 중요한 경우(예: 무선 펌웨어) bsdiff 는 매우 작은 패치를 위해 빌드 시 CPU/메모리를 교환합니다.

"퍼지"와 "친근한"에 대한 간단한 말

diff-match-patch 와 같은 라이브러리는 실제 세계에서 패치하는 파일이 표류했을 수 있음을 인정합니다. 견고한 diff(종종 마이어스)와 퍼지 매칭 (Bitap) 및 구성 가능한 정리 규칙을 결합하여 패치를 적용할 올바른 위치를 찾고 diff를 더 읽기 쉽게 만들 수 있습니다—협업 편집 및 동기화에 중요합니다.

내면화해야 할 "테이블 스테이크"

1. 형식을 알아두십시오. 통합 diff(-u/-U<n>)는 간결하고 패치 친화적입니다. 코드 검토와 CI가 기대하는 것입니다 (참조).
2. 알고리즘을 알아두십시오. 빠른 최소 편집을 위한 마이어스 (논문); 재정렬이나 시끄러운 블록의 가독성을 위한 인내/히스토그램 (인내, 히스토그램); 선형 공간 트릭을 위한 히르쉬버그 (논문); 드문 일치 가속을 위한 헌트-시만스키 (논문).
3. 스위치를 알아두십시오. 공백 제어, 단어-diff 및 색상-이동은 검토 승수입니다 (git diff 문서; GNU 공백 옵션).
4. 병합을 알아두십시오. diff3 스타일의 삼방향은 덜 혼란스럽습니다. ort 와 이름 바꾸기 감지는 이탈을 줄입니다. rerere 는 시간을 절약합니다.
5. 데이터에 적합한 도구를 선택하십시오. CSV/테이블의 경우 daff를 사용하십시오. 바이너리의 경우 VCDIFF/xdelta 또는 bsdiff를 사용하십시오.

부록: 작은 명령어 요리책

근육 기억이 중요하기 때문에:

# 추가 컨텍스트가 있는 표준 통합 diff 표시
  git diff -U5
  diff -u -U5 a b
  
  # 긴 줄이나 산문에 대한 단어 수준의 명확성 얻기
  git diff --word-diff
  
  # 재포맷 후 공백 노이즈 무시
  git diff -b -w --ignore-blank-lines
  diff -b -w -B a b
  
  # 검토 중 이동된 코드 강조
  git diff --color-moved
  git config --global diff.colorMoved default
  
  # 이름 바꾸기 감지로 리팩토링을 길들이고 이름 바꾸기를 통해 기록 추적
  git diff -M
  git log --follow -- <file>
  
  # 가독성을 위해 알고리즘 선호
  git diff --patience
  git diff --histogram
  git config --global diff.algorithm patience
  
  # 충돌 마커에서 기본 줄 보기
  git config --global merge.conflictStyle diff3

마지막 생각

훌륭한 diff는 최소성을 증명하는 것보다 최소한의 인지 비용으로 검토자 이해를 극대화하는 것에 관한 것입니다. 이것이 생태계가 여러 알고리즘(마이어스, 인내, 히스토그램), 여러 프레젠테이션(통합, 단어-diff, 색상-이동) 및 도메인 인식 도구(테이블용 daff, 바이너리용 xdelta/bsdiff)를 발전시킨 이유입니다. 트레이드오프를 배우고, 노브를 조정하면, 빨간색과 녹색 줄에서 컨텍스트를 재구성하는 데 시간을 덜 들이고 의도에 대해 추론하는 데 더 많은 시간을 할애하게 될 것입니다.