Быстрый алгоритм адаптивного кодирования

Пусть $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|)$.