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

Question

Я отсортировал последовательность данных целых чисел. Максимальная разница между 2 числами 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», результат будет лучше, но все же не совсем удовлетворительным. Хаффман и арифметический кодер хуже, чем словарные методы.

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

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

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

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

Answer 1

Так вы говорите, в комментариях, что вы уже хранящих четыре различия за байт, вы, вероятно, не будете делать намного лучше. Если разности 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 предыдущих значений вместо одного предыдущего значения. Однако это будет сильно зависящим от данных. Например, вы можете предположить, что текущее значение, вероятно, упадет на строку, сделанную предыдущими двумя значениями. Или что он падает на параболу, сделанную предыдущими тремя значениями. Или какая-либо другая функция, например. синусоида с некоторой частотой, если данные настолько предвзяты.