Здравствуйте, asdf1234!

Алгоритм Шеннона-Фано работает следующим образом:

1. Упорядочиваем символы по невозрастанию вероятностей.
2. Делим последовательность символов на две группы с примерно равной суммой вероятностей. Для первой группы добавляем справа в код 1, для второй - 0.
3. Повторяем предыдущий шаг для каждой из групп, пока не получим группу из единственного символа.

В данном случае это будет выглядеть так:

[table]
[row][col]Символы[/col][col]Вероятности[/col][/row]
[row][col]Z5[/col][col]0.22[/col][/row]
[row][col]Z3[/col][col]0.20[/col][/row]
[row][col]Z4[/col][col]0.15[/col][/row]
[row][col]Z2[/col][col]0.13[/col][/row]
[row][col]Z8[/col][col]0.10[/col][/row]
[row][col]Z7[/col][col]0.08[/col][/row]
[row][col]Z6[/col][col]0.07[/col][/row]
[row][col]Z1[/col][col]0.05[/col][/row]
[/table]
Это исходная таблица. Разбиваем её на две группы так, чтобы сумма вероятностей в каждой была по возможности близка к 0.5 и присваиваем первой код 1, а второй - код 0:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5,Z3,Z4[/col][col]0.22+0.20+0.15=0.57[/col][col]1[/col][/row]
[row][col]Z2,Z8,Z7,Z6,Z1[/col][col]0.13+0.10+0.08+0.07+0.05=0.43[/col][col]0[/col][/row]
[/table]
Теперь разбиваем первую группу на две с суммой вероятностей близкой к 0.57/2=0.285 и присваиваем им коды 11 и 10, а вторую - на две с суммой вероятностей близкой к 0.43/2=0.215 и присваиваем им коды 01 и 00:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col]11[/col][/row]
[row][col]Z3,Z4[/col][col]0.20+0.15=0.35[/col][col]10[/col][/row]
[row][col]Z2,Z8[/col][col]0.13+0.10=0.23[/col][col]01[/col][/row]
[row][col]Z7,Z6,Z1[/col][col]0.08+0.07+0.05=0.20[/col][col]00[/col][/row]
[/table]
Первая из четырёх получившихся групп содержит только один символ и дальше не разбивается. Остальные разбиваются надвое аналогичным образом:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col]11[/col][/row]
[row][col]Z3[/col][col]0.20[/col][col]101[/col][/row]
[row][col]Z4[/col][col]0.15[/col][col]100[/col][/row]
[row][col]Z2[/col][col]0.13[/col][col]011[/col][/row]
[row][col]Z8[/col][col]0.10[/col][col]010[/col][/row]
[row][col]Z7[/col][col]0.08[/col][col]001[/col][/row]
[row][col]Z6,Z1[/col][col]0.07+0.05=0.12[/col][col]000[/col][/row]
[/table]
Теперь все группы содержат по одному символу, только последняя - два. Её разбиваем надвое:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col]11[/col][/row]
[row][col]Z3[/col][col]0.20[/col][col]101[/col][/row]
[row][col]Z4[/col][col]0.15[/col][col]100[/col][/row]
[row][col]Z2[/col][col]0.13[/col][col]011[/col][/row]
[row][col]Z8[/col][col]0.10[/col][col]010[/col][/row]
[row][col]Z7[/col][col]0.08[/col][col]001[/col][/row]
[row][col]Z6[/col][col]0.07[/col][col]0001[/col][/row]
[row][col]Z1[/col][col]0.05[/col][col]0000[/col][/row]
[/table]
и на этом построение кода Шеннона-Фано закончено.

Алгоритм Хаффмана работает следующим образом:

1. Упорядочиваем символы по невозрастанию вероятностей.
2. Два символа с наименьшими вероятностями заменяем группой с суммарной вероятностью. Для первого символа группы добавляем слева в код 0, для второго - 1, для остальных символов не добавляем ничего.
3. Повторяем, пока не получим группу, объединяющую все символы.

В данном случае это будет выглядеть так:

