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

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

] [
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 до следующего байта после фрагмента и повторяйте до конца файла.[

   ][
] [

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

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

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

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

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

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

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

1. Создайте подпись одного файла с помощью E.G.

    Подпись RDIFF SIG.TXT
    

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

    RDIFF DELTA SIG.TXT B DELTA
    

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

    Rdiff Patch Delta B
    

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

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

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