Bibliothèque Linux C ou C ++ pour diff et les chaînes de patch?

Duplication possible:
Existe-t-il un moyen de diffuser les fichiers à partir de C ++?

J’ai de longues chaînes de texte que je souhaite diffuser et corriger. Cela est donné les chaînes a et b:

ssortingng a = ...; ssortingng b = ...; ssortingng a_diff_b = create_patch(a,b); ssortingng a2 = apply_patch(a_diff_b, b); assert(a == a2);

Si a_diff_b était lisible par l’homme, ce serait un bonus.

Une manière de l’implémenter serait d’utiliser le system(3) pour appeler les commandes du shell diff et patch partir de diffutils et les canaliser. Une autre façon serait d’implémenter les fonctions moi-même (je pensais traiter chaque ligne de manière atomique et utiliser l’algorithme de distance d’édition standard n ^ 3 en ligne avec le retour en arrière).

Je me demandais si quelqu’un connaissait une bonne bibliothèque Linux C ou C ++ qui ferait le travail en cours?

Vous pouvez google mise en œuvre de l’algorithme Myers Diff. (“Un algorithme de différence O (ND) et ses variantes”) ou des bibliothèques qui résolvent le problème de “sous-séquence commune la plus longue”.

Pour autant que je sache, la situation avec diff / patch en C ++ n’est pas bonne – il existe plusieurs bibliothèques (y compris le correctif de correspondance diff , libmba ), mais selon mon expérience, elles sont peu documentées ou ont de fortes dépendances externes ( Le patch de correspondance diff nécessite Qt 4 par exemple) ou sont spécialisés sur le type dont vous n’avez pas besoin (std :: ssortingng lorsque vous avez besoin d’unicode, par exemple) ou ne sont pas assez génériques, ou utilisez un algorithme générique avec une mémoire très élevée exigences ((M + N) ^ 2 où M et N sont des longueurs de séquences d’entrée).

Vous pouvez également essayer d’implémenter vous-même l’algorithme de Myers ((N + M)), mais la solution du problème est extrêmement difficile à comprendre – attendez-vous à lire au moins une semaine de documentation. Une explication assez lisible de l’algorithme Myers est disponible ici .

je crois que

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

peut avoir ce dont vous avez besoin

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

Les bibliothèques Diff Match et Patch offrent des algorithmes robustes pour effectuer les opérations nécessaires à la synchronisation du texte brut.

Actuellement disponible en Java, JavaScript, Dart, C ++, C #, Objective C, Lua et Python. Quelle que soit la langue, chaque bibliothèque dispose de la même API et des mêmes fonctionnalités. Toutes les versions ont également des harnais de test complets.