Как работает алгоритм построения оптимального префиксного кода по заданному множеству данных?

Алгоритм построения оптимального префиксного кода по заданному множеству данных может работать по-разному в зависимости от используемого алгоритма.

Алгоритм Фано: iordanskyma.wordpress.com

1. Список букв алфавита источника упорядочивается в порядке невозрастания вероятностей их появления в сообщениях. iordanskyma.wordpress.com
2. Список букв делится на две последовательные части с равными или примерно равными суммами вероятностей. iordanskyma.wordpress.com
3. Буквам первой части приписывается цифра 0, а буквам второй части — цифра 1. iordanskyma.wordpress.com
4. Действия пунктов 2 и 3 применяются к каждой части до тех пор, пока все полученные части не станут содержать по одной букве. iordanskyma.wordpress.com
5. Каждой букве ставится в соответствие элементарный код, состоящий из цифр 0 и 1, последовательно приписанных частям, содержащим эту букву. iordanskyma.wordpress.com

Алгоритм Хаффмана: ru.wikipedia.org

1. На входе получает таблицу частотностей символов в сообщении. ru.wikipedia.org
2. На основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). ru.wikipedia.org Символы входного алфавита образуют список свободных узлов. ru.wikipedia.org Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение. ru.wikipedia.org
3. Выбираются два свободных узла дерева с наименьшими весами. ru.wikipedia.org
4. Создаётся их родитель с весом, равным их суммарному весу. ru.wikipedia.org Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка. ru.wikipedia.org
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. ru.wikipedia.org Битовые значения ветвей, исходящих от корня, не зависят от весов потомков. ru.wikipedia.org
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. ru.wikipedia.org Он и будет считаться корнем дерева. ru.wikipedia.org
7. Чтобы определить код для каждого из символов, входящих в сообщение, нужно пройти путь от листа дерева, соответствующего текущему символу, до его корня, накапливая биты при перемещении по ветвям дерева (первая ветвь в пути соответствует младшему биту). ru.wikipedia.org

Также существует метод Хаффмана, который заключается в последовательной замене букв, имеющих наименьшие вероятности, на одну новую, имеющую вероятность, равную сумме вероятностей заменяемых букв. math-info.hse.ru