Дельта-кодирование / декодирование потокового файла
Вот проблема — я хочу сгенерировать дельту двоичного файла (размером> 1 МБ) на сервере и отправить дельту на встроенное устройство с ограниченным объемом памяти (мало оперативной памяти и без динамической памяти) через HTTP. Дельты предпочтительны (в отличие от отправки полного двоичного файла с сервера) из-за высокой стоимости передачи данных по проводам.
Проблема в том, что встроенное устройство не может декодировать дельты и создавать содержимое нового файла в памяти. Я изучил различные алгоритмы двоичного дельта-кодирования / декодирования, такие как bsdiff, VCDiff и т. Д., Но не смог найти библиотеки, поддерживающие потоковую передачу.
Возможно, вместо того, чтобы спрашивать, есть ли подходящие библиотеки, можно ли использовать альтернативные подходы, которые все равно решат исходную проблему (отправка минимальных данных по сети)? Хотя было бы полезно, если бы существовали подходящие дельта-библиотеки, поддерживающие потоковое декодирование (написанные на C или C ++ без использования динамической памяти).
Решение
Сохраните на сервере копию текущего файла, хранящуюся на встроенном устройстве. Если вы хотите отправить обновление, выполните XOR новой версии файла со старой версией и сожмите результирующий поток любым разумным компрессором. (Алгоритмы, которые позволяют дорогостоящее кодирование, чтобы позволить дешевое декодирование, были бы особенно полезны здесь.) Отправьте сжатый поток на встроенное устройство, которое считывает поток, распаковывает его на лету и непосредственно выполняет XOR (копию) цели файл.
Если ваши обновления таковы, что содержимое файла мало меняется со временем и сохраняет фиксированную структуру, поток XOR будет преимущественно нулевым и будет очень хорошо сжиматься: количество передаваемых байтов будет небольшим, усилия по распаковке будут низкими, требования к памяти на встроенном устройстве будет минимальным. Чем дальше ваша модель от этих предположений, тем меньше этот подход принесет вам пользу.
Другие решения
Поскольку вы сказали, что дельта может быть произвольно случайной (от нулевой дельты до совершенно другого файла), сжатие дельты может быть проигрышным. Сжатие случайных двоичных данных без потерь теоретически невозможно. Кроме того, поскольку встроенное устройство в любом случае имеет ограниченную память, использование сложной — и, следовательно, вычислительно дорогой — библиотеки для сжатия / распаковки случайной «простой» дельты, вероятно, будет невозможно.
Я бы рекомендовал просто отправить новый файл на устройство в необработанном байтовом формате и перезаписать существующий старый файл.
Как отметил Кевин, сжатие случайных данных не должно быть вашей целью. Было бы полезно добавить еще несколько комментариев о типе данных, с которыми вы работаете. Контекст является ключевым в сжатии.
Вы использовали термин «изображение», что делает его похожим на вызов классического видеокодека. Если вы когда-либо видели странные эффекты сглаживания видео, которые влияют на часть кадра, которая изменилась, а затем вдруг все проясняется. Вы, вероятно, были свидетелями понятия ключевого кадра вместе с серией дельта-кадров. Где дельта-кадры не были применены должным образом.
В этой модели сервер решает, что дешевле:
- полный ключевой кадр
- дельта-команды
Дельта-команды передаются в виде последовательности инструкций записи, которые могут перекрывать существующий буфер клиента.
Пример формата:
- [Адрес] [Длина] [Повтор] [Delta Payload]
- [Адрес] [Длина] [Повтор] [Delta Payload]
- [Адрес] [Длина] [Повтор] [Delta Payload]
Вероятно, существует множество методов для вычисления этих дельта-команд. Метод грубой силы будет:
- Выполните Смит Waterman между двумя изображениями.
- Сожмите полученное преобразование в дельта-команды.