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

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

Метод Шеннон-Фано - это деление сверху вниз: он делит алфавит на 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. Частоты символов в сумме дают величину, близкую к степени двойки, и сами распределены близко к степеням двойки - совпадение деревьев почти гарантировано.