Linux C 또는 C++ 라이브러리에서 문자열을 비교 및 ​​패치 할 수 있습니까?

Question

가능한 중복 :
Is there a way to diff files from C++?

내가 diff를 패치 할 긴 텍스트 문자열을 가지고있다.

string a = ...; 
string b = ...; 

string a_diff_b = create_patch(a,b); 
string a2 = apply_patch(a_diff_b, b); 

assert(a == a2); 

a_diff_b 경우는 보너스 될 사람이 읽을 수 있었다 : 그 문자열을 a와 b가 주어집니다. 이를 구현하기 위해

한 가지 방법은 diffutils 및 파이프 그들에게 문자열에서 diff 및 patch 쉘 명령을 호출 할 system(3)을 사용하는 것입니다. 또 다른 방법은 함수를 직접 구현하는 것입니다. (저는 각 행을 원자 적으로 처리하고 표준 편집 거리 n^3 알고리즘을 역 추적과 함께 사용합니다).

누군가가 좋은 리눅스 C 또는 C++ 라이브러리를 알고 있는지 궁금합니다.

Answer 1

Google에서 Myers Diff 알고리즘을 구현할 수 있습니다. ("O (ND) 차이 알고리즘 및 그 변형") 또는 "Longest common subsequence"문제를 해결하는 라이브러리.

내가 아는 한 C++의 diff/patch 상황은 좋지 않습니다. -, libmba을 비롯한 몇 가지 라이브러리가 있지만 내 경험에 따르면 다소 문서화가 잘되어 있지 않거나 중량이 많은 외부 라이브러리가 있습니다. 의존성 (diff match patch는 예를 들어 Qt 4가 필요합니다.) 또는 필요하지 않은 유형 (예 : 유니 코드가 필요할 때 std :: string)에 특화되어 있거나 충분히 제네릭이 아니거나, 높은 메모리 요구 사항 ((M + N)^2 여기서 M과 N은 입력 시퀀스의 길이 임).

Myers 알고리즘 ((N + M) 메모리 요구 사항)을 직접 구현할 수도 있지만 문제의 해결 방법은 극도로 이해하기 어렵습니다. 설명서를 읽는 데 적어도 일주일은 낭비 할 것으로 예상됩니다. 사람이 읽을 수있는 Myers 알고리즘에 대한 설명은 here입니다.

Answer 2

나는

https://github.com/cubicdaiya/dtl/wiki/Tutorial

는 당신이 필요가있을 수 있다고 생각

Answer 3

http://code.google.com/p/google-diff-match-patch/

은 diff 일치 및 패치 라이브러리 일반 텍스트를 동기화에 필요한 작업을 수행 할 수있는 강력한 알고리즘을 제공

.

현재 Java, JavaScript, Dart, C++, C#, Objective C, Lua 및 Python에서 사용할 수 있습니다. 언어에 관계없이 각 라이브러리는 동일한 API와 동일한 기능을 제공합니다. 모든 버전에는 포괄적 인 테스트 장치가 있습니다.