|
|
|
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 Методы сжатия информации
|
