Previous: 2.6.3 Сжатие данных с использованием преобразования Барроуза-Вилера    UP: 2.6 Методы сжатия информации     Next: 2.6.5 Статический алгоритм Хафмана

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

Семенов Ю.А. (ИТЭФ-МФТИ)
Yu. Semenov (ITEP-MIPT)

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