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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  Сжатие данных «Универсальный код»  -  новости  · газеты  · книги  · ученый  · JSTOR ( ноябрь 2011 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

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

Универсальные и неуниверсальные коды [ править ]

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

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

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

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

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

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

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

Отношение к практическому сжатию [ править ]

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

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

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

Каждый универсальный код, как и каждый другой саморазграничивающий (префиксный) двоичный код, имеет собственное «подразумеваемое распределение вероятностей», задаваемое формулой p ( i ) = 2 ^{- l ( i ),} где l ( i ) - длина i- го кодового слова. а p ( i ) - вероятность соответствующего символа. Если фактические вероятности сообщения равны q ( i ) и расхождение Кульбака – Лейблера D _KL ( q || p ) минимизируется кодом с l ( i), то оптимальный код Хаффмана для этого набора сообщений будет эквивалентен этому коду. Точно так же, насколько код близок к оптимальному, можно измерить по этому расхождению. Поскольку универсальные коды проще и быстрее кодировать и декодировать, чем коды Хаффмана (что, в свою очередь, проще и быстрее, чем арифметическое кодирование ), универсальный код будет предпочтительнее в случаях, когда D _KL ( q || p ) достаточно мало. [3]

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

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

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

Внешние ссылки [ править ]

• Сжатие данных , Дебра А. Лелевер и Дэниел С. Хиршберг ( Калифорнийский университет, Ирвин )
• Теория информации, Умозаключение и алгоритмы обучения ,помощью Дэвида Маккея , имеют главу о кодах для целых чисел,том числе введения в коды Элиаса.
• Кодирование целых чисел содержит в основном англоязычные статьи по универсальным и другим целочисленным кодам.