2.6.4. Метод Шеннона-Фано

Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru

Данный метод выделяется своей простотой. Берутся исходные сообщения m(i) и их вероятности появления P(m(i)). Этот список делится на две группы с примерно равной интегральной вероятностью. Каждому сообщению из группы 1 присваивается 0 в качестве первой цифры кода. Сообщениям из второй группы ставятся в соответствие коды, начинающиеся с 1. Каждая из этих групп делится на две аналогичным образом и добавляется еще одна цифра кода. Процесс продолжается до тех пор, пока не будут получены группы, содержащие лишь одно сообщение. Каждому сообщению в результате будет присвоен код x c длиной –lg(P(x)). Это справедливо, если возможно деление на подгруппы с совершенно равной суммарной вероятностью. Если же это невозможно, некоторые коды будут иметь длину –lg(P(x))+1. Алгоритм Шеннона-Фано не гарантирует оптимального кодирования. Смотри http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html.

Назад: 2.6.3. Сжатие данных с использованием преобразования Барроуза-Вилера
Оглавление: Телекоммуникационные технологии
Вперёд: 2.6.5. Статический алгоритм Хафмана