Эта публикация цитируется в
4 статьях
Теория информации и теория кодирования
Быстрый алгоритм адаптивного кодирования
Б. Я. Рябко
Аннотация:
Пусть
$x_1,x_2\dots x_N$,
$N\geq 1$ – некоторое слово в конечном алфавите
$A$. Рассматриваются последовательные методы кодирования, т.е. такие, когда буквам
$x_1,x_2,\dots$ ставятся в соответствие слова из двоичного алфавита, причем код буквы
$x_i$ может зависеть только от
$x_1\dots x_{i-1}$. (Такие коды эффективны при сжатии текстов, хранящихся в памяти компьютеров [1–3].) В [1] предложен код, у которого при большом числе букв в алфавите
$A(|A|\to\infty)$ избыточность минимальна по порядку –
$O(1)$ бит, время кодирования и декодирования одной буквы
$O(|A|\log|A|)$. В [2, 4] описана реализация метода «стопка книг» из [5], у которой время –
$O(\log^2|A|)$, а избыточность
$\log\log|A|$ бит. В данной работе предлагается алгоритм, позволяющий соединить достоинства кодов из [1] и [5, 2]: его избыточность минимальна и равна
$O(1)$ бит, а время кодирования и декодирования
$O(\log^2|A|)$, что близко к очевидной нижней границе
$О(\log|A|)$.
УДК:
621.391.15
Поступила в редакцию: 23.01.1989
После переработки: 27.03.1990