Как раз экспериментирую над созданием дельты файлов, с блоками фиксированной длины и скользящим окном.
Пока, что схема такая. Файлы разбиваются на блоки, кратные 4 КБ (в зависимости от размера файла), у каждого блока считается crc32 и md5 (для уменьшения вероятности коллизии, эти 2 варианта выбраны, как наиболее быстрые из хэшей реализованных в php), а также сохраняются 5 символов с начала и конца каждого блока. Потом при следующих проходах в случае если в блоке было изменение, ищем не сместился ли конец блока влево (были удалены символы), или вправо (были добавлены символы). Если конец блока нашли, проверяем начало следующего блока, и если оно совпадет, считаем хэши.
В общем основная задача избавиться от лавинного эффекта, когда из-за добавления к примеру в начало файла одного байта изменятся хэши всех блоков в файле.