Статья. Опубликована в Вестнике НГУ (Новосибирск). Серия
«Информационные технологии». — 2010. — Том 8 . — Выпуск 4 . — С.
5-14.
В статье рассматривается кодирование Хаффмана. Его ключевым
элементом является построение бинарного дерева. Дерево задает
некоторый способ рекурсивного разбиения множества алфавита для
получения префиксных кодов. Широко известно обобщение бинарного
дерева на q-арное. В данной статье приводится обобщение кодирования
Хаффмана на случай произвольного дерева. Описывается новый подход
для понимания алгоритмов кодирования семейства Лемпеля - Зива.
Предлагается считать, что эти алгоритмы кодируют не саму строку, а
некоторое отображение, связанное с ней. При этом строка является
неподвижной точкой кодируемого отображения.