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

2.6.4 Метод Шеннона-Фано
Семенов Ю.А. (ГНЦ ИТЭФ)

Данный метод выделяется своей простотой. Берутся исходные сообщения 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.

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

Hosted by uCoz