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