텍스트 비교 도구

이 도구는 Git에서 사용하는 것과 동일한 Myers diff 알고리즘을 구현합니다. 이 알고리즘은 한 텍스트를 다른 텍스트로 변환하는 데 필요한 최소 삽입 및 삭제 횟수인 최단 편집 스크립트(SES)를 찾습니다. x축이 원본 텍스트, y축이 수정된 텍스트를 나타내는 편집 그래프에서 작동합니다. 대각선 이동은 일치하는 문자(변경 없음), 수평 이동은 삭제, 수직 이동은 삽입을 나타냅니다.

알고리즘은 증가하는 거리(d = 0, 1, 2, ...)의 편집 경로를 탐색하며, 각 경로를 대각선(일치하는 시퀀스)을 따라 최대한 확장하는 탐욕적 접근 방식을 사용합니다. 이 과정에서 최장 공통 부분 수열(LCS)이 부산물로 발견됩니다. 최단 편집 경로를 찾으면 이를 역추적하여 diff 출력을 생성합니다. 변경된 줄 내의 문자 수준 하이라이팅을 위해, 각 수정된 줄 쌍의 개별 문자에 대해 diff 알고리즘을 2차로 실행하여 정밀한 줄 내 변경 시각화를 구현합니다.