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

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

Вы можете использовать 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 МБ.

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

• Read over the files in blocks:
  • Split the data of the so called "chunks". The most often used approach is called "Content defined Chunking using Rabins Fingerprinting method" (Code). Using that chunking approach leads to a better deduplication on most data set then using static sized chunks (e.g. shown here).
  • Отпечатайте фрагменты с помощью криптографического метода снятия отпечатков пальцев, например. ША-256.
  • Сохраняйте отпечатки пальцев в индексе и ищите каждый фрагмент, если отпечаток уже известен. Если отпечаток известен, нет необходимости сохранять фрагмент во второй раз. Только когда отпечаток пальца неизвестен, данные должны быть сохранены.

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

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

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

один вопрос - каков размер записи в ваших файлах, т.е. могут ли смещения меняться байт за байтом или файлы состоят, скажем, из блоков 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 до следующего байта после фрагмента и повторите до конца файла.

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

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

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