Ich habe lange Textstrings, die ich diff und patchen möchte. Das sind die Strings a und b:
%Vor% Wenn a_diff_b lesbar wäre, wäre das ein Bonus.
Eine Möglichkeit, dies zu implementieren, wäre die Verwendung von system(3) , um die Shell-Befehle diff und patch von diffutils aufzurufen und ihnen die Zeichenfolgen zu übergeben. Ein anderer Weg wäre, die Funktionen selbst zu implementieren (ich dachte mir, jede Zeile atomar behandeln und den Standard-Edit-Abstand n ^ 3 Algorithmus zeilenweise mit Backtracking verwenden).
Ich habe mich gefragt, ob jemand eine gute Linux C oder C ++ Bibliothek kennt, die den Job im Prozess erledigen würde?
Sie könnten die Implementierung des Myers-Diff-Algorithmus googeln. ("Ein O (ND) Differenzalgorithmus und seine Variationen") oder Bibliotheken, die das "Längste gemeinsame Teilsequenz" -Problem lösen.
Soweit ich weiß, ist die Situation mit diff / patch in C ++ nicht gut - es gibt mehrere Bibliotheken (einschließlich Diff Match Patch , libmba ), aber meiner Erfahrung nach sind sie das entweder etwas schlecht dokumentiert oder haben starke externe Abhängigkeiten (diff Match-Patch erfordert Qt 4, zum Beispiel) oder sind spezialisiert auf Typ, den Sie nicht benötigen (std :: string, wenn Sie beispielsweise Unicode benötigen), oder sind nicht generisch genug oder verwenden einen generischen Algorithmus, der sehr hohe Speicheranforderungen hat ((M + N) ^ 2, wobei M und N Längen von Eingabesequenzen sind).
Sie könnten auch versuchen, Myers-Algorithmus ((N + M) Speicheranforderungen) selbst zu implementieren, aber die Lösung des Problems ist extrem schwierig zu verstehen - erwarten Sie, mindestens eine Woche zu verschwenden Dokumentation zu lesen. Eine etwas für Menschen verständliche Erklärung des Myers-Algorithmus ist hier verfügbar.
Die Bibliotheken "Diff Match" und "Patch" bieten robuste Algorithmen für die zum Synchronisieren von Nur-Text erforderlichen Operationen.
Derzeit verfügbar in Java, JavaScript, Dart, C ++, C #, Objectiv C, Lua und Python. Unabhängig von der Sprache verfügt jede Bibliothek über die gleiche API und die gleiche Funktionalität. Alle Versionen verfügen auch über umfangreiche Prüfkabel.