Методы построения префиксных кодов. Метод Фано.

Метод Рене Фано

1. Буквы алфавита А упорядочиваем по убыванию вероятностей:

2. Множество упорядоченных букв разбивается на 2 подмножестваА⁽⁰⁾ и А⁽¹⁾с помощью некоторого порогового целого числа так, чтобы

достигала наименьшего возможного значения. Буквам из подмножества А⁽⁰⁾ приписываем нули. Буквам подмножества А⁽¹⁾ приписываем единицы.

3. Если подгруппы А⁽⁰⁾ и А⁽¹⁾ состоят более чем из 2 букв, то разбываем множество букв каждой из подгрупп на 2 подгруппы. А⁽⁰⁰⁾,А⁽⁰¹⁾, и А⁽¹⁰⁾,А⁽¹¹⁾cоотвественно с помощью пороговых целых чисел 1<=k⁽¹¹⁾<=k⁽¹⁾-1 и k⁽¹⁾<=k⁽¹²⁾<=n-1так, чтобы величины

достигали наименьших возможных значений

Приписывание букв. Буквам из подгруппА⁽⁰⁰⁾ и А⁽⁰¹⁾ приписываем нули, а из А⁽¹⁰⁾,А⁽¹¹⁾ – единицы.

Если подгруппа A^(I,j), i,j=0,1 состоит более чем из одной буквы, то переходим к шагу 4. Если все подгруппы состоят из одной буквы, то переходим к шагу 5.

4. Если есть подгруппы, состояние более чем из 1 буквы, то разбиваем каждую из них на 2 подгруппы. Исходя из соотношений аналогично (1,2,3). Буквам подгрупп с нулевыми посл индексами приписываем 0. Буквам подгрупп с 1 посл индексами приписываем 1. Если есть подгрсост более чем из 1 буквы то повторяем шаг 4. Если все образовавшиеся подгруппы состоят из 1 группы, то переходим к шагу 5.

5. Если образовавшиеся подгруппы состоят из 1 буквы, то последовательно, начиная с последней метки, выписываем нули и единицы, относящиеся к каждой букве алфавита А. В итоге получается двоичный префиксный код для заданного источника с алфавитом А.

lср = =…

Не нашли, что искали? Воспользуйтесь поиском: