Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана.
Рис. Кодовое слово непрефиксного кода
Сообщения алфавита источника выписывают в порядке убывания вероятностей их появления. Далее разделяют их на две части так, чтобы суммарные вероятности сообщений в каждой из этих частей были по возможности почти одинаковыми. Припишем сообщениям первой части в качестве первого символа – 0, а второй – 1 (можно наоборот). Затем каждая из этих частей (если она содержит более одного сообщения) делится на две по возможности равновероятные части, и в качестве второго символа для первой из них берется 0, а для второй – 1. Этот процесс повторяется, пока в каждой из полученных частей не останется по одному сообщению.
Пример:
Р(а1)=0,1 Р(а2)=0,15 Р(а3)=0,15 Р(а4)=0,1 Р(а5)=0,05
Р(а6)=0,05 Р(а7)=0,2 Р(а8)=0,07 Р(а9)=0,09 Р(а10)=0,04
Рис. Кодовое дерево кода Шеннона – Фано
Методика Шеннона – Фано не всегда приводит к однозначному построению кода, поскольку при разбиении на части можно сделать больше по вероятности как верхнюю, так и нижнюю части. Кроме того, методика не обеспечивает отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. (Под оптимальностью подразумевается то, что никакое другое однозначно декодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество.) Предложенная Хаффманом конструктивная методика свободна от отмеченных недостатков.