Лучший алгоритм сжатия? (см. ниже определение лучшего)

Question

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

• маленький сжатый размер
• самое быстрое де / сжатие
• оптимальный компромисс ("колено" кривой компромисса)

Мои данные выглядят так:

(<int>, <int>, <double>), 
(<int>, <int>, <double>), 
...
(<int>, <int>, <double>)

Один из двух целых относится к моменту времени, и очень вероятно, что числа, заканчивающиеся в одном списке, близки друг к другу. Другое int представляет абстрактный идентификатор, и значения с меньшей вероятностью будут близки, хотя они также не будут полностью случайными. Двойник представляет показания датчика, и хотя между значениями есть некоторая корреляция, он, вероятно, не очень полезен.

Answer 1

Поскольку целые числа «время» могут быть близки друг к другу, попробуйте сохранить только первое, а после этого сохранить разницу с целым числом до (дельта-кодирование). Вы можете попробовать то же самое для второго int тоже.

Еще одна вещь, которую вы можете попробовать - это реорганизовать данные из [int1, int2, double], [int1, int2, double] ... в [int1, int1 ...], [int2, int2 ...] , [двойной, двойной ...].

Чтобы узнать диапазон сжатия, в котором будет находиться ваш результат, вы можете записать свои данные в файл и загрузить компрессор CCM от Christian Martelock здесь . Я обнаружил, что это очень хорошо работает для таких сборов данных. Он использует довольно быстрый алгоритм смешивания контекста . Вы также можете сравнить его с другими компрессорами, такими как WinZIP, или использовать библиотеку сжатия, например, zLib, чтобы посмотреть, стоит ли это усилий.

Answer 2

Сортируйте как уже предложено, затем сохраните

(первые целые) (вторые целые) (Удваивается)

транспонированная матрица. Затем сжатый

Answer 3

Вот общая схема, используемая в большинстве поисковых систем: хранить дельты значений и кодировать дельту, используя схему кодирования переменной байта, то есть, если дельта меньше 128, она может кодироваться только 1 байтом. Подробности смотрите в vint в буферах Lucene и Protocol.

Это не даст вам лучший коэффициент сжатия, но обычно самый быстрый для пропускной способности кодирования / декодирования.

Answer 4

Большинство алгоритмов сжатия будут одинаково плохо работать с такими данными. Тем не менее, есть несколько вещей («предварительная обработка»), которые вы можете сделать, чтобы увеличить сжимаемость данных перед подачей их в gzip-файл или алгоритм, подобный дефлятированию. Попробуйте следующее:

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

Далее, если меры предпринимаются с регулярными интервалами, замените временную метку на разницу с предыдущей временной меткой (за исключением, конечно, самого первого набора для датчика.) Например, если все меры приняты за 5 минут интервалы, дельта между двумя временными метками обычно будет близка к 300 секундам. Поэтому поле временной метки будет гораздо более сжимаемым, так как большинство значений равны.

Затем, предполагая, что измеренные значения стабильны во времени, замените все показания на дельту от предыдущего показания для того же датчика. Опять же, большинство значений будут близки к нулю и, следовательно, будут более сжимаемыми.

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

Answer 5

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

Например, в C # с protobuf-net вы можете просто создать класс для хранения данных:

[ProtoContract]
public class Foo {
    [ProtoMember(1)]
    public int Value1 {get;set;}
    [ProtoMember(2)]
    public int Value2 {get;set;}
    [ProtoMember(3)]
    public double Value3 {get;set;}
}

Затем просто [де] сериализуйте List или Foo [] и т. Д. Через класс ProtoBuf.Serializer.

Я не утверждаю, что он будет вполне столь же эффективным с точки зрения пространства, как и ваш собственный, но это будет чертовски близко. Спецификация буфера протокола довольно хорошо использует пространство (например, при использовании base-128 для целых чисел, так что небольшие числа занимают меньше места). Но было бы просто попробовать, без необходимости писать весь код сериализации самостоятельно.

Этот подход, помимо простоты реализации, также имеет то преимущество, что прост в использовании из других архитектур, поскольку существуют реализации буферов протокола для различных языков . Он также использует гораздо меньше ресурсов ЦП, чем обычное сжатие [de] (GZip / DEFLATE / etc) и / или сериализация на основе XML.

Answer 6

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

1. Сортировка и реорганизация данных таким образом, чтобы похожие числа находились рядом друг с другом, т.е. е. сначала отсортируйте по id, а затем по отметке времени и измените порядок с (<int1>, <int2>, <double>), ... на ([<int1>, <int1> ...], [<int2>, <int2> ... ], [<double>, <double> ...]) (как предложено schnaader и Stephan Leclercq

2. Используйте дельта-кодирование на временных метках (и, возможно, на других значениях), как предложено schnaader и ididak

3. Использовать буферы протокола для сериализации (я все равно буду использовать их в приложении, поэтому не буду добавлять зависимости или что-либо еще). Спасибо Марку Гравеллу за указание на это.