55
правок
Изменения
→Оценка минимальной и максимальной длины кода
{{Теорема
|id = th1.
|statement= При адаптивном арифметическом кодировании строки длины <tex>\mathtt{l}</tex>, символы которой принадлежат алфавиту мощности <tex>\mathtt{n}</tex>, полученный код будет лежать в диапазоне <tex>[\frac{(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>
