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

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

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

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

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

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

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

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

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

<math>E(l) = \frac{6}{\pi^2} \sum_{l=1}^\infty \frac{1}{l} = \infty .</math>

Взаимосвязь и практическое использование

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

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

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

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

Для любого геометрического распределения кодирование Голомба оптимально. С универсальными кодами, подразумеваемое распределение — приблизительно энергетический закон как например 1 / n2. Для кода Фибоначчи, подразумеваемое распределение составляет приблизительно 1 / nq.

Ссылки

• [www-lat.compression.ru/download/integers.html Кодирование целых чисел]

Отрывок, характеризующий Универсальный код

Все, очевидно, несомненно знали, что они были преступники, которым надо было скорее скрыть следы своего преступления.
Пьер заглянул в яму и увидел, что фабричный лежал там коленами кверху, близко к голове, одно плечо выше другого. И это плечо судорожно, равномерно опускалось и поднималось. Но уже лопатины земли сыпались на все тело. Один из солдат сердито, злобно и болезненно крикнул на Пьера, чтобы он вернулся. Но Пьер не понял его и стоял у столба, и никто не отгонял его.
Когда уже яма была вся засыпана, послышалась команда. Пьера отвели на его место, и французские войска, стоявшие фронтами по обеим сторонам столба, сделали полуоборот и стали проходить мерным шагом мимо столба. Двадцать четыре человека стрелков с разряженными ружьями, стоявшие в середине круга, примыкали бегом к своим местам, в то время как роты проходили мимо них.
Пьер смотрел теперь бессмысленными глазами на этих стрелков, которые попарно выбегали из круга. Все, кроме одного, присоединились к ротам. Молодой солдат с мертво бледным лицом, в кивере, свалившемся назад, спустив ружье, все еще стоял против ямы на том месте, с которого он стрелял. Он, как пьяный, шатался, делая то вперед, то назад несколько шагов, чтобы поддержать свое падающее тело. Старый солдат, унтер офицер, выбежал из рядов и, схватив за плечо молодого солдата, втащил его в роту. Толпа русских и французов стала расходиться. Все шли молча, с опущенными головами.
– Ca leur apprendra a incendier, [Это их научит поджигать.] – сказал кто то из французов. Пьер оглянулся на говорившего и увидал, что это был солдат, который хотел утешиться чем нибудь в том, что было сделано, но не мог. Не договорив начатого, он махнул рукою и пошел прочь.


После казни Пьера отделили от других подсудимых и оставили одного в небольшой, разоренной и загаженной церкви.
Перед вечером караульный унтер офицер с двумя солдатами вошел в церковь и объявил Пьеру, что он прощен и поступает теперь в бараки военнопленных. Не понимая того, что ему говорили, Пьер встал и пошел с солдатами. Его привели к построенным вверху поля из обгорелых досок, бревен и тесу балаганам и ввели в один из них. В темноте человек двадцать различных людей окружили Пьера. Пьер смотрел на них, не понимая, кто такие эти люди, зачем они и чего хотят от него. Он слышал слова, которые ему говорили, но не делал из них никакого вывода и приложения: не понимал их значения. Он сам отвечал на то, что у него спрашивали, но не соображал того, кто слушает его и как поймут его ответы. Он смотрел на лица и фигуры, и все они казались ему одинаково бессмысленны.
С той минуты, как Пьер увидал это страшное убийство, совершенное людьми, не хотевшими этого делать, в душе его как будто вдруг выдернута была та пружина, на которой все держалось и представлялось живым, и все завалилось в кучу бессмысленного сора. В нем, хотя он и не отдавал себе отчета, уничтожилась вера и в благоустройство мира, и в человеческую, и в свою душу, и в бога. Это состояние было испытываемо Пьером прежде, но никогда с такою силой, как теперь. Прежде, когда на Пьера находили такого рода сомнения, – сомнения эти имели источником собственную вину. И в самой глубине души Пьер тогда чувствовал, что от того отчаяния и тех сомнений было спасение в самом себе. Но теперь он чувствовал, что не его вина была причиной того, что мир завалился в его глазах и остались одни бессмысленные развалины. Он чувствовал, что возвратиться к вере в жизнь – не в его власти.