Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.13. Использование кодов Хаффмена

Построение кодов Хаффмена является в значительной мере рекурсивным и их легко реализовать программными средствами на ЭВМ. Схема декодирования конечным автоматом (деревом), о которой говорилось в разд. 4.2, дает метод декодирования кодов Хаффмена с применением одного -ичного ветвления на каждый принятый -ичный символ. Метод является быстрым и простым, и каждый принятый символ просматривается только один раз.

Для источников с разумным объемом алфавита кодирование кодов Хаффмена проводится посредством табличного поиска. Если имеется большой объем информации, которую нужно поместить в долговременную память ЭВМ, и если вероятности символов источника значительно отличаются друг от друга, то может оказаться выгодным закодировать информацию подходящим кодом Хаффмена для того, чтобы сэкономить долговременную память ЭВМ. Как было показано, степень экономии зависит от того, насколько сильно вероятности отличаются друг от друга.

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

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

Задача

4 13.1. Рассмотреть составление программы для ЭВМ, которая строит код Хаффмена по

<< Предыдущий параграф Следующий параграф >>
Оглавление