Составители:
26
волов. Однако, есть примеры строк, в которых символы равновероятны, но не являются
случайными, и их можно сжимать. Хорошим примером является последователь-
ность
11
, ...aa
1 2 2
, , ...a a a
2 3 3
,,a a a
. Заметим, что код Хаффмана не работает с двух символь-
ным алфавитом. В таком алфавите одному символу придется присвоить код 0, другому -
1. Метод Хаффмана не может присвоить одному символу код короче одного бита.
В общем случае декодер тем или другим способом получает информацию о дереве
Хаффмана и алфавите кода, только в этом случае возможно декодирование. Алгоритм де-
кодирования очень прост. Эта операция начинается с корня дерева и читается первый бит
сжатого файла. Если это нуль, следует двигаться по нижней ветке дерева, если единица,
то двигаться надо по верхней ветке дерева. Далее читается второй бит и происходит дви-
жение по следующей ветке по направлению к листьям. Когда декодер достигнет листа
дерева, он узнает код первого несжатого символа (обычно это символ ASC11). Процедура
повторяется для следующего бита, начиная опять с корня дерева.
В кодере и декодере кода Хаффмана может использоваться одно и то же дерево, ус-
редненное по многочисленным сообщениям. Тогда его не надо строить и передавать вме-
сте с сообщениями, отпадает необходимость первого прохода при кодировании . Иногда
такое дерево может оказаться не оптимальным, поэтому удобно иметь несколько деревь-
ев, одинаковых в кодере и декодере, для передачи информации различного характера.
Классический алгоритм Хаффмана имеет один существенный недостаток. Для вос-
становления содержимого сообщения декодер должен знать таблицу кодирования, кото-
рой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину
этой таблицы, которая должна посылаться впереди данных, что приводит к увеличению
размеров выходного файла, и, следовательно, снижению степени сжатия. Кроме того, не-
обходимость наличия полной статистики по вероятности кодовых комбинаций перед на-
чалом собственно кодирования требует двух проходов по сообщению: одного для по-
строения модели сообщения (таблицы кодирования - дерева), другого для собственно ко-
дирования.
Следующим шагом в развитии алгоритма Хаффмана является его адаптивная версия.
Адаптивное сжатие Хаффмана позволяет не передавать модель сообщения вместе с ним
самим и ограничиться одним проходом по сообщению, как при кодировании, так и при
декодировании. Практически любая форма кодирования может быть конвертирована в
адаптивную. Схема адаптивного кодирования/декодирования работает благодаря тому,
что при кодировании и при декодировании используются одни и те же процедуры . И
компрессор, и декомпрессор начинают с "пустой" модели (не содержащей информации о
сообщении) и с каждым просмотренным символом обновляют ее одинаковым образом.
Хорошо было бы, чтобы кодер не тратил зря кодовое пространство на символы, кото-
рые не встречаются в сообщении. Если речь идет о классическом алгоритме Хаффмана, то
те символы, которые не встречаются в сообщении, уже известны до начала кодирования,
так как известна таблица частот и символы, у которых частота встречаемости равна 0. В
адаптивной версии алгоритма мы не можем знать заранее, какие символы появятся в со-
общении. Можно проинициализировать дерево Хаффмана так, чтобы оно имело все 256
символов алфавита (для 8-и битовых кодов) с частотой появления, равной 1. В начале ко-
дирования каждый код будет иметь длину 8 битов. По мере адаптации модели наиболее
часто встречающиеся символы будут кодироваться все меньшим и меньшим количеством
Табл. 4. Коды Хаффмана для 5…8 символов
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »
