git의 diff 알고리즘

오늘은 코치님의 멘토링이 있었다.

현재 우리 프로젝트는 LCS를 기반으로 한 diff 알고리즘을 형상 관리에 적용하고 있다.

그런데 코치님은 LCS에 기반한 diff 알고리즘은 비효율적이라고 다른 알고리즘을 사용할 것을 추천하셨다.

그래서 git에서 사용하는 diff 알고리즘에 대한 설명이 담긴 웹 페이지를 공유해주셨다.

그것을 보고 학습한 내용을 정리해보려고 한다.

 

diff와 patch

diff는 두 개의 파일 또는 문서 간의 차이점을 식별하는 알고리즘 또는 도구를 의미한다.

원본과 수정된 버전 사이의 변경 내용을 탐지하고 추가된 내용, 제거된 내용, 수정된 내용 등을 식별한다.

주로 LCS 알고리즘이나 히스토그램 알고리즘 등을 사용해 구현할 수 있다.

 

patch는 변경된 내용을 적용하는 것을 의미한다.

원본 파일에 수정 사항을 적용하여 수정된 버전을 만드는 작업을 말한다.

patch는 diff 알고리즘을 사용하여 생성된 변경 내용을 포함한 파일이나 데이터를 적용함으로써 이루어진다.

 

정리하면, diff는 두 개의 버전 간의 차이를 식별하는 알고리즘이며,

patch는 변경된 내용을 적용하여 수정된 버전을 생성하는 작업을 의미한다. 

 

 

 

git에서 사용하는 대표적인 알고리즘

 

Myers Algorithm
Myers Algorithm은 DP(Dynamic Programming)을 기반으로하며,
시간 복잡도가 선형 시간에 가까운 O(N+M)복잡도를 가지는 효율적인 알고리즘이다.
원본 문서와 수정된 문서를 비교하면서 공통 부분을 찾고 이를 기반으로 변경된 부분을 식별한다.

 

동일한 파일의 첫번째와 두 번째 버전

 

Myers Algorithm의 변경 사항 탐색 과정

 

 

Histogram Algorithm

Histogram Algorithm은 diff 결과를 생성하는 데 있어서 Myers Algorithm과 약간 다른 방식으로 작동한다.

변경된 부분을 식별하기 위해 문서에서 각 라인의 히스토그램 정보를 계산한다.

이 히스토그램 정보는 라인의 내용과 출현 빈도를 나타내며, 변경된 부분의 히스토그램 차이를 계산하여 변화를 탐지한다.

Histogram Algorithm의 변경 사항 탐색 과정

 

 

Myers Algorithm과 Histogram Algorithm 알고리즘의 차이

 

 

동작방식

• Myers Algorithm
  두 개의 문자열 간의 최장 공통 부분 수열(LCS)를 찾는 알고리즘이다.
  행렬 기반의 동적 계획법(DP)을 사용하여 LCS를 계산하고 LCS의 길이를 기반으로
  변경된 부분을 식별한다.
• Histogram Algorithm
  라인(줄) 단위로 변경을 추적하는 알고리즘이다.
  두 개의 문서를 라인 단위로 비교하여 변경된 라인을 식별하고 변경된 라인 내의 글자 단위 변경 사항을 파악한다.

 

추적 정확성

• Myers Algorithm
  LCS를 기반으로 최장 공통 부분 수열을 찾기 때문에 변경된 부분을 정확하게 식별할 수 있다.
  글자 단위의 변경사항도 식별할 수 있으며 수정, 추가, 삭제된 글자들을 정확하게 추적할 수 있다.
  
  
• Histogram Algorithm
  주로 라인 단위의 변경을 추적하는 데에 특화되어있다.
  글자 단위의 변경 사항까지 정확하게 식별하려면 추가 과정이 필요하다.
  따라서 글자 단위 변경 사항을 정확하게 식별하는 LCS 알고리즘에 비해 상대적으로 정확도가 떨어질 수 있다.

 

 

결론적으로 마이어스와 히스토그램의 차이는 변경 추적의 단위가 글자인지 라인인지에 있다.

변경 사항을 글자 단위로 추적하면 정확도는 높아지지만 그만큼 시간복잡도가 증가한다.

반면에 라인 단위로 추적하면 효율성이 증가한다. 그리고 정확도 또한 우려할 정도로 낮아지지는 않는다고 한다.

코치님이 왜 LCS를 안쓰는 알고리즘을 적용해보라고 했는지 이유는 알 것 같다.

일단 히스토그램 알고리즘을 구현해서 비교해보고 최종 결정을 내리는 것이 좋겠다.

 

 

참조 및 출처

https://link.springer.com/article/10.1007/s10664-019-09772-z#Sec3

https://velog.io/@jshme/diff-algorithm-deep-dive-1

Git Diff / Android DiffUtil Deep Dive - 1

https://grasshopper42.vercel.app/post/e56936bb-ddfa-4391-8135-210b36ae320d

https://grasshopper42.vercel.app/post/3fbdbeae-51b5-4b0f-b280-581f7d1240b4