Код переменной длины - Variable-length code

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

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

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

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

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

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

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

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

Неособые коды

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

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

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

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

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

Коды префикса

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

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

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

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

aabacdab → 00100110111010 → | 0 | 0 | 10 | 0 | 110 | 111 | 0 | 10 | → aabacdab

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

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

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

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

{displaystyle 1 imes {frac {1} {2}} + 2 imes {frac {1} {4}} + 3 imes {frac {1} {8}} + 3 imes {frac {1} {8}} = {гидроразрыв {7} {4}}}

.

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

Примечания

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