Алгоритм сжатия, работающий на предварительно построенном словаре в качестве структуры данных

Question

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

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

Например, я бы запустил его на 10 000 сообщений общим объемом 10 МБ, чтобы определить словарьструктура данных, делитесь этим словарем между всеми сторонами, а затем обменивайтесь сообщениями, наслаждаясь очень быстрым и сильным сжатием.

Есть ли что-то в этом роде?IBM DB2 делает именно это , но я сомневаюсь, что они открыли этот подход.zlib позволяет передавать словарь , но это необработанный байтовый массив, который необходимо обрабатывать для каждого сообщения, и нет способа генерирования указанного байтового массива.

Идея храненияструктура данных в памяти позволяет избежать накладных расходов при обработке сообщений.

Бонусные баллы за реализацию Java.

Answer 1

В конце концов меня указали на Zstd компрессию , которая позволяет предоставить ваш собственный (общий) словарь.Есть Java-привязки с возможностью обучения словарю на основе выборок.

Он способен превзойти мой собственный алгоритм с общим словарем всего в 512 байт:

(s - количество выборок, d - длина словаря, l - уровень сжатия)

Answer 2

В итоге я реализовал собственное сжатие с использованием гибрида LZW-Хаффмана.

Я строю словарь (используя набор справочных данных), используя LZW, где кодовые точки отображаются на последовательности байтов, а затем создаю дерево Хаффмана из этих кодовых точек 'частоты.Затем я использую TreeMap, чтобы найти последовательности байтов во входном массиве, передать их кодеру Хаффмана.

Это работает достаточно хорошо.Сжатие 0,4 типично для ~ 120-байтовых записей, где GZip дает 0,75.

Тем не менее меня интересуют оптимизированные решения для этой проблемы.