[table]
[row][col]Символы[/col][col]Вероятности[/col][/row]
[row][col]Z5[/col][col]0.22[/col][/row]
[row][col]Z3[/col][col]0.20[/col][/row]
[row][col]Z4[/col][col]0.15[/col][/row]
[row][col]Z2[/col][col]0.13[/col][/row]
[row][col]Z8[/col][col]0.10[/col][/row]
[row][col]Z7[/col][col]0.08[/col][/row]
[row][col]Z6[/col][col]0.07[/col][/row]
[row][col]Z1[/col][col]0.05[/col][/row]
[/table]
Объединяем два последних символа (Z6 и Z1) в одну группу и присваиваем им коды 0 и 1. Остальным символам коды не присваиваем:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z8[/col][col]0.10[/col][col][/col][/row]
[row][col]Z7[/col][col]0.08[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.07+0.05=0.12[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.12[/col][col]0,1[/col][/row]
[row][col]Z8[/col][col]0.10[/col][col][/col][/row]
[row][col]Z7[/col][col]0.08[/col][col][/col][/row]
[/table]

и объединяем символы Z8 и Z7, присваивая новой группе коды 0 и 1 (остальные символы по-прежнему не имеют кодов):
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.12[/col][col]0,1[/col][/row]
[row][col]Z8,Z7,[/col][col]0.10+0.08=0.18[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z8,Z7[/col][col]0.18[/col][col]0,1[/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.12[/col][col]0,1[/col][/row]
[/table]
и объединяем два последних символа (Z2 и Z6,Z1) в одну группу, присвоив им коды 0 и 10,11:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z8,Z7[/col][col]0.18[/col][col]0,1[/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.13+0.12=0.25[/col][col]0,10,11[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.25[/col][col]0,10,11[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z8,Z7[/col][col]0.18[/col][col]0,1[/col][/row]
[row][col]Z4[/col][col]0.15[/col][col][/col][/row]
[/table]
и объединяем символы Z8,Z7 и Z4, присваивая новой группе коды 00,01 и 1:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.25[/col][col]0,10,11[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z8,Z7,Z4[/col][col]0.18+0.15=0.33[/col][col]00,01,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z8,Z7,Z4[/col][col]0.33[/col][col]00,01,1[/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.25[/col][col]0,10,11[/col][/row]
[row][col]Z5[/col][col]0.22[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[/table]
и объединяем два последних символа (Z5 и Z3) в одну группу, присвоив им коды 0 и 1:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z8,Z7,Z4[/col][col]0.33[/col][col]00,01,1[/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.25[/col][col]0,10,11[/col][/row]
[row][col]Z5,Z3[/col][col]0.22+0.20=0.42[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5,Z3[/col][col]0.42[/col][col]0,1[/col][/row]
[row][col]Z8,Z7,Z4[/col][col]0.33[/col][col]00,01,1[/col][/row]
[row][col]Z2,Z6,Z1[/col][col]0.25[/col][col]0,10,11[/col][/row]
[/table]
и объединяем символы Z8,Z7,Z4 и Z2,Z6,Z1, присваивая новой группе коды 000,001,01 и 10,110,111:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5,Z3[/col][col]0.42[/col][col]0,1[/col][/row]
[row][col]Z8,Z7,Z4,Z2,Z6,Z1[/col][col]0.33+0.25=0.58[/col][col]000,001,01,10,110,111[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z8,Z7,Z4,Z2,Z6,Z1[/col][col]0.58[/col][col]000,001,01,10,110,111[/col][/row]
[row][col]Z5,Z3[/col][col]0.42[/col][col]0,1[/col][/row]
[/table]
Поскольку осталось только две группы символов, добавляем слева к кодам первой 0, а к кодам второй - 1 и снова разделяем группы на отдельные символы:
[table]
[row][col]Символы[/col][col]Коды[/col][/row]
[row][col]Z8[/col][col]0000[/col][/row]
[row][col]Z7[/col][col]0001[/col][/row]
[row][col]Z4[/col][col]001[/col][/row]
[row][col]Z2[/col][col]010[/col][/row]
[row][col]Z6[/col][col]0110[/col][/row]
[row][col]Z1[/col][col]0111[/col][/row]
[row][col]Z5[/col][col]10[/col][/row]
[row][col]Z3[/col][col]11[/col][/row]
[/table]
На этом построение кода Хаффмана закончено.