Хорошая схема сжатия для продолжения сроков?
Таким образом, я реализую библиотеку непрерывных дробей для обработки подмножества квадратичных целых и рациональных чисел. Продолженные члены дроби представлены целыми числами без знака. Я заметил следующие общие закономерности при работе с непрерывными дробями:
- Большинство терминов представляют собой небольшие однозначные числа, причем 1 является наиболее распространенным.
- Некоторые термины могут быть огромными, наибольшее возможное для моего приложения - 366 бит, но они встречаются крайне редко.
- Большой термин представляет собой особенно хорошее приближение числа, что означает, что обычно для большого числа обычно меньше терминов.
- Худшая возможная непрерывная дробь - это золотое сечение, а рациональное приближение с 366 битами точности соответствует примерно 525 единицам подряд.
- Случайные рациональные числа, как правило, не имеют больших серий одного и того же числа, но могут иметь от двух до четырех подряд, причем 1 снова является наиболее распространенным.
Таким образом, у меня есть ограничение как на количество терминов, так и на размер термина, причем число терминов примерно обратно пропорционально их размеру. Поэтому хранение этих терминов в машинных словах или даже байтах обычно занимает очень много места, и в худшем случае мне все же нужно обрабатывать многословную арифметику. Учитывая примерно обратную зависимость между размером терминов и количеством терминов (которые также зависят от размера числителя и знаменателя дроби), я пытался найти или придумать хорошую схему сжатия, чтобы не тратить впустую так много места для хранения целочисленных терминов.
Я рассмотрел кодирование Хаффмана, поскольку скорость кодирования и декодирования хороша, но я не уверен, как определить вероятности значений кода. У меня есть смутная интуиция, что Деревья Штерна-Броко могут предложить подсказку, поскольку они являются двоичными деревьями, имеющими прямую связь с непрерывными дробями.
Кто-нибудь знает о хорошем подходе к сжатию для обработки большого количества небольших чисел, в которых иногда встречаются огромные числа, в которых прогоны с одинаковым числом обычно короткие (но в редких случаях могут быть длинными)? В частности, мне нужно иметь возможность кодировать и декодировать довольно быстро (скажем, O(n*lg(n)) - это абсолютная наихудшая скорость, которую я могу терпеть, с O(n) или лучше предпочтительным), и быть в состоянии достичь положение отдельных терминов, чтобы я знал, над каким номером термина я оперирую (четвертый, пятый и т. д.).
Кроме того, я не заинтересован в использовании сторонних библиотек вещественных чисел или цепей дробных чисел. Я посмотрел на несколько из них, и они либо недостаточны, либо излишни для моих нужд, и мне бы хотелось, чтобы я сам их кодировал для своего назидания.
Обновить
Я также узнал о распределении Гаусса – Кузьмина, которое дает распределение вероятностей конкретного продолженного дробного члена k для случайного числа, равномерно распределенного между 0 и 1.
P(k) = -lg(1.0 - 1.0/((k + 1.0)**2) в псевдокоде Python, где lg - логарифм с основанием 2. Это предел как k приближается к бесконечности, поэтому мой случай несколько более ограничен (хотя 2**366 все еще огромный). " Энтропия непрерывных дробей" Линаса Вепста дает (информационную) энтропию распределения Гаусса-Кузьмина примерно в 3,43 бита. Мой максимальный знаменатель настолько велик, что информационная энтропия моих продолженных дробей, вероятно, близка к этому пределу, хотя график в связанной статье показывает, что предел приближается довольно медленно и поэтому отличается для относительно небольших знаменателей.
5 ответов
Одной из возможностей является простой префиксный код, где двоичное число 1x имеет биты x, закодированные как 0 -> 10 и 1 -> 11, за которыми следует терминатор 0.
Таблица:
1 -> 0
2 -> 100
3 -> 110
4 -> 10100
5 -> 10110
6 -> 11100
7 -> 11110
8 -> 1010100
Соответствующие вероятности кода Хаффмана здесь для n являются чем-то вроде тэты (1/n^2) (немного машет руками, потому что алфавит бесконечен).
Ваш дистрибутив, кажется, поддается Rice Coding. Вы можете настроить параметр кодирования, давайте назовем его k, для ваших данных. Кодирование берет биты числа выше младших k битов и передает столько же 1 битов, а затем 0. Затем вы передаете младшие k битов напрямую.
Вы могли бы рассмотреть возможность отбрасывания цепных дробей и использовать вместо них своего мутировавшего двоюродного брата: продолженные логарифмы Смотрите в самой нижней части этого документа для обсуждения и реализации базовой арифметики.
Есть даже аппаратная реализация для чрезвычайно параллельной арифметики на продолженных логарифмах, с такой же асимптотической сложностью, что и FFT, но гораздо более простая и, следовательно, намного более низкие константы.
Если вы ищете что-то более экзотическое, чем то, что может быть построено только с помощью обратимых операторов {+,-,*,/}, см. Мой новый вопрос об операторе пола.
Как вы видели, непрерывные дроби имеют тенденцию увеличиваться в размерном значении бит для очень больших целых или очень маленьких дробей. Это колебание гигантских терминов с маленькими терминами - это то, что вам нужно использовать в любой схеме сжатия.
С другой стороны, непрерывные логарифмы разделяют большие термины в своего рода "рекурсивной научной нотации", как Билл Госпер добавляет в эту статью. Каждый термин сопрограмма испускает или потребляет только очень маленькие сообщения, которые могут быть сформированы в естественном виде закодированной сериализации длины серии, описывающей "основание журнала 2 из числа, которое осталось описать".
К сожалению, побочным эффектом использования этих продолженных логарифмов является то, что числа Гурвица не имеют шаблонов, а в непрерывных дробях очень регулярны. Однако большинство, но не все, квадратичные разряды остаются периодическими, что также можно рассматривать как схему сжатия.
Оказавшись в компактном формате кодированных длин серий, вы можете использовать традиционные методы сжатия для серий небольших чисел, такие как LZW, описанные в комментариях вопроса Марком Рэнсомом.
Вы можете использовать арифметическое кодирование, рассматривая каждое положительное целое число как символ в исходном алфавите. Неважно, что их бесконечно много, так как относительная вероятность больших и больших целых чисел падает до нуля.
Фактически, учитывая равномерное распределение на [0,1), вы можете установить условную вероятность каждого нового целого числа a_n в продолжении дробного дробления (т.е. каждого нового символа из источника энтропии) равной P(a_n = k) = 1/k - 1/(k+1). Вы можете рассмотреть первое целое число, чтобы понять, почему эта условная вероятность имеет смысл (половина чисел в интервале [0,1) будет иметь a_1 = 1, для одной шестой из них a_1 = 2 и т. Д.).
Кроме того, вам может потребоваться изменить направление арифметического кодирования с каждым новым символом, чтобы декодирование было однозначным. К сожалению, арифметическое en/decoding не очень быстрое.
Другая возможность - использовать какую-то схему "Универсального кодирования". Поскольку случайно выбранные непрерывные дроби редко имеют действительно большие частные отношения, универсальное кодирование должно быть полезным.