Как вычислить дельта на файл, то есть изменена часть файла

Question

Я хочу рассчитать дельта на файл, то есть хочу получить только измененные биты файла, как это делают приложения, такие как DropBox или Google Диск.

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

Я хочу реализовать это решение на платформе Windows, поэтому я в порядке с C, C++ или C# .Net решением.

Update: Пример: Предположим, у меня есть файл X, имеющий размер 10 МБ (Binary или текст) в моей локальной просматриваемой папки. Предположим, что я изменил 1 МБ. Теперь я хочу получить только измененные байты (1 МБ) и диапазон, в котором я могу применить 1 МБ на файловом сервере. Это также называется функцией Delta Sync.

Answer 1

В Linux/Unix есть команда под названием rsync, которая в основном делает то, что вы хотите, и идея этой программы заключается в том, что она берет первый фрагмент (размером, скажем, 512 байт) измененного файла и вычисляет контрольную сумму этого фрагмента с использованием алгоритма слабой контрольной суммы и сравнить его с исходным файлом. Если контрольные суммы различны, мы обнаруживаем фрагмент, который изменился. И если слабые контрольные суммы одинаковы, тогда он вычисляет еще одну контрольную сумму этого куска, используя сильный алгоритм контрольной суммы, а затем снова сравнивает его с исходным файлом. Если контрольные суммы совпадают, мы можем быть уверены, что этот кусок не изменился. Затем программа перемещает байт (а не кусок, BYTE) вперед и подбирает другой кусок и повторяет эту процедуру. Наиболее важный момент в этом алгоритме лежит на алгоритме слабой контрольной суммы, который называется rolling checksum. Этот алгоритм контрольной суммы позволяет вычислить контрольную сумму (k + 1, k + 513) по сравнению с (k, k + 512) в O (1) раз. Вы можете узнать this для получения подробной информации об этом алгоритме.

Answer 2

Это не то, что делает Drive или Dropbox, когда они отмечают файл как измененный, они перезагружают весь документ. По правде говоря, когда вы сохраняете что-то, кто хочет сказать, что важная информация разбросана в разных местах двоичного файла, который является документом.