LCS 기반 Myers Algorithm을 통한 Git Diff의 최소 편집 거리 최적화

Context

단순 Line-by-line 비교 방식은 코드 삽입 시 대량의 불필요한 변경 사항을 생성하는 한계 존재. 파일의 구조적 변화를 정확히 감지하기 위해 단순 위치 비교가 아닌 두 시퀀스 간의 공통 분모를 찾는 접근 방식 필요.

Technical Solution

• Longest Common Subsequence(LCS) 모델을 통한 두 파일 간 최대 공통 부분 시퀀스 식별
• DP 기반 LCS 알고리즘의 $O(m \times n)$ 시간 및 공간 복잡도 문제를 해결하기 위한 Myers Diff 채택
• Shortest Edit Script 개념을 도입하여 Old 파일에서 New 파일로 변환하는 최소 삽입 및 삭제 경로 탐색
• LCS가 길수록 변경 사항이 적다는 상관관계를 활용하여 Diff 결과의 가독성 극대화
• 텍스트를 단순 문자열이 아닌 Line sequence로 처리하여 엔지니어링 관점의 변경 단위 정의
• Myers, Patience, Histogram 등 다양한 알고리즘 옵션을 제공하여 파일 특성별 최적의 Diff 결과 도출