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

Код, который отображает информацию в переменное количество бит

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → аабакдаб

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

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

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

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

${\displaystyle 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 бита на символ, этот код сжимает источник настолько, насколько это возможно, чтобы его можно было восстановить с нулевой ошибкой.

Смотрите также

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

Ссылки

1. Этот код основан на примере, найденном в Berstel et al. (2009), Пример 2.3.1, стр. 63.

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

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