Ковалев Д.С. "ОБОБЩЕНИЕ ИЗВЕСТНЫХ СПОСОБОВ КОДИРОВАНИЯ СТРОК"

ОБОБЩЕНИЕ ИЗВЕСТНЫХ СПОСОБОВ КОДИРОВАНИЯ СТРОК

В перовой части статьи рассматривается кодирование Хаффмана. Его ключевым элементом является построение бинарного дерева. Дерево задает некоторый способ рекурсивного разбиения множества алфавита для получения префиксных кодов. Широко известно обобщение бинарного дерева на 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.

Keywords: Huffman coding, Lempel-Ziv algorithms, LZ77, LZ78, enumerative coding.

Страницы 5 - 14

Прикрепленный файлРазмер
01.pdf265.39 кб