Здравствуйте, Чванов Сергей!

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

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

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

[table]
[row][col]Символы[/col][col]Вероятности[/col][/row]
[row][col]Z5[/col][col]0.21[/col][/row]
[row][col]Z3[/col][col]0.20[/col][/row]
[row][col]Z4[/col][col]0.17[/col][/row]
[row][col]Z2[/col][col]0.13[/col][/row]
[row][col]Z8[/col][col]0.11[/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.03[/col][/row]
[/table]
Это исходная таблица. Разбиваем её на две группы так, чтобы сумма вероятностей в каждой была по возможности близка к 0.5 и присваиваем первой код 1, а второй - код 0:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5,Z3,Z4[/col][col]0.21+0.20+0.17=0.58[/col][col]1[/col][/row]
[row][col]Z2,Z8,Z7,Z6,Z1[/col][col]0.13+0.11+0.08+0.07+0.03=0.42[/col][col]0[/col][/row]
[/table]
Теперь разбиваем первую группу на две с суммой вероятностей близкой к 0.58/2=0.29 и присваиваем им коды 11 и 10, а вторую - на две с суммой вероятностей близкой к 0.42/2=0.21 и присваиваем им коды 01 и 00:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col]11[/col][/row]
[row][col]Z3,Z4[/col][col]0.20+0.17=0.37[/col][col]10[/col][/row]
[row][col]Z2,Z8[/col][col]0.13+0.11=0.24[/col][col]01[/col][/row]
[row][col]Z7,Z6,Z1[/col][col]0.08+0.07+0.03=0.18[/col][col]00[/col][/row]
[/table]
Первая из четырёх получившихся групп содержит только один символ и дальше не разбивается. Остальные разбиваются надвое аналогичным образом:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col]11[/col][/row]
[row][col]Z3[/col][col]0.20[/col][col]101[/col][/row]
[row][col]Z4[/col][col]0.17[/col][col]100[/col][/row]
[row][col]Z2[/col][col]0.13[/col][col]011[/col][/row]
[row][col]Z8[/col][col]0.11[/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.03=0.1[/col][col]000[/col][/row]
[/table]
Теперь все группы содержат по одному символу, только последняя - два. Её разбиваем надвое:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Код[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col]11[/col][/row]
[row][col]Z3[/col][col]0.20[/col][col]101[/col][/row]
[row][col]Z4[/col][col]0.17[/col][col]100[/col][/row]
[row][col]Z2[/col][col]0.13[/col][col]011[/col][/row]
[row][col]Z8[/col][col]0.11[/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.03[/col][col]0000[/col][/row]
[/table]
и на этом построение кода Шеннона-Фано закончено.

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

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

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

[table]
[row][col]Символы[/col][col]Вероятности[/col][/row]
[row][col]Z5[/col][col]0.21[/col][/row]
[row][col]Z3[/col][col]0.20[/col][/row]
[row][col]Z4[/col][col]0.17[/col][/row]
[row][col]Z2[/col][col]0.13[/col][/row]
[row][col]Z8[/col][col]0.11[/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.03[/col][/row]
[/table]
Объединяем два последних символа (Z6 и Z1) в одну группу и присваиваем им коды 0 и 1. Остальным символам коды не присваиваем:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z8[/col][col]0.11[/col][col][/col][/row]
[row][col]Z7[/col][col]0.08[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.07+0.03=0.1[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z8[/col][col]0.11[/col][col][/col][/row]
[row][col]Z6,Z1[/col][col]0.1[/col][col]0,1[/col][/row]
[row][col]Z7[/col][col]0.08[/col][col][/col][/row]
[/table]

и объединяем символы Z6,Z1 и Z7, присваивая новой группе коды 00,01 и 1 (остальные символы по-прежнему не имеют кодов):
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z8[/col][col]0.11[/col][col][/col][/row]
[row][col]Z6,Z1,Z7,[/col][col]0.1+0.08=0.18[/col][col]00,01,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z6,Z1,Z7[/col][col]0.18[/col][col]00,01,1[/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[row][col]Z2[/col][col]0.13[/col][col][/col][/row]
[row][col]Z8[/col][col]0.11[/col][col][/col][/row]
[/table]
и объединяем два последних символа (Z2 и Z8) в одну группу, присвоив им коды 0 и 1:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z6,Z1,Z7[/col][col]0.18[/col][col]00,01,1[/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[row][col]Z2,Z8[/col][col]0.13+0.11=0.24[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z2,Z8[/col][col]0.24[/col][col]0,1[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z6,Z1,Z7[/col][col]0.18[/col][col]00,01,1[/col][/row]
[row][col]Z4[/col][col]0.17[/col][col][/col][/row]
[/table]
и объединяем символы Z6,Z1,Z7 и Z4, присваивая новой группе коды 000,001,01 и 1:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z2,Z8[/col][col]0.24[/col][col]0,1[/col][/row]
[row][col]Z5[/col][col]0.21[/col][col][/col][/row]
[row][col]Z3[/col][col]0.20[/col][col][/col][/row]
[row][col]Z6,Z1,Z7,Z4[/col][col]0.18+0.17=0.35[/col][col]000,001,01,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z6,Z1,Z7,Z4[/col][col]0.35[/col][col]000,001,01,1[/col][/row]
[row][col]Z2,Z8[/col][col]0.24[/col][col]0,1[/col][/row]
[row][col]Z5[/col][col]0.21[/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]Z6,Z1,Z7,Z4[/col][col]0.35[/col][col]000,001,01,1[/col][/row]
[row][col]Z2,Z8[/col][col]0.24[/col][col]0,1[/col][/row]
[row][col]Z5,Z3[/col][col]0.21+0.20=0.41[/col][col]0,1[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5,Z3[/col][col]0.41[/col][col]0,1[/col][/row]
[row][col]Z6,Z1,Z7,Z4[/col][col]0.35[/col][col]000,001,01,1[/col][/row]
[row][col]Z2,Z8[/col][col]0.24[/col][col]0,1[/col][/row]
[/table]
и объединяем символы Z6,Z1,Z7,Z4 и Z2,Z8, присваивая новой группе коды 0000,0001,001,01 и 10,11:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z5,Z3[/col][col]0.41[/col][col]0,1[/col][/row]
[row][col]Z6,Z1,Z7,Z4,Z2,Z8[/col][col]0.35+0.24=0.59[/col][col]0000,0001,001,01,10,11[/col][/row]
[/table]
Упорядочиваем получившуюся таблицу по убыванию вероятностей:
[table]
[row][col]Символы[/col][col]Вероятности[/col][col]Коды[/col][/row]
[row][col]Z6,Z1,Z7,Z4,Z2,Z8[/col][col]0.59[/col][col]0000,0001,001,01,10,11[/col][/row]
[row][col]Z5,Z3[/col][col]0.41[/col][col]0,1[/col][/row]
[/table]
Поскольку осталось только две группы символов, добавляем слева к кодам первой 0, а к кодам второй - 1 и снова разделяем группы на отдельные символы:
[table]
[row][col]Символы[/col][col]Коды[/col][/row]
[row][col]Z6[/col][col]00000[/col][/row]
[row][col]Z1[/col][col]00001[/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]Z8[/col][col]011[/col][/row]
[row][col]Z5[/col][col]10[/col][/row]
[row][col]Z3[/col][col]11[/col][/row]
[/table]
На этом построение кода Хаффмана закончено.