Сравнительная характеристика Шеннона-Фано и Хаффмана (кодов)

Методика Шеннона–Фано не всегда приводит к однозначному построению кода.
Ведь при разбиении на подгруппы на 1-й итерации можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу. В результате среднее число символов на букву окажется другим.
Таким образом, построенный код может оказаться не самым лучшим.

От указанного недостатка свободна методика Хаффмана. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

Метод Хаффмана производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Результаты эффективного кодирования по методу Хаффмана всегда лучше результатов кодирования по методу Шеннона-Фано.

Предложенный Хаффманом алгоритм построения оптимальных неравномерных кодов – одно из самых важных достижений теории информации, как с теоретической, так и с прикладной точек зрения. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия.

Трудно поверить, но этот алгоритм был придуман в 1952 г. студентом Дэвидом Хаффманом в процессе выполнения домашнего задания =).

Кодирование методом Хаффмана называют двухпроходным, так как его реализация распадается на два этапа:

1. на первом этапе реализуется алгоритм Хаффмана,
2. а на втором этапе строится дерево Хаффмана.