2015-05-06
614
Исходными данными для построения кода Шеннона-Фано является совокупность значений вероятностей появления символов сообщения.
Код Шеннона-Фано строится следующим образом:
1. Все имеющиеся К символов алфавита располагаются в один столбец в порядке убывания вероятностей.
2. Затем эти символы разбиваются на две приблизительно одинаковые по суммарному значению вероятностей группы, соответствующие ветвям кодового дерева, исходящим из его корня; верхнюю и нижнюю так, чтобы суммарные вероятности этих групп были по возможности ближе друг к другу. Для символов верхней группы в качестве первого элемента кодового слова используется «1», а для нижней «0».
3. Далее каждую из двух полученных групп вновь необходимо разделить на две части по возможности с близким суммарными вероятностями, в качестве второго элемента кодового слова используется «1» или «0» в зависимости от принадлежности символов верхней или нижней подгруппе и.т.д.
Данный процесс повторяется до тех пор, пока не сформируются группы, каждая из которых содержит по единственному символу, то есть пока каждый символ алфавита не будет иметь собственную ветвь кодового дерева. На практике, как правило, работают не с вероятностями, а с частотностями появления символов в сообщении, что не оказывает видимого влияния на алгоритм формирования кодового дерева.
