В статье рассматривается кодирование Хаффмана. Его ключевым элементом является построение бинарного дерева. Дерево задает некоторый способ рекурсивного разбиения множества алфавита для получения префиксных кодов. Широко известно обобщение бинарного дерева на q-арное. В данной статье приводится обобщение кодирования Хаффмана на случай произвольного дерева. Описывается новый подход для понимания алгоритмов кодирования семейства Лемпеля – Зива. Предлагается считать, что эти алгоритмы кодируют не саму строку, а некоторое отображение, связанное с ней. При этом строка является неподвижной точкой кодируемого отображения.
The first part of this paper is about Huffman coding. Its key feature is a binary tree construction. This tree defines recursive partition of alphabet set to construct prefix codes. Generalization of binary tree to q-ary tree is well known. This paper gives Huffman coding generalization for any trees. The second part of this paper defines another approach to understanding Lembel-Ziv family of algorithms. The suggestion is that these algorithms encode a mapping associated with a string, not a string itself. The string is a fixed point of encoded mapping in this case.
