Хороший алгоритм сжатия для маленьких кусков данных? (размером около 2К) - PullRequest
6 голосов
/ 29 сентября 2011

У меня есть система с одним компьютером, генерирующая небольшие порции данных в виде объектов, содержащих массивы целых и длинных. Эти куски передаются на другой сервер, который, в свою очередь, распространяет их в другом месте.

Я хочу сжать эти объекты, чтобы уменьшить нагрузку на память на сквозном сервере. Я понимаю, что алгоритмы сжатия, такие как deflate, должны создавать словарь, чтобы что-то подобное не работало с такими маленькими данными.

Существуют ли алгоритмы, которые могли бы эффективно сжимать данные?

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

Не то чтобы я думаю, что это имеет значение, но целевой системой является Java.

Изменить: Гамма-код Elias будет лучшим для этой ситуации?

Спасибо

Ответы [ 4 ]

3 голосов
/ 30 сентября 2011

Если вы считаете, что сокращение пакета данных до уровня энтропии в лучшем случае является наилучшим, попробуйте простое сжатие Хаффмана.

Для раннего просмотра того, насколько хорошо это будет сжиматься, вы можете передать пакет через Huff0: http://fastcompression.blogspot.com/p/huff0-range0-entropy-coders.html

Это простой кодер Хаффмана 0-го порядка. Таким образом, результат будет представительным.

Для более конкретных идей о том, как эффективно использовать характеристики ваших данных, рекомендуется немного описать, какие данные содержатся в пакетах и ​​как они генерируются (как вы сделали в комментариях, поэтому они являются целочисленными ( 4 байта?) И long (8 байтов?)), А затем предоставьте один или несколько образцов.

2 голосов
/ 30 сентября 2011

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

Важно то, что вам нужно согласовать код, который вы используете, с распределением значений.вы ожидаете от своих данных: чтобы получить хороший результат от гамма-кодирования Elias, вам нужно убедиться, что значения, которые вы кодируете, являются маленькими положительными целыми числами ...

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


Если вы беспокоитесь, что вашКомпрессор может превратиться в «расширитель», вы можете добавить начальный флаг, чтобы указать, сжимаются ли данные или нет.Затем, в худшем случае, когда ваши данные вообще не соответствуют вашей модели сжатия, вы всегда можете скопировать и отправить несжатую версию;ваш наихудший случай - размер флага ...

1 голос
/ 29 сентября 2011

Я бы внимательно рассмотрел параметры вашей библиотеки сжатия, например, deflateSetDictionary () и флаг Z_FILTERED в http://www.zlib.net/manual.html. Если вы можете распространять - или использовать в исходном коде - согласованный словарь дляотправитель и получатель заблаговременно, и если этот словарь представляет реальные данные, вы должны получить приличную экономию сжатия.К сожалению, в Java посмотрите java.util.zip.Deflater.setDictionary () и FILTERED.

1 голос
/ 29 сентября 2011

Elias Gamma Coding может фактически увеличить размер ваших данных.

У вас уже есть верхние границы ваших чисел (все, что вписывается в 4- или, возможно, 8-байтовый int / long). Этот метод кодирует длину ваших номеров, а затем ваш номер (вероятно, не то, что вы хотите). Если вы получите много маленьких значений, это может сделать вещи меньше. Если вы также получите большие значения, это, вероятно, увеличит размер (8-байтовое максимальное значение без знака станет почти в два раза больше).

Посмотрите на энтропию ваших пакетов данных. Если оно близко к максимуму, сжатие будет бесполезным. В противном случае попробуйте другие компрессоры GP. Но я не уверен, что время, потраченное на сжатие и распаковку, стоит уменьшения размера.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...