Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Сопоставление 2-х крупных бинарных файлов

Anna | 24.06.2014 | нет комментариев

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

#0 Постановка задачи.

На работе мне поставили такую задачу: сделать патчер.
На вход прилетают два файла. Нужно выдать файлик

диффа

файл, в котором описаны по определенным правилам отличия между двумя файлами.

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

#1 Типовые способы решения

Существует два основных подхода — на LCS(longest common sequence) и так либо напротив использующих хэши.
Начнем по порядку.

LCS

Объясню, отчего LCS. Ищем LCS от 2-х файлов, все, что в нее не попало, считаем разницей, дальше пишем в дифф список блоков на удаление и на добавление.
Все легко, осталось обнаружить LCS.
На прогре много статей, описывающих различные алгорифмы.
Предшествующий передо мною автор патчера, видимо, ничего не слышал о том, что у алгорифмов есть трудность, и написал поиск LCS через димамической программирование. Это примитивный алгорифм, пишется стремительно и отменно работает на маленьких файлах. Но вот трудность у него

O(n*m)

n и m размеры файлов, до конца поста

. И по памяти тоже O(n*m). Хорошо, по памяти от нас ничего не требовали, а считает все равно сервер, у него памяти много. Но вот квадратичная трудность по времени убивала все. Сервер обсчитывал 600 Мб файл за 6 часов. Нехорошо, но это будет отправным временем сопоставления результативности тех либо иных идей. Так как я был вторым, я решил свои тесты проводить не на сервере, а на обыкновенном ноуте, Дабы все было Добросовестно.
LCS в той либо другой мере применяется юниксовой утилитой diff(с значительными доработками, безусловно).
Какие же есть алгорифмы?
Есть ДП — время квадрат, память квадрат.
Есть алгорифм Хиршберга — время квадрат, память линейна. Это отменнее, но мы соревнуемся по секундомеру.
Есть алгорифм с nlogn и по времени и по памяти, но хочется стремительней.
И, наконец, есть алгорифм с линейной памятью и временем O(n*(n-sizeof(LCS)). Здорово! Рассматривая, что разница между различными версиями файлов крошечная, порядка 1% для файлов в 300Мб и дальше уменьшается(объем изменений непрерывен, относительный объем уменьшается), то это примерно линия! Но, константы этого алгорифма слишком крупные. И выигрывает он лишь в дальнем громадном необозримом размере файла.
Так что нет, не LCS.
p.s. изложения этих алгорифмов легко гуглятся, так что не буду увеличивать и без того огромный пост лишними словами.

Хэши

Самая знаменитая утилита, реализующая эту парадигму, именуется Rsync. Я даже слышал о ней до того, как занялся этой задачей.
Алгорифм Rsync описывался на прогре, и дюже хорошо, так что вновь гугл вам в поддержка.
Основная идея в том, что один из файлов дерется на блоки, для них считаются слабые и крепкие хэши, потом идем по второму файлу, считаем слабый хэш, если он совпал, то проверяем, верно ли блоки идентичны, мощным хэшем. Слабый хэш считается стремительно, мощный обеспечивает наименьшее допустимое число коллизий. Криптоустойчивость здесь ни к чему, так что берется обыкновенно MD5.(про криптоустойчивость MD5 — им рекомендовали не пользоваться в шифровании, вновь гугл в поддержка).
Так что принимаем волевое решение — сегодня мы любим хэши, а не LCS.

#3 Выбранный алгорифм и реализация.

Изначально алгорифм был такой. Считываем файлы, для ветхого файла считаем кольцевые хэши для всякого байтового сдвига.

кольцевой хэш

Хэш такой, что для вычисления от строки не нужно знать строку. Нужно знать только значения хэша дой ~<4. На два файла по 600 Мб у моего ноута хватает оперативы. Правда ее каждого 4Гб.
Время — 18 секунд для 600Мб. Это с вводом(написанным лишь бы был), хэширование поиск, и итог(тоже лишь бы был).
Типичный ввод/вывод даст еще пару секунд максимум. Размер патча недурен — с изменениями в 1,5% дифф весит 600Kb. Рядом лежит 15мб файл с блоками, которые нужно вставить либо записать взамен каких-то.
Код примитивен, как душа комсомолки, фактически чистый STL и ничего больше.
Ну только аллокаторы сам написал, чтоб не было переаллокаций, а сразу выделял столько, сколько в конце концов необходимо будет.Итог — С 11 классен, а трудности нужно знать и понимать =)

p.s. к сожалению каждый код — торговая тайна, но вам не составит труда написать сходственное)

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB