1.2. Коды переменной длиныПервое правило построения кодов с переменной длиной вполне очевидно. Короткие коды следует присваивать часто встречающимся символам, а длинные редко встречающимся. Однако есть другая проблема. Эти коды надо назначать так, чтобы их было возможно декодировать однозначно, а не двусмысленно. Маленький пример прояснит это. Рассмотрим четыре символа Предположим теперь, что эти четыре символа появляются с разными вероятностями, указанными в табл. 1.2, то есть
Табл. 1.2. Коды переменной длины. В табл. 1.2 предложен код Code1, который присваивает самому часто встречающемуся символу самый короткий код. Если закодировать данный с помощью Code1, то среднее число бит на символ будет равно
в которой четыре символа появляются, примерно, с указанными частотами. Этой строке будет соответствовать кодовая строка кода Code1 длины 37 бит
которая для удобства разделена черточками. Нам понадобилось 37 битов, чтобы закодировать 20 символов, то есть, в среднем 1.85 бит/символ, что не слишком далеко от вычисленной выше средней величины. (Читатель должен иметь в виду, что эта строка весьма коротка, и для того чтобы получить результат, близкий к теоретическому, необходимо взять входной файл размером несколько тысяч символов). Однако, если мы теперь попробуем декодировать эту двоичную последовательность, то немедленно обнаружим, что Code1 совершенно не годен. Первый бит последовательности равен 1, поэтому первым символом может быть только Code2 имеет одно важное свойство, которое делает его лучше, чем Code1, которое называется свойством префикса. Это свойство можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код другого символа не должен иметь в начале эту последовательность (не может быть префиксом, то есть, приставкой). Раз строка «1» уже выбрана в качестве целого кода для Значит, выбирая множество кодов переменной длины, необходимо соблюдать два принципа: (1) следует назначать более короткие коды чаще встречающимся символам, и (2) коды должны удовлетворять свойству префикса. Следуя эти принципам, можно построить короткие, однозначно декодируемые коды, но не обязательно наилучшие (то есть, самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (которые в среднем имеют наименьшую длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. К счастью, такой простой алгоритм существует. Он был придуман Давидом Хаффманом и называется его именем. Этот алгоритм будет описан в § 1.4. Следует отметить, что не только статистические методы компрессии используют коды переменной длины при кодировании индивидуальных символов. Замечательным примером служат арифметические коды, о которых будет рассказано в § 1.7.
|