Алгоритмы сжатия данных с использованием внешнего словаря и их реализация
Практически все существующие алгоритмы сжатия данных без потерь (имеется в виду сжатие бинарных данных) работают по принципу — анализ данных с набором некой информации (таблицы частот блоков, словари перекодирования,..), в последствии эти данные помещаются по блочно в архив (возможны ситуации с их динамическим изменением).
Но если вместо того, чтобы хранить этот словарь в самом архиве, его можно было бы хранить отдельно (и передавать отдельно по сети, независимо от основного потока данных)… или например хранить в самом архиваторе для различных типов данных… вариант с передачей данных смотрится гораздо привлекательнее, то это могло бы значительно повысить коэффициент сжатия.
Зачастую сеанс связи по сети между приложениями основывается на небольшом количестве типов сообщений, форматы которых совпадают, отличаются только данные (значения полей). Практически бессмысленно упаковывать каждое сообщение по отдельности (с этим вполне справляются железные решения на уровне создания канала, или те же vpn-сети), но если сжимать весь сеанс связи, то это может позволить повысить степень сжатия на порядок.
Простейший пример (я его реализовывал в одном своем приложении, вполне полезно и удобно) с использованием алгоритма diff (а точнее bzdiff — это почти то же самое но результат сжимается bz).
Есть серия сообщений (для простоты предположим что они одного формата).
* выбираем первое/любое сообщение как шаблон (его отсылаем на другой узел как указание появления шаблона)
* каждое последующее сообщение сравниваем с текущим шаблоном с использованием алгоритма diff
* полученный патч отсылаем с указанием идентификатора шаблона
* на другом узле восстанавливаем сообщение с использованием указанного шаблона и присланного патча
* при отсутствии шаблона на удаленном узле высылать само сообщение с указанием нового идентификатора
При каждом сравнении сообщения с шаблоном можно использовать несколько шаблонов (хранить несколько, например последних использованных, или сортировать по частоте совпадений), т.е. выбирать, на основе какого шаблона делать патч (естественно использовать тот, у кого наименьший размер патча). Изменение списка сохраненных шаблонов можно ограничить, с целью минимизации рассылки новых/измененных шаблонов, тут большое пространство для экспериментов.
В данном алгоритме внешним словарем является этот набор шаблонов, понятно что это частный случай, в более универсальном виде словарь и алгоритмы сжатия могут быть боле сложными и между узлами может быть передана более подробная информация.
Конкретно этот алгоритм работал для сжатия текстовых данных с веб-сайтов (сообщения — новые версия страниц ограниченного набора веб-сайтов), я думаю бессмысленно сообщать что в этом случае размер передаваемого сообщения был предельно сокращен до размера изменений на страницах, степень сжатия — пара порядков, естественно ни один алгоритм сжатия самих сообщений не мог дать такого.
Алгоритмы почти наверняка хорошо распараллеливаются (т.е. может быть использованы более дешевые вычислительные мощности, например GPU), т.е. возможно создание комплекса для сжатия данных в канале связи (особенно если это вынужденно узкий канал).
Внимание вопрос… я делаю очередной велосипед или тут 'поле не пахано'? Есть ли готовые решения и библиотеки (в идеале opensource, так как возможны слишком узкие ниши применения с соответствующими требованиям к исправлениям, плюс гибкость выбора платформ)?
Вопрос номер два — есть ли те, кому требуется сократить нагрузку на каналы связи (если их мало или они дорогие, например спутниковая связь)?
Эх, велосипеды-велосипедики.
Большинство алгоритмов сжатия как раз основывается на алгоритмах Хаффмана и Шеннона-Фано, просто их «словарь» (кодовое дерево) хранится вместе со сжатыми данными и в результате архив является самодостаточным.
Если говорить относительно передачи данных, то в прикладной разработке существуют такие библиотеки как Apache Thrift и Google Protobuf, которые заранее позволяют сгенерировать структуры, описывающие формат данных, а затем при пересылке использовать компактные бинарные форматы и передавать необходимый минимум данных.
Я же не говорю о формате данных… нужны именно алгоритмы!
Чем мне поможет Apache Thrift? если именно его вызовы я собираюсь упаковывать, за счет повторяющихся данных в сообщениях, разнесенных во времени, а так же за счет 'лишней' информации в сообщениях, определенных их форматом (rpc — xml или json, если конечно не бинарный формат, который далеко не каждое приложение поддерживает, очень кушает трафик тупо за счет имен тегов и другой синтаксической обвязки).
У меня был пример где тупо на тегах и атрибутах уходило значительно больше половины трафика (я просто сравнил размер сообщения и объем данных в них, представленный в текстовом виде), особенно это заметно если параметры вызовов сложные структуры без текстовых данных, — таблицы и просто объекты с большим количеством полей.
Конечно в этом приложении мне не требовалось уменьшать трафик
Простой