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