Универсальный код (сжатие данных)

Фибоначчи, Элиас Гамма и Элиас Дельта против двоичного кодирования

Рис с k = 2, 3, 4, 5, 8, 16 по сравнению с двоичным

При сжатии данных универсальный код для целых чисел представляет собой префиксный код , который отображает положительные целые числа на двоичные кодовые слова, с дополнительным свойством, заключающимся в том, что независимо от истинного распределения вероятностей целых чисел, пока распределение является монотонным (т. е. p ( i ) ≥ p ( i + 1) для всех положительных i ), ожидаемые длины кодовых слов находятся в пределах постоянного коэффициента ожидаемых длин, которые оптимальный код мог бы назначить для этого распределения вероятностей. Универсальный код является асимптотически оптимальным, если соотношение между фактической и оптимальной ожидаемой длиной ограничено функцией информационной энтропии кода, которая не только ограничена, но и приближается к 1, когда энтропия стремится к бесконечности.

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

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

Универсальные и неуниверсальные коды

Это некоторые универсальные коды для целых чисел; звездочка ( * ) указывает на код, который можно тривиально переформулировать в лексикографическом порядке , а двойной крестик ( ‡ ) указывает на код, который является асимптотически оптимальным:

• Гамма-кодирование Элиаса *
• Дельта-кодирование Элиаса * ‡
• Омега-кодирование Элиаса * ‡
• Кодирование Экспер-Голомба *, в котором гамма-кодирование Элиаса является особым случаем. (Используется в H.264/MPEG-4 AVC )
• Кодирование Фибоначчи
• Кодирование Левенштейна * ‡, оригинальный универсальный метод кодирования [1]
• Байтовое кодирование , при котором специальный битовый шаблон (по крайней мере, с двумя битами) используется для обозначения конца кода — например, если целое число кодируется как последовательность полубайтов, представляющих цифры по основанию 15 вместо более естественного основания 16 , тогда наибольшее значение полубайта (т. е. последовательность из четырех единиц в двоичном формате) можно использовать для обозначения конца целого числа.
• Количество переменной длины

Это неуниверсальные:

• Унарное кодирование , которое используется в кодах Элиаса.
• Кодирование Райса , которое используется в FLAC аудиокодеке и имеет унарное кодирование как особый случай.
• Кодирование Голомба , в котором в качестве особых случаев используются кодирование Райса и унарное кодирование.

Их неуниверсальность можно наблюдать, заметив, что, если какой-либо из них используется для кодирования распределения Гаусса – Кузьмина или распределения Дзета с параметром s = 2, ожидаемая длина кодового слова будет бесконечной. Например, использование унарного кодирования для распределения Зета дает ожидаемую длину

$E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty .\,$

С другой стороны, использование универсального гамма-кодирования Элиаса для распределения Гаусса-Кузьмина приводит к ожидаемой длине кодового слова (около 3,51 бита) близкой к энтропии (около 3,43 бита) - Академия Google .

практическим

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

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

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

Каждый универсальный код, как и любой другой саморазграничивающийся (префиксный) двоичный код, имеет свое собственное «предполагаемое распределение вероятностей», определяемое P ( i ) = 2. ^{- л ( я )} где l ( i ) — длина i- го кодового слова, а P ( i ) — вероятность соответствующего символа. Если фактические вероятности сообщения равны Q ( i ) и расхождению Кульбака – Лейблера $D_{\text{KL}}(Q\|P)$минимизируется кодом с l ( i ) , то оптимальный код Хаффмана для этого набора сообщений будет эквивалентен этому коду. Аналогично, по этому расхождению можно измерить, насколько код близок к оптимальному. Поскольку универсальные коды проще и быстрее кодировать и декодировать, чем коды Хаффмана (что, в свою очередь, проще и быстрее, чем арифметическое кодирование ), универсальный код был бы предпочтительнее в тех случаях, когда $D_{\text{KL}}(Q\|P)$достаточно мал. Программа сжатия данных без потерь: Hybrid LZ77 RLE

Для любого геометрического распределения (экспоненциального распределения целых чисел) код Голомба является оптимальным. В случае универсальных кодов неявное распределение представляет собой примерно степенной закон , такой как $1/n^{2}$(точнее, распределение Ципфа ). Для кода Фибоначчи неявное распределение приблизительно равно $1/n^{q}$, с

$q=1/\log _{2}(\varphi )\simeq 1.44,$

где $\varphi$это золотое сечение . Для троичного кода с запятой (т. е. кодирования по основанию 3, представленного двумя битами на символ), неявное распределение представляет собой степенной закон с $q=1+\log _{3}(4/3)\simeq 1.26$. Таким образом, эти распределения имеют почти оптимальные коды с соответствующими степенными законами.

Внешние ссылки

• Сжатие данных , Дебра А. Лелевер и Дэниел С. Хиршберг ( Калифорнийский университет, Ирвайн )
• «Теория информации, вывод и алгоритмы обучения » Дэвида Маккея содержит главу, посвященную кодам для целых чисел, включая введение в коды Элиаса.
• Кодирование целых чисел has mostly English-language papers on universal and other integer codes.