В сжатии данных универсальный код для целых чисел представляет собой префиксный код , который отображает положительные целые числа в двоичные кодовые слова с дополнительным свойством, что независимо от истинного распределения вероятностей для целых чисел, пока распределение является монотонным (т. е. p ( i ) ≥ p ( i + 1) для всех положительных i ), ожидаемые длины кодовых слов находятся в пределах постоянного множителя ожидаемых длин, которые назначил бы оптимальный код для этого распределения вероятностей. Универсальный код является асимптотически оптимальным, если отношение между фактической и оптимальной ожидаемой длиной ограничено функцией информационной энтропии кода, которая, помимо того, что ограничена, стремится к 1, когда энтропия стремится к бесконечности.
В общем, большинство префиксных кодов для целых чисел назначают более длинные кодовые слова большим целым числам. Такой код может использоваться для эффективной передачи сообщения, взятого из набора возможных сообщений, просто упорядочивая набор сообщений по убыванию вероятности, а затем отправляя индекс предполагаемого сообщения. Универсальные коды, как правило, не используются для точно известных распределений вероятностей, и ни один универсальный код не является оптимальным для любого распределения, используемого на практике.
Универсальный код не следует путать с универсальным кодированием источника, в котором метод сжатия данных не обязательно должен быть фиксированным префиксным кодом, а соотношение между фактической и оптимальной ожидаемой длиной должно приближаться к единице. Однако следует отметить, что асимптотически оптимальный универсальный код может использоваться на независимых одинаково распределенных источниках , используя все более крупные блоки , как метод универсального кодирования источника.
Вот некоторые универсальные коды для целых чисел; звездочка ( * ) обозначает код, который можно тривиально переформулировать в лексикографическом порядке , а двойной крестик ( ‡ ) обозначает код, который является асимптотически оптимальным:
Вот неуниверсальные:
Их неуниверсальность можно наблюдать, заметив, что если любой из них используется для кодирования распределения Гаусса–Кузьмина или распределения Дзета с параметром s=2, ожидаемая длина кодового слова бесконечна. Например, использование унарного кодирования на распределении Дзета дает ожидаемую длину
С другой стороны, использование универсального гамма-кодирования Элиаса для распределения Гаусса–Кузьмина приводит к ожидаемой длине кодового слова (около 3,51 бита), близкой к энтропии (около 3,43 бита)- Академия Google.
Кодирование Хаффмана и арифметическое кодирование (когда их можно использовать) обеспечивают по крайней мере такое же, а часто и лучшее сжатие, чем любой универсальный код.
Однако универсальные коды полезны, когда кодирование Хаффмана невозможно использовать — например, когда неизвестна точная вероятность каждого сообщения, а известны только рейтинги их вероятностей.
Универсальные коды также полезны, когда коды Хаффмана неудобны. Например, когда передатчик, но не получатель знают вероятности сообщений, кодирование Хаффмана требует накладных расходов на передачу этих вероятностей получателю. Использование универсального кода не имеет таких накладных расходов.
Каждый универсальный код, как и любой другой саморазграничивающий (префиксный) двоичный код, имеет свое собственное «подразумеваемое распределение вероятностей», заданное как P ( i )=2 − l ( i ), где l ( i ) — длина i -го кодового слова, а P ( i ) — вероятность соответствующего символа. Если фактические вероятности сообщений равны Q ( i ) и расхождение Кульбака–Лейблера минимизируется кодом с l ( i ) , то оптимальный код Хаффмана для этого набора сообщений будет эквивалентен этому коду. Аналогично, насколько близок код к оптимальному, можно измерить с помощью этого расхождения. Поскольку универсальные коды проще и быстрее кодировать и декодировать, чем коды Хаффмана (которые, в свою очередь, проще и быстрее арифметического кодирования ), универсальный код будет предпочтительнее в случаях, когда достаточно мало. Программа сжатия данных без потерь: гибридный LZ77 RLE
Для любого геометрического распределения (экспоненциального распределения целых чисел) код Голомба является оптимальным. С универсальными кодами неявное распределение приблизительно соответствует степенному закону, такому как (точнее, распределению Ципфа ). Для кода Фибоначчи неявное распределение приблизительно равно , с
где — золотое сечение . Для троичного кода с запятой (т.е. кодирования по основанию 3, представленного 2 битами на символ) неявное распределение — это степенной закон с . Таким образом, эти распределения имеют почти оптимальные коды с соответствующими степенными законами.
