Linux C или C ++ библиотека для сравнения и исправления строк?

Question

Linux C или C ++ библиотека для сравнения и исправления строк?

Возможный дубликат:
Есть ли способ сравнения файлов из C ++?

У меня есть длинные текстовые строки, которые я хочу изменить и исправить. То есть заданы строки a и b:

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 был читабельным, что было бы бонусом.

Одним из способов реализации этого было бы использовать system(3) позвонить diff а также patch Команды оболочки от diffutils и труба им струны. Другим способом было бы реализовать эти функции самостоятельно (я думал, что нужно обрабатывать каждую строку атомарно и использовать стандартный алгоритм редактирования расстояния n ^ 3 аналогично с возвратом назад).

Мне было интересно, если кто-нибудь знает хорошую библиотеку Linux C или C ++, которая будет выполнять эту работу в процессе?

9

algorithm c++diff linux

Решение

Другие решения

я полагаю, что

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

может иметь то, что вам нужно

7

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

Библиотеки Diff Match и Patch предлагают надежные алгоритмы для выполнения операций, необходимых для синхронизации простого текста.

В настоящее время доступны на Java, JavaScript, Dart, C ++, C #, Objective C, Lua и Python. Независимо от языка каждая библиотека имеет одинаковый API и одинаковые функциональные возможности. Все версии также имеют комплексные тестовые комплекты.

2

Источник

Accepted Answer

Вы могли бы Google реализовать алгоритм Майерса Диффа. («Разностный алгоритм O (ND) и его вариации») или библиотеки, которые решают проблему «самой длинной общей подпоследовательности».

Насколько я знаю, ситуация с diff / patch в C ++ не очень хорошая — есть несколько библиотек (включая патч сравнения, libmba), но, по моему опыту, они либо плохо документированы, либо имеют сильные внешние зависимости (например, для diff match patch требуется Qt 4), либо специализируются на типе, который вам не нужен (std :: string, когда вам нужен unicode, например), или не достаточно универсальны, или используют универсальный алгоритм, который имеет очень высокие требования к памяти ((M + N) ^ 2, где M и N — длины входных последовательностей).

Вы также можете попытаться реализовать алгоритм Майерса ((N + M) требований к памяти) самостоятельно, но решение проблемы чрезвычайно сложно понять — вы можете потратить хотя бы неделю на чтение документации. Доступно несколько понятное человеку объяснение алгоритма Майерса Вот.

7