Шеннон - Фано и Хаффман

Оба метода работают на взвешенном алфавите (с назначенной каждому символу частотой).

Метод Шеннон-Фано - это деление сверху вниз: он делит алфавит на 2 части с примерно равной суммарной частотой и каждой части назначает 1 бит, затем в каждой из частей процесс рекурсивно повторяется.

Метод Хаффмана - это деление снизу вверх: на каждом шаге выбираются два символа с наименьшими частотами, им назначается 1 бит, в алфавит вставляется объединённый символ с суммарной частотой, а исходные 2 символа удаляются. Шаг повторяется, пока все символы не будут объединены в один.

Метод Хаффмана более тонко учитывает неравномерные распределения частот, не.соответствующих степени 2. Например, для следующего алфавита:

 A  15

B   7

C   6

D   6

E   5

F   1 

Шеннон-Фано сразу разделит его на группы AE и BCDF с частотами по 20, и на следующих шагах A и E получат одинаковое количество бит (по 2), а более часто встречающиеся символы B, C, D получат по 3 бита, т.к. попадут в большее подмножество.
Хаффман начнёт с объединения E и F, и у них не будет шанса получить больше бит, чем у более часто встречающихся символов.

При малом разбросе частот и Шеннон-Фано, и Хаффман будут группировать символы примерно равномерно. Деревья при этом могут получиться одинаковыми или разными (метод Шеннона-Фано вообще недетерменирован), но распределение кол-ва бит по символам в итоговом коде окажется примерно одинаковым и с минимальным разбросом (в 1 бит). В этом можно убедиться, попробовав закодировать следующий алфавит:

 A  50

B  49

C  48

D  47

E  46

F  45 

При большом разбросе частот метод Шеннона-Фано даст хороший (совпадающий с методом Хаффмана) код, когда частоты близки к степеням двойки, и их сумма близка к степени двойки, например:

 A  64

B  32

C  16

D   8

E   4

F   4 

Тогда деление алфавита пополам всегда будет давать частоту, близкую к степени 2, а её распределение между символами будет соответствовать количеству назначаемых им бит.
Оба метода дадут одинаковое количество бит для символов:

 A - 1 бит

B - 2 бита

C - 3 бита

D - 4 бита

E - 5 бит

F - 5 бит 

Поэтому можно сказать, что деревья Шеннона-Фано и Хаффмана совпадают в двух случаях:

1. Частоты символов примерно равны (кодирование почти не уменьшает длину сообщения) - есть шанс на совпадение деревьев.
2. Частоты символов в сумме дают величину, близкую к степени двойки, и сами распределены близко к степеням двойки - совпадение деревьев почти гарантировано.