Сжатие отсортированных данных с небольшой разницей

Я отсортировал последовательность данных целых чисел. Максимальная разница между двумя числами равна 3. Таким образом, данные выглядят, например, так:

Data: 1 2 3 5 7 8 9 10 13 14
Differences: (start 1) 1 1 2 2 1 1 1 3 1

Есть ли лучший способ сохранить (сжать) этот тип последовательностей, чем сохранить значения разницы? Потому что, если я использую методы на основе словаря, мне не удалось сжать из-за случайности чисел 1,2 и 3. Если я использую сжатие в стиле «PAQ», результат лучше, но все же не совсем удовлетворительный. Хаффман и арифметический кодер хуже, чем методы на основе словаря.

Есть ли способ с предсказанием?

Например, чтобы использовать регрессию для исходных данных и сохранять различия (которые могут быть меньше или более последовательными).

Или использовать какой-то прогноз, основанный на гистограмме различий?

Или что-то совершенно другое... или это вообще невозможно (что, на мой взгляд, является реальным ответом :))


compression sorted
person Martin Perry    schedule 14.02.2013    source источник
comment
Вы можете сохранить каждое число как расстояние от предыдущего числа (1-3), но сделать это как 2-битное число. Затем вы можете упаковать 4 числа в каждый байт. Недостатком этого является то, что для определения любого заданного числа в последовательности вам придется начинать с самого начала. Вы и сложите все расстояния.   -  person Pete    schedule 14.02.2013
comment
Да.. Я уже упаковал 4 числа в 1 байт. Мне было интересно, есть ли лучшее решение этой проблемы   -  person Martin Perry    schedule 14.02.2013
comment
Возможно, вы сможете высвободить неиспользуемую половину и получить немного больше места. Но если числовая последовательность действительно случайна, то вы вряд ли получите большую пользу от алгоритмов сжатия, поскольку они, как правило, основаны на идее какой-то повторяющейся последовательности, а случайным данным обычно этого не хватает.   -  person Pete    schedule 14.02.2013
comment
Я полагаю, настоящий вопрос заключается в том, действительно ли ваши данные случайны? Может быть, какое-то природное явление? Или, возможно, в нем можно обнаружить какую-то глубинную закономерность? Если шаблон не найден, сжимаемость отсутствует.   -  person Pete    schedule 14.02.2013
comment
Они в значительной степени случайны... но наиболее частым значением является 1 (примерно более 80% данных), чем 2 и 3. Нет видимой закономерности. Вот почему я подумал об использовании, например, нейронной сети, чтобы найти что-либо. Или, если на график нанесены исходные данные, они очень близки к линейной функции (после линейной регрессии в Excel надежность = 0,9998).   -  person Martin Perry    schedule 14.02.2013

Ответы (1)


arrow_upward
0
arrow_downward

Поскольку вы говорите в комментариях, что уже храните четыре различия на байт, вы, вероятно, не сделаете намного лучше. Если бы различия 0, 1, 2 и 3 были случайными и равномерно распределенными, то не было бы никакого способа сделать лучше.

Если они распределены неравномерно, возможно, вам удастся добиться большего успеха с помощью кода Хаффмана или арифметического кода. Например. если 1 встречается чаще, чем 0, что встречается чаще, чем 2 и 3, то вы можете сохранить 1 как 0, 0 как 10, 2 как 110 и 3 как 111. Или, если 0 никогда не встречается, 1 как 0, 2 и 3 как 10 и 11. Вы могли бы добиться большего успеха с арифметическим кодом для случая, который вы цитируете, где 1 встречается в 80% случаев. Или арифметический код бедняка, кодирующий пары символов. Например.:

11 0
13 100
21 101
12 110
31 1110
22 111100
23 111101
32 111110
33 111111

будет хорошим кодом для 1 80%, 2 10%, 3 10%. (Это не совсем подходит для случая нечетного числа различий, но вы можете справиться с этим, указав только бит в начале, указывающий на четное или нечетное число, и еще несколько битов в конце, если нечетное.)

Может быть лучший предиктор, чем предыдущее значение. Это будет функция n предыдущих значений вместо одного предыдущего значения. Однако это будет сильно зависеть от данных. Например, вы можете предположить, что текущее значение, скорее всего, попадет на линию, образованную двумя предыдущими значениями. Или что он падает на параболу, составленную тремя предыдущими значениями. Или какая-то другая функция, например. синусоиду с некоторой частотой, если данные настолько необъективны.

person Mark Adler    schedule 14.02.2013