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

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

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

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

Универсальные коды включают в себя:

• Унарное кодирование
• Гамма-код Элиаса
• Дельта-код Элиаса
• Омега-код Элиаса
• Дельта-код
• Кодирование Фибоначчи
• Экспоненциальный код Голомба

Некоторые неуниверсальные коды:

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

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

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

Практическое использование в сжатии данных

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

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

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

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

Для любого геометрического распределения кодирование Голомба оптимально. Для универсальных кодов подразумеваемое распределение приблизительно подчиняется степенному закону, например $1/n^2$, а точнее, закону Ципфа. Для кода Фибоначчи подразумеваемое распределение приблизительно подчиняется закону $1/n^q$ при $q = 1/\log_2(\varphi) \approx 1{,}44$, где $\varphi$ — отношение золотого сечения.

Ссылки

• Кодирование целых чисел