Ковалев Д.С. Обобщение известных способов кодирования строк

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