7
DiffMerge과 같은 응용 프로그램은 텍스트 파일의 차이점을 어떻게 감지합니까? 또한 검사 대상 파일과 다른 줄이 아닌 새로운 줄을 결정하는 방법은 무엇입니까?텍스트 차이 인식 응용 프로그램은 어떻게 작동합니까?
구현하기가 상당히 쉬운가요? 이 작업을 수행 할 이미 라이브러리가 있습니까?
A
답변
5
다음은 UNIX 명령 줄 도구 diff의 기초가되는 the paper입니다.
4
실제로는 매우 간단합니다. 대부분 DIFF 프로그램은 그래프 알고리즘을 사용하여 해결할 수있는 Longest Common Sequence을 기반으로합니다.
This web page은 C#의 예제 구현을 제공합니다.
4
그건 복잡한 질문입니다. diff를 수행한다는 것은 두 파일 간의 최소 편집 거리를 찾는 것을 의미합니다. 즉, 한 파일을 다른 파일로 변환 할 때 변경해야하는 최소 변경 횟수입니다. 이것은 두 파일 사이에서 가장 긴 공통 서브 시퀀스를 찾는 것과 같습니다. 이것은 다양한 diff 프로그램의 기초입니다. 가장 긴 공통 서브 시퀀스 문제는 잘 알려져 있으며 Google에서 동적 프로그래밍 솔루션을 찾을 수 있어야합니다.
동적 프로그래밍 방식의 문제는 O (n^2)입니다. 따라서 대용량 파일에서는 매우 느리고 큰 바이너리 문자열에서는 사용할 수 없습니다. diff 프로그램을 작성하는 것이 어려운 부분은 문제 도메인에 대한 알고리즘을 최적화하므로 합리적인 성능 (그리고 합리적인 결과)을 얻을 수 있습니다. Hunt와 McIlroy의 "차동 파일 비교를위한 알고리즘"이라는 논문은 Unix diff 유틸리티의 초기 버전에 대한 좋은 설명을 제공합니다.
4
라이브러리가 있습니다. 여기에 하나 : http://code.google.com/p/google-diff-match-patch/
StackOverflow는 비 교적 비교를 위해 Beyond Compare를 사용합니다. 필자는 Beyond Compare를 명령 줄에서 호출하여 작동한다고 생각합니다.
차분 할 파일은 10-50 줄 정도로 매우 작으므로 알고리즘의 속도는 문제가되지 않습니다. – scottm
그리고 Kristo는 그것을 O (ND)로 줄이는 논문을 이미 언급했습니다. – beef2k