Лучший способ определить измененные данные в C ++

Question

Мне нужно написать инструмент на C ++ для определения измененных битов в файле по сравнению с другим файлом для репликации. Каков наилучший метод для достижения этой цели?

У меня нет конкретной ОС или библиотеки, я открыт для предложений. Моя основная задача - уменьшить объем сетевого трафика, участвующего в репликации.

Answer 1

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

Answer 2

Если вы не можете использовать rsync как есть, отметьте librsync . Он старый, но код легко читается и улучшается.

Answer 3

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

Для создания эффективных различий взгляните на двоичное дельта-сжатие VCDIFF (RFC 3284). Хорошей реализацией является xdelta (www.xdelta.org). Реализовать декодер / декомпрессор довольно легко, если вы хотите избежать использования xdelta на принимающей стороне из-за проблем с лицензией. Написание собственного генератора различий VCDIFF, который будет генерировать компактные разности, намного сложнее (например, поиск перемещенных блоков).

В VCDIFF различия также могут быть без исходного кода, то есть они распаковываются в целевой файл без исходного файла (файла, к которому применяется diff) - в VCDIFF сжатие файла - это особый случай создания сжатого файла. дельта между двумя файлами. Это полезно, потому что вы можете использовать один и тот же формат независимо от того, имеет ли место назначения версию вашего файла.

Answer 4

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

Answer 5

Я бы начал с попытки реализации diff (http://en.wikipedia.org/wiki/Diff)