| Строка 1: |
Строка 1: |
| − | В сжатии данных, [[универсальный код]] для целых чисел это префиксный код, который переводит положительные целые числа в двоичный код с дополнительным свойством: любое истинное распределение вероятностей на целых числах, пока распространение монотонно (то есть ''p(i)>=p(i+1)'', для каждого положительного i), ожидаемые длины ключевых слов в пределах постоянного фактора ожидаемых длин, которые оптимальный код для этого распределения вероятностей назначил бы. Универсальный код асимптотически оптимален, если соотношение между фактическими и оптимальными ожидаемыми длинами связяно функцией информационной энтропии кода, что, в добавление к тому, чтобы быть связанным, приближается к 1, так как энтропия приближается к бесконечности.
| |
| − |
| |
| − | Вообще, большинство префиксных кодов для целых чисел назначают более длинные ключевые слова большим целым числам. Такой код может использоваться, чтобы эффективно закодировать сообщение, тянущееся из набора возможных сообщений, близко просто, упорядочивая набор сообщений по уменьшению вероятности а затем пересылая индекс предназначаемого сообщения. Универсальные коды в общем не используются для точно известных распределений вероятностей, и никакой универсальный код, известно, не оптимален, ибо любое распространение использовало на практике.
| |
| − |
| |
| − | '''Универсальные коды''' включают в себя:
| |
| − |
| |
| − | * [[унарное кодирование]]
| |
| − | * [[гамма-кодирование Элиаса]]
| |
| − | * [[дельта-кодирование Элиаса]]
| |
| − | * [[омега-кодирование Элиаса]]
| |
| − | * [[дельта код]]
| |
| − | * [[кодирование Фибоначчи]]
| |
| − | * [[кодирование Голомба]]
| |
| − | * [[кодирование Райса]]
| |
| − |
| |
| − |
| |
| − | Байтовое кодирование ‡, также известно как кодирование запятой, где специальный двоичный код (как минимум с двумя кусками) используется, чтобы отметить конец кода — например, если целое число кодируется как последовательность откусываний, представляющих цифры в основе 15 вместо более естественной основы 16, то самое высокое значение (то есть, последовательность четыре те в наборе из двух предметов) откусывания может использоваться, чтобы указать конец целого числа.
| |
| − |
| |
| − | Они не универсальны:
| |
| − | одноместное кодирование, которое используется в кодах Elias
| |
| − | Рисовое кодирование, которое используется в FLAC звук codec, так как который имеет одноместное кодирование как особый правовой вопрос
| |
| − | Golomb, закодировавший, который имеет Рис, закодировавший и одноместное кодирование как особые правовые вопросы.
| |
| − |
| |
| − | Их неуниверсальность может наблюдать обращение внимания на это, если любые из них используются, чтобы закодировать распространение Gauss-Kuzmin или распространение Дзэты с параметр s=2, ожидал длину ключевого слова бесконечен. Например, используя одноместное кодирование на распространении Дзэты приводит ожидаемую длину
| |
| − |
| |
| − |
| |
| − |
| |
| − | С другой стороны, используя универсальную гамму Elias, закодировавшую для Gauss-Kuzmin результатов распространения в ожидаемой длине (около 3.51 кусков) ключевого слова возле энтропии (около 3.43 кусков)[2].
| |
| − |
| |
| − | Универсальный код не нужно смешивать с универсальным исходным кодированием, в котором методу сжатия данных не нужно быть исправленным префиксным кодом, и соотношение между фактическими и оптимальными ожидаемыми длинами должно приблизиться к одному. Однако, отмечают, что асимптотически оптимальный универсальный код может использоваться на независимом политическом деятеле одинаково распространяемые источники, используя все более и более большие блоки, как метод универсального исходного кодирования.
| |
| − |
| |
| − | [редактирование]
| |
| − | Взаимоотношение к практической компрессии
| |
| − |
| |
| − | Кодирование 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, и различные Рисовые кодирования для кусков использовали, чтобы кодировать целые значения. Базовый, «прямой, набор» из двух предметов, для двоичного шифрования, где размер уже известен также включается.
| |
| − |
| |
| − |
| |
| | '''Универсальные коды''' включают в себя: | | '''Универсальные коды''' включают в себя: |
| | | | |