Кодирование Шеннона-Фано

Методы эффективного кодирования сообщений для передачи по дискретному каналу без помех, предложенные Шенноном и Фано, заложили основу статистических методов сжатия данных. Код Шеннона-Фано строится следующим образом: символы алфавита выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были максимально близки (по возможности, равны). В кодах всех символов верхней группы первый бит устанавливается равным 0, в нижней группы – 1. Затем каждую из групп разбивают на две подгруппы с одинаковыми суммами вероятностей, и процесс назначения битов кода продолжается по аналогии с первым шагом. Кодирование завершается, когда в каждой группе останется по одному символу.

Качество кодирования по Шеннону-Фано сильно зависит от выбора разбиений на подгруппы: чем больше разность сумм вероятностей подгрупп, тем более избыточным оказывается код. Для дальнейшего уменьшения избыточности, используют кодирование крупными блоками – в качестве “символов” используются комбинации исходных символов сообщения, но и этот подход имеет те же ограничения. От указанного недостатка свободна методика кодирования Хаффмана.