Алгоритм эффективного сравнения огромных файлов

Question

Мне нужно сохранить два файла A и B, оба очень большие (около 100 ГБ).Однако B, вероятно, во многом будет похож на A, поэтому я мог бы сохранить A и diff(A, B).У этой проблемы есть два интересных аспекта:

1. Файлы слишком велики для анализа любой известной мне библиотеки различий, поскольку они находятся в памяти.
2. На самом деле мне не нужен diff - обычно в diff есть вставки, изменения и удаления, потому что он предназначен для чтения людьми.Я могу обойтись меньшим количеством информации:Мне нужно только «новый диапазон байтов» и «копировать байты из старого файла с произвольным смещением».

В настоящее время я не понимаю, как вычислить дельту от A до B в этих условиях.Кто-нибудь знает алгоритм для этого?

Опять же, проблема проста:Напишите алгоритм, который может хранить файлы A и B с минимальным количеством байтов, учитывая тот факт, что оба они очень похожи.

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

Answer 1

Взгляните на алгоритм RSYNC, поскольку он предназначен именно для этого и позволяет эффективно копировать дельты.Насколько я помню, алгоритм довольно хорошо документирован.

Answer 2

Вы можете использовать rdiff, который очень хорошо работает с большими файлами.Здесь я создаю разницу двух больших файлов A и B:

1. Создайте подпись одного файла, например.

   rdiff signature A sig.txt
   

2. используя сгенерированный файл подписи sig.txt и другой большой файл, создайте дельту:

   rdiff delta sig.txt B delta
   

3. сейчас delta содержит всю информацию, необходимую для воссоздания файла B когда у тебя есть оба A и delta.Чтобы воссоздать B, запустите

   rdiff patch A delta B
   

В Ubuntu просто запустите sudo apt-get install rdiff чтобы установить его.Это довольно быстро, у меня на ПК получается около 40 МБ в секунду.Я только что попробовал это с файлом размером 8 ГБ, и память, используемая rsync, составила около 1 МБ.

Answer 3

Это именно проблема, известная как «дедупликация данных».Наиболее часто используемый подход:

• Прочитайте файлы в блоках:
  • Разделите данные на так называемые «куски».Наиболее часто используемый подход называется «Разбиение на части, определяемое контентом, с использованием метода отпечатков пальцев Рабинса» (Код).Использование такого подхода к фрагментированию приводит к лучшей дедупликации большинства наборов данных, чем использование фрагментов статического размера (например,показано здесь).
  • Отпечатки пальцев на кусках, используя метод криптографического снятия отпечатков пальцев, напримерША-256.
  • Сохраните отпечатки пальцев в индексе и найдите каждый фрагмент, если отпечаток пальца уже известен.Если отпечаток известен, нет необходимости сохранять чанк второй раз.Данные необходимо сохранить только в том случае, если отпечаток пальца неизвестен.

Такой алгоритм дедупликации данных не так точен, как, например. xdelta, но он быстрее и масштабируемее для больших наборов данных.Фрагментирование и снятие отпечатков пальцев выполняются со скоростью около 50 МБ/с на ядро ​​(Java).Размер индекса зависит от избыточности, размера фрагмента и размера данных.Для 200 ГБ он должен поместиться в памяти для размеров фрагментов, например.16 КБ.

Бентли и Макилой подход к сжатию очень похож (используется, например,от Googles BigTable), однако мне неизвестны какие-либо готовые инструменты командной строки, использующие технику сжатия.

А "фс-с" Проект с открытым исходным кодом содержит большую часть необходимого кода.Однако сама fs-c пытается только измерить избыточность и анализируемые файлы в памяти или с помощью Хадуп кластер.

Answer 4

один вопрос - каков размер записи в ваших файлах, т.е.могут ли смещения меняться побайтно или файлы состоят, скажем, из блоков по 1024 байт.Предполагая, что данные байтово-ориентированные, вы можете сделать следующее:

1. Создайте массив суффиксов для файла A.Этот массив представляет собой перестановку всех значений индекса файла A.Если A имеет 2 ^ 37 байтов, то массив индексов проще всего представить 64-битными целыми числами, поэтому каждый байт (смещение по отношению к файлу) соответствует 8 байтам в массиве индексов, поэтому массив индексов будет иметь длину 2 ^ 40 байт, тогда .Например.800 ГБ, скажем.Вы также можете индексировать только каждую 1024-ю позицию, скажем, чтобы уменьшить размер индексного массива.Это ухудшает качество упаковки в зависимости от продолжительности средних тиражей копируемых фрагментов.

2. Теперь, чтобы жадно упаковать файл B, вы начинаете с его начала со смещением o = 0, а затем используете массив индексов, чтобы найти самое длинное совпадение в A, которое соответствует данным, начинающимся с «o».Выводите пару в запакованный файл.В вашем случае без какой-либо кодировки это занимает 16 байт, поэтому, если прогон <16 байт, вы фактически теряете место.Это можно легко исправить, используя кодирование на уровне битов и используя битовый маркер, чтобы отметить, кодируете ли вы изолированный байт (маркер + 8 бит = 9 бит) или пару смещение/длина (маркер + 40 бит + 40 бит = 81). бит), скажем.После упаковки самого длинного фрагмента в o увеличьте o до следующего байта после фрагмента и повторяйте до конца файла.

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

Answer 5

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

Если вам нужно произвольное выравнивание байтов и вы действительно заботитесь о производительности, посмотрите Симхаш алгоритм, и используйте его для поиска похожих, но невыровненных блоков.