61. Алгоритм Фано.Пример
Метод кодирования Фано заключается в следующем: упорядоченной в порядке убывания системе букв приписываются действия.
1) Список букв делиться на две части a1……..ak, ak+1…….an. таким образом, чтобы суммы вероятностей обеих частей как можно меньше отличались друг от друга.
2) Буквам первой части приписывается символ 1,буквам второй части – 0.Далее точно также поступают с оставшимися частями. Процесс продолжается до тех пор, пока весь список не разделится на части, каждая из которых состоит из 1 – ой части.
3)Каждой букве ставится в соответствие последовательность из 1 и приписанных в результате деления. Каждая буква ai получает свой код, который является префиксным.
Метод Фано позволяет построить префиксный код, стоимость которого очень близка к оптимальной.
ПРИМЕР: Рассмотрим алфавит, состоящий из 7 букв.
A={a1, a2, a3, a4, a5, a6, a7,}
Даны вероятности уже в порядке убывания:
P={0,2; 0,2; 0,19; 0,12; 0,11; 0,09; 0,09}.
|
Метод Фано | ||
|
pi |
Коды |
hi |
|
0,20 0,20 0,19 0,12 0,11 0,09 0,09 |
00 010 011 100 101 110 111 |
2 3 3 3 3 3 3 |
62. Алгоритм кодирования Хаффмена.Пример
Лемма:
Пусть G=(αi->βi),
где i=1
до i=n;
схема оптимального кодирования для
вероятности p,
где p1≥p2≥…≥pn
I
.Тогда если pi
>pa
, то ki
<= kk
.
Теорема: Пусть Gn-1=(αi->βi), где i=1 до i=n-1 схема оптимального префиксного кодирования.
Пусть при этом pj = q/+q//, тогда p1≥p2≥…≥pj-1≥pj+1≥….≥pn-1≥ q/≥ q//>0. Тогда кодирование имеющие
Gn=( α1->β1,…, αj-1->βj-1 ,…, αj+1->βj+1,…., αn-1->βn-1)
Тогда кодирование с такой схемой, является оптимальным префиксным кодированием с системой P: p1,….,pj-1, pj+1,…, pn-1, q/, q//.
Данная теорема определяет способ построения алгоритма кода.
Для списка вероятностей упорядоченного по убыванию убирают две последние вероятности. Вероятности, а их список составляют так, чтобы он был упорядочен по убыванию, на втором шаге вновь выбрасывают две последние вероятности, а их сумма вставляется в преобразованный список так, чтобы он оставался упорядоченным по убыванию.
Первой вероятности принимают символ 0, второй символ 1.
Далее согласно теореме из оптимального кода для двух букв строиться оптимальный код для трех букв и т.д. до тех пор, пока не получится исходный код исходного списка вероятностей.
Пример:
0,2 0,2 0,23 0,37 0,4 0,6 0
0,2 0,2 0,2 0,23 0,37}00 0,4 1
0,19 0,19 0,2 0,2} 10 0,23}01
0,11 0,18 0,19} 000 0,2}11
0,09} 0010 0,12}010 0,18}001
0,09} 0010 0,11}010
} – показывается сумма!
Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.