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

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

Рассмотрим четыре символа  и . Если они появляются в последовательности данных с равной вероятностью ( каждая), то мы им просто присвоим четыре двухбитовых кода 00, 01, 10 и 11. Все вероятности равны, и поэтому коды переменной длины не сожмут эти данные. Для каждого символа с коротким кодом найдется символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных с равновероятными символами равна нулю, и строку таких символов невозможно сжать с помощью кодов переменной длины (или любым иным методом).

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

Символ	Вероятность	Code1	Code2
	0.49	1	1
	0.25	01	01
	0.25	010	000
	0.01	001	001

Табл. 1.2. Коды переменной длины.

В табл. 1.2 предложен код Code1, который присваивает самому часто встречающемуся символу самый короткий код. Если закодировать данный с помощью Code1, то среднее число бит на символ будет равно . Это число весьма близко к теоретическому минимуму. Рассмотрим последовательность из 20 символов

,

в которой четыре символа появляются, примерно, с указанными частотами. Этой строке будет соответствовать кодовая строка кода Code1 длины 37 бит

,

которая для удобства разделена черточками. Нам понадобилось 37 битов, чтобы закодировать 20 символов, то есть, в среднем 1.85 бит/символ, что не слишком далеко от вычисленной выше средней величины. (Читатель должен иметь в виду, что эта строка весьма коротка, и для того чтобы получить результат, близкий к теоретическому, необходимо взять входной файл размером несколько тысяч символов).

Однако, если мы теперь попробуем декодировать эту двоичную последовательность, то немедленно обнаружим, что Code1 совершенно не годен. Первый бит последовательности равен 1, поэтому первым символом может быть только , так как никакой другой код в таблице для Code1 не начинается с 1. Следующий бит равен 0, но коды для  и  все начинаются с 0, поэтому декодер должен читать следующий бит. Он равен 1, однако коды для  и  оба имеют в начале 01. Декодер не знает, как ему поступить. То ли декодировать строку как , то есть, , то ли как , то есть . Причем заметим, что дальнейшие биты последовательности уже не помогут исправить положение. Код Code1 является двусмысленным. В отличие от него, код Code2 из табл. 1.2 дает при декодировании всегда однозначный результат.

Code2 имеет одно важное свойство, которое делает его лучше, чем Code1, которое называется свойством префикса. Это свойство можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код другого символа не должен иметь в начале эту последовательность (не может быть префиксом, то есть, приставкой). Раз строка «1» уже выбрана в качестве целого кода для , то ни один другой код не может начинаться с 1 (то есть, они все должны начинаться на 0). Раз строка «01» является кодом для , то другие коды не должны начинаться с 01. Вот почему коды для  и  должны начинаться с 00. Естественно, они будут «000» и «001».

Значит, выбирая множество кодов переменной длины, необходимо соблюдать два принципа: (1) следует назначать более короткие коды чаще встречающимся символам, и (2) коды должны удовлетворять свойству префикса. Следуя эти принципам, можно построить короткие, однозначно декодируемые коды, но не обязательно наилучшие (то есть, самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (которые в среднем имеют наименьшую длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. К счастью, такой простой алгоритм существует. Он был придуман Давидом Хаффманом и называется его именем. Этот алгоритм будет описан в § 1.4.

Следует отметить, что не только статистические методы компрессии используют коды переменной длины при кодировании индивидуальных символов. Замечательным примером служат арифметические коды, о которых будет рассказано в § 1.7.