Изменения

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

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

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

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

*[[Кодирование Голомба]]

*[[Кодирование Голомба]]

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

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

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

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

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

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

== Ссылки ==

== Ссылки ==