Изменения
added adaptive coding
Число бит в закодированном тексте:
<tex>\log_2 L = -\sum\limits_{i=1}^n f_i\cdot \log_2 p_i = -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1 \ldots p_n)</tex>
}}
== Адаптивное арифметическое кодирование ==
Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, что декодировщику не нужно передавать вероятностные оценки для символов, он будет строить их по мере декодирования сообщения, что может сильно сократить вес такого сообщения.
=== Алгоритм кодирования ===
На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <tex>\alpha \in \sum</tex> сопоставляется его вес <tex>w_\alpha</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>.
Вероятность каждого символа <tex>\alpha</tex> {{---}} <tex>p(\alpha)</tex> устанавливется равной его весу, делённому на суммарный вес всех символов: <tex dpi="180">p(\alpha) = \dfrac{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>\dfrac{x}{2^p}: x,p \in \mathbb N</tex>.
=== Псевдокод алгоритма ===
* <tex>\mathtt{in}</tex> {{---}} текст, подаваемый на вход
* <tex>\mathtt{n}</tex> {{---}} длина исходного текста
* <tex>\mathtt{Segment}</tex> {{---}} структура, задающая подотрезок отрезка <tex>[0, 1)</tex>, соответствующая конкретному символу. Имеет следующие поля:
** <tex> \mathtt{left} </tex> {{---}} левая граница подотрезка
** <tex> \mathtt{right} </tex> {{---}} правая граница подотрезка
* <tex> \mathtt{m} </tex> {{---}} мощность алфавита
* <tex> \mathtt{weight} </tex> {{---}} веса символов алфавита
* <tex> \mathtt{segments} </tex> {{---}} набор подотрезков, соответствующих символам алфавита
* <tex> \mathtt{left, right} </tex> {{---}} границы отрезка, содержащие возможный результат арифметического кодирования
* <tex> \mathtt{getAlphabet(in : char[n])}</tex> {{---}} функция возвращает множество различных символов в тексте <tex> \mathtt{in} </tex>
==== Подотрезок ====
'''struct''' Segment:
'''double''' left;
'''double''' right;
==== Определение начальных границ подотрезков ====
'''map<char,''' '''Segment'''> defineSegments'''('''set<char>''' alphabet):
<font color=green>// определяем размер подотрезков </font>
double p = 1 / alphabet.size()
'''Segments'''[m] segments
<font color=green>// задаём левую и правую границы каждого из отрезков </font>
'''double''' curLeft = 0
'''double''' curRight = p
<font color=green>// разбиваем отрезок [0,1) на подотрезки, соответсвующие символам алфавита </font>
'''for''' i = 0 '''to''' m - 1
segments[i].left = curLeft
segments[i].right = curRight
curLeft = curRight
curRight = curRight + p
'''return''' segments
==== Перестройка подотрезков ====
'''map<char''', '''Segment'''> '''resizeSegments'''(alphabet : '''char'''[m], weight : '''map<char''', '''int>''', segments : '''map<char''', '''Segment>''')
<font color=green>// новая левая граница подотрезка</font>
'''double''' l = 0
<font color=green>// сумма весов символов алфавита</font>
'''int''' sum = 0
<font color=green>// подсчет суммы весов символов алфавита</font>
'''for''' i = 0 '''to''' m - 1
sum = sum + weight[i]
<font color=green>// перестроение подотрезков, для символов алфавита</font>
'''for''' i = 0 '''to''' m - 1
'''char''' c = alphabet[i]
segments[c].left = l
segments[c].right = l + (weight[c] / sum)
l = segments[c].right;
'''return''' segments
==== Определение начальных весов символов алфавита ====
'''map<char''', '''int> defineWeights'''(alphabet : '''set<char>'''):
'''map<char''', '''int>''' weight
<font color=green>// проход по всем символам алфавита и установка начального веса</font>
'''for''' i = 0 '''to''' m - 1
'''char''' c = alphabet[i]
weight[c] = 1
'''return''' weight
==== Кодирование строки ====
'''double''' '''adaptiveCoding'''(in : '''char'''[n], alphabet : '''set<char>'''):
'''int'''[m] weight = defineWeights(alphabet)
'''int'''[m] segments = defineSegments(alphabet)
<font color=green>// начальные границы отрезка</font>
'''double''' left = 0
'''double''' right = 1
'''for''' i = 0 '''to''' n - 1
'''char''' c = in[i]
<font color=green>// увеличение веса символа строки</font>
weight[c]++
<font color=green>// определение новых границ диапазона с искомым кодом, с учётом полученного символа c</font>
'''double''' newRight = left + (right - left) * segments[c].right
'''double''' newLeft = left + (right - left) * segments[c].left
left = newLeft
right = newRight
resizeSegments(alphabet, weight, segments)
'''return''' (left + right) / 2;
=== Алгоритм декодирования ===
При декодировании последовательности символов также используется множество весов <tex>w</tex> символов алфавита <tex>\sum</tex>. В начале работы алгоритма все веса символов равны <tex>1</tex>. На каждом шаге определяется интевал, содержащий данный код, по интервалу находится символ, который потом записывается в выходную последовательность. Вес полученного символа <tex>\alpha</tex> увеличивается на <tex>1</tex>. Отрезки, соответствующие символам алфавита, перестраиваются в зависимости от изменённых весов символов и размера текущего подотрезка. При получении символа конца последовательности или обработки нужного числа символов алгоритм завершает работу.
==== Декодирование ====
* <tex>\mathtt{code}</tex> {{---}} вещественное число, подаваемое на вход;
* <tex>\mathtt{n}</tex> {{---}} длина декодируемой строки;
* <tex>\mathtt{m}</tex> {{---}} мощность алфавита;
* <tex>\mathtt{weight}</tex> {{---}} веса символов алфавита;
* <tex>\mathtt{segments}</tex> {{---}} веса символов алфавита;
'''string''' '''decode('''code : '''double''', alphabet : '''set<char>''', '''int''' len):
'''map<char, int>''' weight = '''defineWeights('''alphabet''')'''
'''map<char, Segment>''' segments = '''defineSegments('''alphabet''')'''
'''string''' ans = ""
<font color=green>// декодирование строки</font>
'''for''' i = 0 '''to''' n - 1:
<font color=green>// поиск нужного символа исходной строки по текущему значению кода</font>
'''for''' j = 0 '''to''' m - 1:
'''char''' c = alphabet[j]
'''if''' code >= segments[c].left '''and''' code < segments[c].right
ans = ans + c
weight[c]++
<font color=green>// вычисление следующего значения кода, с учетом декодированного символа c</font>
code = (code - segments[c].left) / segments[c].right - segments[c].left)
<font color=green>// перестроение подотрезков, с учётом декодированного символа c </font>
resizeSegments(alphabet, weight, segments)
'''break;'''
'''return''' ans
=== Оценка минимальной и максимальной длины кода ===
{{Теорема
|id = th1.
|statement= При адаптивном арифметическом кодировании строки длины <tex>\mathtt{l}</tex>, символы которой принадлежат алфавиту мощности <tex>\mathtt{n}</tex>, полученный код будет лежать в диапазоне <tex>[\dfrac{(n-1)!}{(n+l-1)!}, \dfrac{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>\dfrac{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>\dfrac{w_{\alpha_k}}{n+k-1}</tex>.
В общем виде его можно представить так:
<tex>
L = \prod_{i=1}^l \dfrac{w_{\alpha_i}}{n+i-1}
</tex>
Знаменатель каждого следующего члена произведения будет увеличиваться на <tex>1</tex>, так как на каждом шаге увеличивается вес одного из символов алфавита.
Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов.
Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов.
В таком случае вес каждого из полученных символов будет равен <tex>1</tex>, а значение кода на каждом из шагов <tex>k=1, 2, \dots, l</tex> будет изменяться в <tex>\dfrac{1}{n+k-1}</tex> раз.
Соответственно, формула примет вид:
<tex>
L_{min} = \prod_{i=1}^l \dfrac{1}{n+i-1} = \dfrac{1}{\dfrac{(n+l-1)!}{(n-1)!}} = \dfrac{(n-1)!}{(n+l-1)!}
</tex>
Можно записать, используя формулы комбинаторики:
<tex>
L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!}
</tex>
==== Верхняя граница ====
Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов <tex>k=1, 2, \dots, l</tex> вес символа будет равен k, а значение кода будет изменяться в <tex>\dfrac{k}{n+k-1}</tex> раз.
Соответственно, формула будет иметь следующий вид:
<tex>
L_{max} = \prod_{i=1}^l \dfrac{i}{n+i-1} = \dfrac{l!(n-1)!}{(n+l-1)!}
</tex>
Можно записать, используя формулы комбинаторики:
<tex>
L_{max} = \dfrac{1}{\binom{n+l-1}{l}} = \dfrac{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>
}}
