В чем заключается метод построения кода Фано?

Метод построения кода Фано (алгоритм Шеннона — Фано) — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Клод Шеннон и Роберт Фано. 34

Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. 34

Метод строится с помощью дерева. 34 Построение начинается от корня: 34

1. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). 34
2. Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. 34 Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. 34
3. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. 34 Им соответствуют вершины третьего уровня. 34
4. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. 34
5. Подобным образом поступают до тех пор, пока не получат все концевые вершины. 34
6. Ветви кодового дерева размечают символами 1 и 0. 34

Условие Фано при построении кода заключается в том, что ни одно кодовое слово не должно быть началом другого. 15 Это свойство позволяет однозначно декодировать любую последовательность кодовых слов. 34