55
правок
Изменения
→Адаптивное арифметическое кодирование
На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <tex>\alpha \in \sum</tex> сопоставляется его вес <tex>w_\alpha</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>.
Вероятность каждого символа <tex>\alpha</tex> {{---}} <tex>p(\alpha)</tex> устанавливется равной его весу, делённому на суммарный вес всех символов: <tex dpi="180">p(\alpha) = \fracdfrac{w_\alpha}{\sum_{i=1}^n w_i}</tex>. После получения очередного символа и построения нужного интервала, вес символа увеличивается на <tex>1</tex>. Когда все символы последовательности будут обработаны, необходимо либо записать маркер конца последовательности, либо запомнить её длину, чтобы позже передать декодировщику. После получения нужных границ <tex>[l, r]</tex>, в котором будет лежать код, необходмо выбрать число <tex>x</tex>, описывающее кодирование:<tex>x \in [l, r]</tex>. Выбор числа <tex>x</tex> производится также, как и в неадаптивном алгоритме. Выбирается число вида <tex>\fracdfrac{x}{2^p}: x,p \in \mathbb N</tex>.
=== Псевдокод алгоритма ===