Изменения
→Оценка минимальной и максимальной длины кода
На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <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>.
=== Псевдокод алгоритма ===
{{Теорема
|id = th1.
|statement= При адаптивном арифметическом кодировании строки длины <tex>\mathtt{l}</tex>, символы которой принадлежат алфавиту мощности <tex>\mathtt{n}</tex>, полученный код будет лежать в диапазоне <tex>[\fracdfrac{(n-1)!}{(n+l-1)!}, \fracdfrac{l!(n-1)!}{(n+l-1)!}]</tex>
|proof=
Во время кодирования строки алгоритм выбирает необходимый подотрезок, увеличивает вес символа и перестраивает подотрезки.
Пусть <tex>L</tex> {{---}} результат кодирования строки длины <tex>l</tex>, использующей алфавит длины <tex>n</tex>. Код <tex>L</tex> формируется следующим образом: на каждом из шагов <tex>k=1, 2, \dots, l</tex>
он изменяется в <tex>\fracdfrac{w_{\alpha_k}}{n+k-1}</tex> раз. На каждом шаге <tex>k</tex>-й символ <tex>\alpha</tex> будет иметь вес <tex>\alpha_k</tex> (каждый раз больший на <tex>1</tex>, потому что алгоритм адаптивный).
Значит, на каждом шаге суммарный вес символов будет увеличиваться на <tex>1</tex>, т.е. на шаге <tex>k</tex> суммарный вес символов будет равен <tex>n+k-1</tex>
Во время перестроения подотрезков, по алгоритму, каждому символу ствавится в соответствие подотрезок длины <tex>\fracdfrac{w_{\alpha_k}}{n+k-1}</tex>.
В общем виде его можно представить так:
<tex>
L = \prod_{i=1}^l \fracdfrac{w_{\alpha_i}}{n+i-1}
</tex>
Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов.
Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов.
В таком случае вес каждого из полученных символов будет равен <tex>1</tex>, а значение кода на каждом из шагов <tex>k=1, 2, \dots, l</tex> будет изменяться в <tex>\fracdfrac{1}{n+k-1}</tex> раз.
Соответственно, формула примет вид:
<tex>
L_{min} = \prod_{i=1}^l \fracdfrac{1}{n+i-1} = \fracdfrac{1}{\fracdfrac{(n+l-1)!}{(n-1)!}} = \fracdfrac{(n-1)!}{(n+l-1)!}
</tex>
Можно записать, используя формулы комбинаторики:
<tex>
L_{min} = \fracdfrac{1}{{\binom{l}{n+l-1}}l!} = \fracdfrac{1}{C_{n+l-1}^{l}l!}
</tex>
==== Докажем верхнюю границу: Верхняя граница ====
Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\fracdfrac{k}{n+k-1}</tex> раз.
Соответственно, формула будет иметь следующий вид:
<tex>
L_{max} = \prod_{i=1}^l \fracdfrac{i}{n+i-1} = \fracdfrac{l!(n-1)!}{(n+l-1)!}
</tex>
<tex>
L_{max} = \fracdfrac{1}{\binom{n+l-1}{l}} = \fracdfrac{1}{C_{n+l-1}^{l}}
</tex>
}}
{{Утверждение
|id = th1.
|statement=При адаптивном арифметическом кодировании строки длины <tex>l</tex>, символы которой принадлежат алфавиту мощности <tex>n</tex>, количество бит, необходимых для кодирования сообщения будет лежать в диапазоне <tex>[-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}]</tex>
|proof=
Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:
<tex>
log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1}
</tex>
Все коды лежат в диапазоне <tex>[0, 1)</tex>.
Таким образом:
Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:
<tex>
log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1}
</tex>
Минимальное число бит будет затрачено в случае записи кода максимального размера:
<tex>
log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i}
</tex>
}}
