Универсальный код: различия между версиями

Текущая версия от 00:47, 20 августа 2025

Универсальный код для целых чисел в сжатии данных — префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределении вероятностей на целых числах, пока распределение — монотонно (то есть $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$ — отношение золотого сечения.

СсылкиПравить

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

Ошибка Lua в Модуль:Navbox на строке 353: attempt to index local 'listText' (a nil value).

@@ Строка 1: / Строка 1: @@
-В сжатии данных, [[универсальный код]] для целых чисел это префиксный код, который переводит положительные целые числа в двоичный код с дополнительным свойством: любое истинное распределение вероятностей на целых числах, пока распространение монотонно (то есть ''p(i)>=p(i+1)'', для каждого положительного i), ожидаемые длины ключевых слов в пределах постоянного фактора ожидаемых длин, которые оптимальный код для этого распределения вероятностей назначил бы. Универсальный код асимптотически оптимален, если соотношение между фактическими и оптимальными ожидаемыми длинами связяно функцией информационной энтропии кода, что, в добавление к тому, чтобы быть связанным, приближается к 1, так как энтропия приближается к бесконечности.
+'''Универсальный код''' для целых чисел в [[Сжатие данных|сжатии данных]] — [[префиксный код]], который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном [[распределение вероятностей|распределении вероятностей]] на целых числах, пока распределение — монотонно (то есть <math>p(i) \geq p(i+1)</math> для любого <math>i</math>), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей.
-Вообще, большинство префиксных кодов для целых чисел назначают более длинные ключевые слова большим целым числам. Такой код может использоваться, чтобы эффективно закодировать сообщение, тянущееся из набора возможных сообщений, близко просто, упорядочивая набор сообщений по уменьшению вероятности а затем пересылая индекс предназначаемого сообщения. Универсальные коды в общем не используются для точно известных распределений вероятностей, и никакой универсальный код, известно, не оптимален, ибо любое распространение использовало на практике.
+Универсальный код асимптотически оптимален, если коэффициент между фактическими и оптимальными ожидаемыми длинами связывает функция информационной энтропии кода, которая приближается к 1, так как [[энтропия]] приближается к бесконечности.
-'''Универсальные коды''' включают в себя:
+Большинство префиксных кодов для целых чисел назначает более длинные ключевые слова большим целым числам. Такой код может использоваться, чтобы эффективно закодировать сообщение, тянущееся из набора возможных сообщений, просто упорядочивая набор сообщений по уменьшению вероятности а затем пересылая индекс предназначаемого сообщения. Универсальные коды в общем не используются для точно известных распределений вероятностей.
-* [[унарное кодирование]]
+Универсальные коды включают в себя:
-* [[гамма-кодирование Элиаса]]
+* [[Унарное кодирование]]
-* [[дельта-кодирование Элиаса]]
+* [[Гамма-код Элиаса]]
-* [[омега-кодирование Элиаса]]
+* [[Дельта-код Элиаса]]
-* [[дельта код]]
+* [[Омега-код Элиаса]]
-* [[кодирование Фибоначчи]]
+* [[Дельта-код]]
-* [[кодирование Голомба]]
+* [[Кодирование Фибоначчи]]
-* [[кодирование Райса]]
+* [[Экспоненциальный код Голомба]]
+Некоторые неуниверсальные коды:
-Байтовое кодирование ‡, также известно как кодирование запятой, где специальный двоичный код (как минимум с двумя кусками) используется, чтобы отметить конец кода — например, если целое число кодируется как последовательность откусываний, представляющих цифры в основе 15 вместо более естественной основы 16, то самое высокое значение (то есть, последовательность четыре те в наборе из двух предметов) откусывания может использоваться, чтобы указать конец целого числа.
+* [[одноместное кодирование]], используется в кодах Элиаса
+* [[Кодирование Райса]]
+* [[Кодирование Голомба]]
-Они не универсальны:
+Их неуниверсальность проявляется в том, что если любые из них использовать, чтобы закодировать [[распределение Гаусса-Кузьмина]] или [[дзета-распределение]] с параметром s=2, то ожидаемая длина ключевого слова бесконечена. Например, используя одноместное кодирование на дзета-распределение, имеем следующую ожидаемую длину:
-одноместное кодирование, которое используется в кодах Elias
-Рисовое кодирование, которое используется в FLAC звук codec, так как который имеет одноместное кодирование как особый правовой вопрос
-Golomb, закодировавший, который имеет Рис, закодировавший и одноместное кодирование как особые правовые вопросы.
-Их неуниверсальность может наблюдать обращение внимания на это, если любые из них используются, чтобы закодировать распространение Gauss-Kuzmin или распространение Дзэты с параметр s=2, ожидал длину ключевого слова бесконечен. Например, используя одноместное кодирование на распространении Дзэты приводит ожидаемую длину
+<math>E(l) = \frac{6}{\pi^2} \sum_{l=1}^\infty \frac{1}{l} = \infty .</math>
+== Практическое использование в сжатии данных ==
+Использование [[код Хаффмана|кода Хаффмана]] и [[арифметическое кодирование|арифметического кодирования]] (когда они могут использоваться вместе) даёт лучший результат, чем любой другой универсальный код.
+Однако, универсальные коды полезны, когда код Хаффмана не может использоваться — например, когда невозможно определить точную вероятность каждого сообщения, но известно ранжирование их вероятностей.
-С другой стороны, используя универсальную гамму Elias, закодировавшую для Gauss-Kuzmin результатов распространения в ожидаемой длине (около 3.51 кусков) ключевого слова возле энтропии (около 3.43 кусков)[2].
+Универсальные коды также полезны, когда код Хаффмана отрабатывает не совсем корректно. Например, когда отправитель знает вероятности сообщений, а получатель — нет, код Хаффмана требует передачи вероятностей к получателю. Использование универсального кода избавляет от таких неудобств.
-Универсальный код не нужно смешивать с универсальным исходным кодированием, в котором методу сжатия данных не нужно быть исправленным префиксным кодом, и соотношение между фактическими и оптимальными ожидаемыми длинами должно приблизиться к одному. Однако, отмечают, что асимптотически оптимальный универсальный код может использоваться на независимом политическом деятеле одинаково распространяемые источники, используя все более и более большие блоки, как метод универсального исходного кодирования.
+Каждый универсальный код дает собственное «подразумеваемое распределение» вероятностей <math>p(i) = 2^{-l(i)}</math>, где <math>l(i)</math> — длина i-го ключевого слова и <math>p(i)</math> — вероятность символа передачи. Если фактические вероятности сообщения — <math>q(i)</math> и [[расстояние Кульбака — Лейблера]] <math>DKL(q||p)</math> минимизирует код с <math>l(i)</math>, оптимальный код Хаффмана для этого множества сообщений будет эквивалентен к этому коду. Поскольку универсальные коды быстрее, чем код Хаффмана, универсальный код предпочтителен в случаях, где <math>DKL(q||p)</math> достаточно мало.
-[редактирование]
+Для любого [[геометрическое распределение|геометрического распределения]] [[кодирование Голомба]] оптимально. Для универсальных кодов подразумеваемое распределение приблизительно подчиняется [[Степенной закон|степенному закону]], например <math>1/n^2</math>, а точнее, [[Закон Ципфа|закону Ципфа]]. Для [[код Фибоначчи|кода Фибоначчи]] подразумеваемое распределение приблизительно подчиняется закону <math>1/n^q</math> при <math>q = 1/\log_2(\varphi) \approx 1{,}44</math>, где <math>\varphi</math> — отношение [[Золотое сечение|золотого сечения]].
-Взаимоотношение к практической компрессии
-Кодирование Huffman и арифметическое шифрование (когда они могут использоваться) предоставляют как минимум, как хорошо, и часто лучшая компрессия, чем любой универсальный код.
-Однако, универсальные коды полезны, когда Huffman, закодировавший, не может использоваться — например, когда один не знает точную вероятность каждого сообщения, но только знает ранжирования их вероятностей.
-Универсальные коды также полезны, когда коды Huffman неудобны. Например, когда отправитель но не приемник знает вероятности сообщений, Huffman, закодировавший, требует наверху передачи тех вероятностей к приемнику. Использование универсального кода не имеет этих накладных расходов.
-Каждый универсальный код, друг подобно другу, однородный-отграничивая (приставка) двоичный код, предоставил его собственное «подразумеваемое распределение» вероятностей p(i) =2-l(i), где l(i) — длина ith ключевого слова и p(i) — вероятность символа передачи. Если фактические вероятности сообщения — q(i) и Kullback-Leibler расхождение DKL(q||p) минимизирует код с l(i), то оптимальный код Huffman для этого набора сообщений будет эквивалентен к этому коду. Также, как закрывают код подходит оптимальному может быть взвешен этим расхождением. С тех пор, как универсальные коды проще и быстрее, чтобы кодировать и расшифровывать, чем коды (который есть, в свою очередь, проще и быстрее, чем арифметическое шифрование) Huffman, универсальный код был бы предпочтителен в случаях, где DKL(q||p) достаточно маленький. [3]
-Для любого геометрического распространения (экспоненциальное распространение на целых числах), код Golomb оптимален. С универсальными кодами, неявное распространение — приблизительно энергетический закон как например 1 / n2 (точнее, распространение Zipf). Для кода Fibonacci, неявное распространение составляет приблизительно 1 / nq, с
-где — золотое соотношение. Для тройного кода (то есть, кодируя в основе 3, представил с 2 кусками за символ) запятой, неявное распространение — энергетический закон . Эти распространения поэтому имеют near-optimal коды с их соответствующими энергетическими законами.
-Фигуры ниже Elias Гаммы сравнения, Дельты Elias, Fibonacci, и различные Рисовые кодирования для кусков использовали, чтобы кодировать целые значения. Базовый, «прямой, набор» из двух предметов, для двоичного шифрования, где размер уже известен также включается.
-'''Универсальные коды''' включают в себя:
-* [[унарное кодирование]]
-* [[гамма-кодирование Элиаса]]
-* [[дельта-кодирование Элиаса]]
-* [[омега-кодирование Элиаса]]
-* [[дельта код]]
-* [[кодирование Фибоначчи]]
-* [[кодирование Голомба]]
-* [[кодирование Райса]]
 == Ссылки ==
-* [http://www-lat.compression.ru/download/integers.html Кодирование целых чисел]
+* [https://web.archive.org/web/20070214150309/http://www-lat.compression.ru/download/integers.html Кодирование целых чисел]
 {{методы сжатия}}
 [[Категория:Алгоритмы сжатия без потерь]]
-[[en:Universal code (data compression)]]
-[[ko:범용 부호]]