Код переменной длины

В теории кодирования код переменной длины — это код , который отображает исходные символы в переменное количество битов . Эквивалентное понятие в информатике — битовая строка .

Коды переменной длины позволяют сжимать и распаковывать источники с нулевой ошибкой ( сжатие данных без потерь ) и при этом считывать их посимвольно. При правильной стратегии кодирования независимый и одинаково распределенный источник может быть сжат почти сколь угодно близко к его энтропии . В этом отличие от методов кодирования фиксированной длины, для которых сжатие данных возможно только для больших блоков данных, а любое сжатие, превышающее логарифм общего числа возможностей, имеет конечную (хотя, возможно, и сколь угодно малую) вероятность неудачи.

Некоторыми примерами хорошо известных стратегий кодирования переменной длины являются кодирование Хаффмана , кодирование Лемпеля-Зива , арифметическое кодирование и контекстно-адаптивное кодирование переменной длины .

Коды и их расширения

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

Используя термины теории формального языка , точное математическое определение выглядит следующим образом: Пусть $S$ и $T$ быть двумя конечными множествами, называемыми исходным и целевым алфавитами соответственно. Код $C:S\to T^{*}$ это полная функция ^[1] отображение каждого символа из $S$ к последовательности символов над $T$ и расширение $C$ к гомоморфизму $S^{*}$ в $T^{*}$ , который естественным образом отображает каждую последовательность исходных символов в последовательность целевых символов, называется его расширением .

Классы кодов переменной длины

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

Несингулярные коды

Код является несингулярным , если каждый исходный символ отображается в другую непустую битовую строку, т. е. отображение исходных символов в битовые строки является инъективным .

Например, отображение $M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}$ является не неединичным, поскольку и «a», и «b» соответствуют одной и той же битовой строке «0»; любое расширение этого отображения будет генерировать кодирование с потерями (без потерь). Такое сингулярное кодирование все еще может быть полезно, когда некоторая потеря информации приемлема (например, когда такой код используется при сжатии аудио или видео, где кодирование с потерями становится эквивалентным квантованию источника ).
Однако отображение $M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}$ несингулярен; его расширение будет генерировать кодирование без потерь, что будет полезно для общей передачи данных (но эта функция не всегда требуется). Обратите внимание, что несингулярный код не обязательно должен быть более компактным, чем исходный (и во многих приложениях полезен более крупный код, например, как способ обнаружения и/или восстановления после ошибок кодирования или передачи, или в приложения безопасности для защиты источника от необнаружимого вмешательства).

Уникально декодируемые коды

Код однозначно декодируем, если его расширение неособо . Вопрос о том, является ли данный код однозначно декодируемым, можно решить с помощью алгоритма Сардинаса-Паттерсона .

Отображение $M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}$ однозначно декодируется (это можно продемонстрировать, посмотрев на следующий набор после каждой целевой строки битов в карте, поскольку каждая строка битов завершается, как только мы видим нулевой бит, который не может следовать за каким-либо существующим кодом, чтобы создать более длинный действительный код в карту, но однозначно запускает новый код).
Рассмотрим еще раз код $M_{2}$ из предыдущего раздела. ^[1] Этот код не является однозначно декодируемым, поскольку строку 011101110011 можно интерпретировать как последовательность кодовых слов 01110 – 1110 – 011 , но также и как последовательность кодовых слов 011 – 1 – 011 – 10011 . дают два возможных декодирования этой закодированной строки Таким образом, cdb и baby . Однако такой код полезен, когда набор всех возможных исходных символов полностью известен и конечен или когда существуют ограничения (например, формальный синтаксис), определяющие приемлемость исходных элементов этого расширения. Такие ограничения позволяют декодировать исходное сообщение путем проверки того, какие из возможных исходных символов, сопоставленных с одним и тем же символом, действительны в соответствии с этими ограничениями.

Префиксные коды

Код является префиксным кодом , если ни одна целевая битовая строка в отображении не является префиксом целевой битовой строки другого исходного символа в том же отображении. Это означает, что символы могут быть декодированы мгновенно после получения всего их кодового слова. Другими часто используемыми названиями для этой концепции являются код без префиксов , мгновенный код или контекстно-свободный код .

Пример сопоставления $M_{3}$ в предыдущем абзаце не является префиксным кодом, поскольку после чтения битовой строки «0» мы не знаем, кодирует ли она исходный символ «a» или является ли это префиксом кодировок «b» или «c». "символы.
Пример префиксного кода показан ниже.

Символ	Кодовое слово
а	0
б	10
с	110
д	111

Пример кодирования и декодирования:

отец → 00100110111010 → |0|0|10|0|110|111|0|10| → отец

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

Другим частным случаем префиксных кодов являются коды LEB128 и коды переменной длины (VLQ), которые кодируют сколь угодно большие целые числа в виде последовательности октетов, т. е. каждое кодовое слово кратно 8 битам.

Преимущества

Преимущество кода переменной длины состоит в том, что маловероятным исходным символам могут быть назначены более длинные кодовые слова, а вероятным исходным символам могут быть назначены более короткие кодовые слова, что дает низкую ожидаемую длину кодового слова. В приведенном выше примере, если бы вероятности (a, b, c, d) были $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ , ожидаемое количество битов, используемых для представления исходного символа с использованием приведенного выше кода, будет:

1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}

.

Поскольку энтропия этого источника составляет 1,75 бита на символ, этот код максимально сжимает источник, чтобы его можно было восстановить с нулевой ошибкой.

См. также

Код Голомба
Крускал граф
Наборы команд переменной длины в вычислениях

Ссылки

^ Jump up to: ^а ^б Этот код основан на примере, найденном в Berstel et al. (2009), Пример 2.3.1, с. 63.

Дальнейшее чтение

Саломон, Дэвид (сентябрь 2007 г.). Коды переменной длины для сжатия данных (1-е изд.). Спрингер Верлаг . ISBN 978-1-84628-958-3 . (xii+191 стр.) Ошибка 1 Ошибка
Берстель, Жан; Перрен, Доминик; Ройтенауэр, Кристоф (2010). Коды и автоматы . Энциклопедия математики и ее приложений. Том. 129. Кембридж, Великобритания: Издательство Кембриджского университета . ISBN 978-0-521-88831-8 . Збл 1187.94001 . Проект доступен онлайн

[:0-1] Jump up to: ^а ^б Этот код основан на примере, найденном в Berstel et al. (2009), Пример 2.3.1, с. 63.

[1]