Diffing быстрее

Question

Я работаю над анализом больших двоичных файлов.Я реализовал знаменитый алгоритм Майерса Диффа, который производит минимальный дифференциал.Тем не менее, это O (ND), поэтому для различий двух очень разных файлов размером 1 МБ, я предполагаю, что потребуется время 1 миллион в квадрате = 1 триллион.Это нехорошо!

Мне нужен алгоритм, который создает потенциально неминимальную разность, но делает это намного быстрее.Я знаю, что нужно существовать, потому что Beyond Compare делает это.Но я не знаю как!

Конечно: есть такие инструменты, как xdelta или bdiff, но они производят патч, предназначенный для использования компьютером, который отличается от различий, потребляемых человеком.Патч связан с преобразованием одного файла в другой, поэтому он может выполнять такие вещи, как копирование из предыдущих частей файла.Дифференцированный для человека дифференциал предназначен для визуального отображения различий и может только вставлять и удалять.Например, это преобразование:

"puddi" -> "puddipuddipuddi"

даст небольшой патч из "copy [0,4] в [5,9] и в [10,14] ", но больше различий в" append 'puddipuddi' ".Я заинтересован в алгоритмах, которые производят большую разницу.

Спасибо!

Answer 1

Diffing - в основном тот же алгоритм, который используется в биоинформатике для выравнивания последовательностей ДНК.Эти последовательности часто бывают большими (миллионы или миллиарды нуклеотидов длиной), и одна из стратегий, которая хорошо работает там с более длинными геномами, используется программой MUMmer :

1. Быстрый поиск всех Максимальные уникальные соответствия (подстроки, которые появляются в обоих файлах и которые не могут быть расширены в обоих направлениях при сохранении этого условия) с использованием дерева суффиксов
2. Быстрый поиск самого длинного подмножества MUM, которые появляются в последовательныхПорядок в обоих файлах с использованием алгоритма динамического программирования с наибольшей увеличивающейся подпоследовательностью
3. Исправьте это подмножество MUM в выравнивании (т. е. пометьте эти области как совпадающие)
4. Если это необходимо, выполните медленнее (например,Майерс) Разница между регионами MUM.В вашем случае вы, вероятно, пропустили бы этот шаг полностью, если бы обнаружили, что длина самого длинного MUM была ниже некоторого порогового значения (которое вы могли бы считать доказательством того, что 2 файла не связаны).

Этоимеет тенденцию давать очень хороший (хотя и не гарантированный оптимальный) набор выровненных областей (или, что эквивалентно, очень маленький набор различий) всякий раз, когда нет слишком много различий.Я не уверен в точных временных границах для каждого шага, но я знаю, что нет терминов n^2 или выше.

Я считаю, что программе MUMmer требуются последовательности ДНК или белка, поэтому она может не работатьдля вас, но понятия, безусловно, применимы к общим строкам (например, файлам), поэтому, если вы готовы переопределить их самостоятельно, я бы порекомендовал этот подход.

Answer 2

С точки зрения производительности по мере увеличения размера файла, GNU Diffutils , вероятно, является наиболее надежным вариантом. В вашей ситуации я бы, вероятно, использовал формат параллельного сравнения , который, пожалуй, самый дружелюбный из всех. В противном случае вы снимаете вывод в другом формате и выполняете некоторую работу, чтобы сделать его красивым.

Хорошим конкурентом, чья производительность постоянно улучшается, включая многочисленные ускорения, является diff-match-patch . Он реализует алгоритм Myers Diff на нескольких языках, включая Java и JavaScript. См. онлайн демо для примера последнего с довольно печатными результатами. Если вы хотите провести различие между строками, изучите вики для подсказок о том, как использовать его для этой цели.