Арифметическое кодирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 8 участников)
Строка 1: Строка 1:
Convex hull trick {{---}} один из методов оптимизации динамического программирования [[http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
+
{{Определение
                                                                                 
+
|definition=
                                                                                  ==Пример задачи, решаемой методом convex hull trick==
+
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
                                                                                  Рассмотрим задачу на ДП:
+
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.
                                                                                  {{Задача
+
}}
                                                                                  |definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
+
 
                                                                                  бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
+
== Принцип действия ==
                                                                                  срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость
+
При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
                                                                                  бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки
+
=== Кодирование ===
                                                                                  равна <tex>c_i</tex>.  Изначально пила заправлена.
+
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
                                                                                  Также известны следующие ограничения : <tex>c_n = 0, a_1 = 1, a_i</tex> возрастают, <tex>c_i</tex> убывают. Изначально пила заправлена.
+
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.  
                                                                                  (убывание и возрастание нестрогие)
+
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
                                                                                  }}
+
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
                                                                                  (Задача H с Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf])
+
# Повторим пункт <tex>(3)</tex> до конца входного потока.
                                                                                                                                    </noinclude>
+
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
                                                                                                                                    <includeonly>{{#if: {{{neat|}}}|
+
 
                                                                                                                                    <div style="background-color: #fcfcfc; float:left;">
+
=== Псевдокод ===
                                                                                                                                    <div style="background-color: #ddd;">'''Задача:'''</div>
+
 
                                                                                                                                    <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div>
+
*<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход;
                                                                                                                                    </div>|
+
*<math>\mathtt{n}\,</math> {{---}} длина исходного текста;
                                                                                                                                    <table border="0" width="100%">
+
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
                                                                                                                                    <tr><td style="background-color: #ddd">'''Задача:'''</td></tr>
+
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
                                                                                                                                    <tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr>
+
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
                                                                                                                                    </table>}}
+
*<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
                                                                                                                                    </includeonly>
+
**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
                                                                                                                                   
+
**<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
                                                                                                                                    ==Наивное решение==
+
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
                                                                                                                                    Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.
+
 
                                                                                                                                    Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i.</tex> будет срублено.
+
'''struct''' Segment:
                                                                                                                                    База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
+
    '''double''' left
                                                                                                                                    Переход динамики :  понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед  <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>, причем <tex>j \leqslant i - 1</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j \leqslant i - 1</tex> и попытаться использовать ответ для дерева намер <tex>j</tex>. Итак, пусть перед <tex>i</tex>-м деревом мы полностью срубили <tex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</tex>, а т.к. последнее дерево, которое мы срубили имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>-го дерева составит <tex>c[j]</tex>. Поэтому на сруб <tex>i</tex>-го дерева мы потратим <tex>a[i] \cdot c[j]</tex> монет. Также не стоит забывать, ситуацию, когда  <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет.
+
    '''double''' right
                                                                                                                                    Итогвая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])</tex>.
+
 
                                                                                                                                   
+
'''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
                                                                                                                                    Посмотрим на код выше описанного решения:
+
    '''Segment'''[m] segment
                                                                                                                                    '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n])
+
    '''double''' l = 0
                                                                                                                                    dp[1] = 0
+
    '''for''' i = 0 '''to''' m - 1
                                                                                                                                    dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
+
        segment[letters[i]].left = l
                                                                                                                                    '''for''' i = 1..n-1
+
        segment[letters[i]].right = l + probability[i]
                                                                                                                                    dp[i] = <tex>+\infty</tex>
+
        l = segment[letters[i]].right
                                                                                                                                    '''for''' j = 0..i-1
+
    '''return''' segment
                                                                                                                                    '''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
+
 
                                                                                                                                    dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
+
'''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]):
                                                                                                                                    '''return''' dp[n]
+
    '''Segment'''[m] segment = defineSegments(letters, probability)
                                                                                                                                    Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
+
    '''double''' left = 0
                                                                                                                                   
+
    '''double''' right = 1
                                                                                                                                    ==Ключевая идея оптимизации==
+
    '''for''' i = 0 '''to''' n - 1
                                                                                                                                    Для начала сделаем замену обозначений. Давайте обозначим <tex>dp[j]</tex> за <tex>b[j]</tex>, <tex>a[i]</tex> за <tex>x[i]</tex>, а <tex>c[j]</tex> за <tex>k[j]</tex>.
+
        '''char''' symb = s[i]
                                                                                                                                   
+
        '''double''' newRight = left + (right - left) * segment[symb].right
                                                                                                                                    Теперь формула приняла вид <tex>dp[i] = \min\limits_{j=0...i-1}(k[j] \cdot x[i] + b[j])</tex>. Выражение <tex>k[j] \cdot x + b[j]</tex> {{---}} это в точности уравнение прямой вида <tex>y = kx + b</tex>.
+
        '''double''' newLeft = left + (right - left) * segment[symb].left
                                                                                                                                   
+
        left = newLeft
                                                                                                                                    Сопоставим каждому <tex>j</tex>, обработанному ранее, прямую <tex>y[j](x) = k[j] \cdot x + b[j]</tex>. Из условия «<tex>c[i]</tex> убывают <tex>\Leftrightarrow  k[j]</tex> уменьшаются с номером <tex>j</tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :
+
        right = newRight
                                                                                                                                   
+
    '''return''' (left + right) / 2
                                                                                                                                    [[Файл:picture1convexhull.png]]
+
 
                                                                                                                                   
+
'''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
                                                                                                                                    Выделим множество точек <tex>(x0, y0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x0) < y0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, convex(x))</math> представляет собой выпуклую вверх функцию.
+
 
                                                                                                                                   
+
=== Декодирование ===
                                                                                                                                    ==Цель нижней огибающей множества прямых==
+
Алгоритм по вещественному числу восстанавливает исходный текст.
                                                                                                                                    Пусть мы считаем динамику для <tex>i</tex>-го дерева. Его задает <tex>x[i]</tex>. Итак, нам нужно для данного <tex>x[i]</tex> найти <tex>\min\limits_{j=0..i-1}(k[j] \cdot x[i] + b[i]) = \min\limits_{j=0..i-1}(y[j](x[i]))</tex>. Это выражение есть <math>convex(x[i])</math>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <tex>x = x[i]</tex>, можно найти бинарным поиском. Это потребует <tex>O(\log(n))</tex> времени на поиск такого <tex>j</tex>, что <tex>dp[i] = k[j] \cdot x[i] + b[j]</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять <tex>i</tex>-ю прямую после того, как мы посчитали <tex>b[i] = dp[i]</tex>.
+
# Выберем на отрезке <tex>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
                                                                                                                                   
+
# Нормируем подотрезок и вещественное число.
                                                                                                                                    Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex>k[]</tex> и <tex>b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>i</tex>-тую) прямую в множество. Пусть сейчас в множестве лежит <tex>sz</tex> прямых (нумерация с 1). Пусть <tex>(xL, yL)</tex> {{---}} точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(xR, yR)</tex> {{---}} точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>xL</tex> и <tex>xR</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(xL \geqslant xR)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе {{---}} остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо <tex>xL</tex> не станет меньше <tex>xR.</tex>
+
# Повторим пункты <tex>1</tex>{{---}}<tex>2</tex> до тех пор, пока не получим ответ.
                                                                                                                                   
+
 
                                                                                                                                    Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
+
=== Псевдокод ===
                                                                                                                                   
+
 
                                                                                                                                    [[Файл:picture2convexhull.png]]
+
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
                                                                                                                                    [[Файл:picture3convexhull.png]]
+
*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;
                                                                                                                                   
+
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
                                                                                                                                    {{Теорема
+
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
                                                                                                                                    |id=th1239.
+
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
                                                                                                                                    |statement=Алгоритм построения нижней огибающей множества прямых корректен.
+
*<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
                                                                                                                                    |proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя {{---}} предпоследнюю.
+
** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
                                                                                                                                   
+
** <math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
                                                                                                                                    Пусть <tex>Y(x) = Kx + B</tex> {{---}} уравнение новой прямой,  <tex>y[i](x) = K[i]x + B[i]</tex> {{---}} уравнения прямых множества. Тогда т.к. <tex>K < K[sz]</tex>, то при <tex>x \in [- \infty; xR]  : y[sz](x) <= Y(x)</tex>, а т.к. <tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [xL; + \infty]  : y[sz - 1](x) \geqslant y[sz](x)</tex>. Если <tex>xL < xR</tex>, то при <tex>x \in [xL; xR]  : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[xL; xR]</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex>xL > xR</tex>, то она ниже всех на отрезке <tex>[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества
+
** <math>\mathtt{character}\,</math> {{---}} значение символа.
                                                                                                                                    }}
+
 
                                                                                                                                   
+
'''struct''' Segment:
                                                                                                                                    ==Детали реализации:==
+
    '''double''' left
                                                                                                                                    Будем хранить 2 массива : <tex>front[]</tex> {{---}} <tex>x</tex>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <tex>x</tex> <tex>\in</tex> <tex>[front[i]; front[i + 1])</tex> ) и <tex>st[]</tex> {{---}} номера деревьев, соответствующих прямым (т.е. <tex>i</tex>-я прямая множества, где <tex>i</tex> <tex>\in</tex> <tex>[1; sz]</tex> соответствует дереву номер <tex>sz[i]</tex>). Также воспользуемся тем, что <tex>x[i] = a[i]</tex> возрастают (по условию задачи), а значит мы можем искать первое такое <tex>j</tex>, что <tex>x[i] \geqslant front[j]</tex> не бинарным поиском, а методом двух указателей за <tex>O(n)</tex> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые <tex>x[i]</tex>, а значит если <tex>k</tex>-я прямая пересекается с <tex>k+1</tex>-й в точке <tex>z +</tex> <tex>\alpha</tex> (<math>z</math>-целое,  <tex>\alpha</tex> <tex>\in</tex> <tex>[0;1)</tex>), то мы будем подставлять в их уравнения <tex>z</tex> или <tex>z + 1</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <tex>x = z+1</tex>
+
    '''double''' right
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
+
    '''char''' character
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ==Реализация==
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n])
+
'''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    st[1] = 1
+
    '''Segment'''[m] segment
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
+
    '''double''' l = 0
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
+
    '''for''' i = 0 '''to''' m - 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
+
        segment[i].left = l
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''for'''  i = 2..n 
+
        segment[i].right = l + probability[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
+
        segment[i].character = letters[i]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    pos = pos + 1
+
        l = segment[i].right
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    j = st[pos]
+
    '''return''' segment
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    dp[i] = K[j]<math>\cdot</math>a[i] + B[j]
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (i < n)  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
+
'''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''):
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
+
    '''Segment'''[m] segment = defineSegments(letters, probability)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
+
    '''string''' s = ""
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = -<tex>\infty</tex>  
+
    '''for''' i = 0 '''to''' n - 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''while''' ''true''
+
        '''for''' j = 0 '''to''' m - 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    j = st[sz]
+
            '''if''' code<tex>\small{~\geqslant~}</tex>segment[j].left '''and''' code < segment[j].right
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
+
                s += segment[j].character
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (x > from[sz]) '''break'''  <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
+
                code = (code – segment[j].left) / (segment[j].right – segment[j].left)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
+
                '''break'''
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    st[sz + 1] = i 
+
    '''return''' s
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[sz + 1] = x <font color=green>// добавили новую прямую </font >
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = sz + 1
+
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''return''' dp[n]
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Здесь функция <tex>\mathtt{divide}</tex>(a, b) возвращает нужное(*) округление a / b. Приведем её код :
+
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате знаменатель дроби не превысит <tex>n^{n}</tex>, а поскольку сумма всех вероятностей встречи символов равна <tex>1</tex>, полученная дробь будет находиться в промежутке <tex>[0; 1)</tex>.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b)
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    delta = 0
+
== Пример работы ==
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (a '''mod''' b ≠ 0) delta = 1
+
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' ((a > 0 '''and''' b > 0) '''or''' (a < 0 '''and''' b < 0)) '''return''' [a / b] + delta
+
=== Кодирование ===
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''return''' -[|a| / |b|]
+
{|class="wikitable"
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
+
!Символ||Частота появления
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Такая реализация будет работать за O(n).
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ==Динамический convex hull trick==
+
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Заметим, что условия на прямые, что <tex>k[i]</tex> возрастает/убывает и <tex>x[i]</tex> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой {{---}} отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf]).
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.142857</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за <tex>O(\log(n))</tex> можем найти  <tex>dp[i]</tex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <tex>O(1)</tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая {{---}} та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x1; x2]</tex>, где <tex>x1, x2 \in R</tex> {{---}} точки пересечения с некоторыми прямыми, причем <tex>x2</tex> не обязательно равно <tex>+ \infty</tex>
+
|}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Файл:picture4convexhull.png]]
+
[[Файл:Code_png.png|thumb|right|200px|Пример работы кодировщика ]]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
{|class="wikitable"
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Чтобы уметь вставлять прямую в множество будем хранить <math>std::set</math> (или любой аналог в других языках программирования) пар <tex>(k, st)</tex> = <tex>(коэффицент прямой, ее номер в глобальной нумерации)</tex>. Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
+
!Считанный символ||Левая граница отрезка||Правая граница отрезка
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Асимптотика решения составит <tex>O(\log(n))</tex> на каждый из <tex>n</tex> запросов «добавить прямую» + <tex>O(n\cdot\log(n))</tex> суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает <tex>O(\log(n))</tex> времени. Итого <math>O(n\cdot\log(n))</math>.
+
|||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>1</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      == Альтернативный подход ==
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Другой способ интерпретировать выражение <tex>dp[i] = \min\limits_{j=0...i-1}(c[j] \cdot a[i] + dp[j])</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : <tex>dp[j] + a[i] \cdot c[j] = (dp[j], c[j]) \cdot (1, a[i])</tex>, т.е. запишем как скалярное произведение векторов <tex>v[j] = (dp[j], c[j])</tex> и <tex >u[i] = (1, a[i])</tex >. Вектора  <tex >v[j] =  (dp[j], c[j])</tex> хотелось бы организовать так, чтобы за <tex >O(\log(n))</tex> находить вектор, максимизирующий выражение <tex>v[j] \cdot u[i]</tex>. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) <tex>j</tex> не может давать более оптимальное значение <tex>v[j] \cdot u[i]</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]</tex>, а ответ на запрос {{---}} это поиск <tex>v[j]</tex>, максимизирующего проекцию на <tex>u[i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>(0, 0)</tex> в <tex>(1, a[i])</tex>). Ее можно решить за <tex>O(\log(n))</tex> двумя бинарными или одним тернарным поиском
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Асимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>
+
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.489796</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Файл:picture5convexhull.png]]
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <math>3</math> вектора <math>a, b, c</math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow |[a-b, b-c]| < 0 </tex>, то либо <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>,  либо <tex>(c, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>.
+
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      {{Теорема
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |id=th12392.
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |statement=Если есть <tex>3</tex> вектора <tex>a, b, c</tex>, таких что <tex>|[a-b, b-c]| < 0</tex> то либо <math>(a, u) < (b, u)</math>, либо <math>(c, u) < (b, u)</math>, где вектор <math>u = (1; k)</math>.
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |proof=По условию теоремы известно, что <tex>|[a-b, b-c]| < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u) < (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} < c_{x} + k \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) < k \cdot (c_{y} - b_{y})</tex> и  <tex>(b, u) < (c, u) \Leftrightarrow b_{x}  + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) > k \cdot (b_{y} - a_{y})</tex>.
+
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = k</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.412093</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      }}
+
|}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
Код: <tex>0.411471</tex>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Из доказанной теоремы и следует корректность алгоритма.
+
 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
=== Декодирование ===
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ==См. также==
+
Код: <tex>0.411471</tex>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
+
[[Файл:decode1_png.png|thumb|right|200px|Пример работы декодировщика ]]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
{|class="wikitable"
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование
+
!Декодируемый символ||Код
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория:Дискретная математика и алгоритмы]]
+
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.411471</tex></p>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория: Динамическое программирование]]
+
|-
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория: Способы оптимизации методов динамического программирования]]
+
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.720074</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.520259</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.910454</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.373178</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.653061</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
 +
|}
 +
 
 +
'''Замечание:''' при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
 +
=== Декодирование (второй способ)===
 +
Код: <tex>0.411471</tex>
 +
[[Файл:decode2_png.png|thumb|right|200px|Пример работы декодировщика (второй способ) ]]
 +
{|class="wikitable"
 +
!Декодируемый символ||colspan="4" |Границы отрезка
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>||<p style="text-align:center;"><tex>0.857143</tex></p>||<p style="text-align:center;"><tex>1</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.489796 </tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.326531 </tex></p>||<p style="text-align:center;"><tex>0.419825 </tex></p>||<p style="text-align:center;"><tex>0.466472 </tex></p>||<p style="text-align:center;"><tex>0.489796 </tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.379842</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>||<p style="text-align:center;"><tex>0.417921 </tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>
 +
|-
 +
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.412093</tex></p>||<p style="text-align:center;"><tex>0.412714</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>
 +
 
 +
|}
 +
== Оценка длины кодового слова ==
 +
{{Теорема
 +
|statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
 +
 
 +
 
 +
 
 +
 
 +
||proof=Условные обозначения:
 +
*<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,
 +
*<tex>L</tex> {{---}} длина последнего отрезка в арифметическом кодировании <tex>s</tex>,
 +
*<tex>l</tex> {{---}} длина исходной строки <tex>s</tex>,
 +
*<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,
 +
*<tex>n</tex> {{---}} размер алфавита,
 +
*<tex>f_i</tex> {{---}} частота встречаемости символа,
 +
*<tex>p_i = \dfrac{f i}{l}</tex> {{---}} вероятность вхождения символа,
 +
*<tex>H(p_1 \ldots p_n)</tex> {{---}} энтропия случайного источника с частотами <tex>(p_1 \ldots p_n)</tex>.
 +
 
 +
 
 +
Пусть в результате арифметического кодирования мы получили число <tex>\dfrac{x}{2^q}</tex>, где <tex>q</tex> {{---}} количество бит в кодовом слове, т.е. <tex>q = A(s)</tex>.
 +
 
 +
Из алгоритма арифметического кодирования <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>.
 +
 
 +
Тогда <tex>A(s) = q \leq  -\log_2 L = -\log_2 \prod\limits_{i=1}^n p_{i}^{f_{i}} = -\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 </tex>.
 +
 
 +
Энтропия источника вычисляется по следующей формуле <tex>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>.
 +
 
 +
Следовательно, <tex>A(s) \leq 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>
 +
}}
 +
 
 +
== См. также ==
 +
* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]]
 +
* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]
 +
* [[Энтропия_случайного_источника | Энтропия случайного источника]]
 +
 
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Википедия {{---}} Арифметическое кодирование]
 +
* [https://en.wikipedia.org/wiki/Arithmetic_coding Wikipedia {{---}} Arithmetic coding]
 +
* [http://www.sernam.ru/cod_3.php Арифметическое кодирование]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/arithmetic-coding-2006 Визуализатор арифметического кодирования]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Теория вероятности]]
 +
[[Категория: Алгоритмы сжатия]]

Текущая версия на 19:36, 4 сентября 2022

Определение:
Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [math][0; 1)[/math]. Данный метод, как и алгоритм Хаффмана, является энтропийным, то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.


Принцип действия

При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу [math]a[/math] с вероятностью появления [math]p(a)[/math] допустимо ставить в соответствие код длины [math]-\log_2 p(a)[/math], следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).

Кодирование

На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.

  1. Рассмотрим отрезок [math][0; 1)[/math] на координатной прямой.
  2. Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
  3. Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
  4. Повторим пункт [math](3)[/math] до конца входного потока.
  5. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Псевдокод

  • [math]\mathtt{s}\,[/math] — текст, подаваемый на вход;
  • [math]\mathtt{n}\,[/math] — длина исходного текста;
  • [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
  • [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
  • [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
  • [math]\mathtt{Segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
    • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
  • [math]\mathtt{left}\,[/math], [math]\mathtt{right}\,[/math] — границы отрезка, содержащего возможный результат арифметического кодирования.
struct Segment:
    double left
    double right
Segment[m] defineSegments(letters: char[m], probability: double[m]):
   Segment[m] segment
   double l = 0
   for i = 0 to m - 1
       segment[letters[i]].left = l
       segment[letters[i]].right = l + probability[i]
       l = segment[letters[i]].right
   return segment
double arithmeticCoding(letters: char[m], probability: double[m], s: char[n]):
    Segment[m] segment = defineSegments(letters, probability)
    double left = 0
    double right = 1
    for i = 0 to n - 1
        char symb = s[i]
        double newRight = left + (right - left) * segment[symb].right
        double newLeft = left + (right - left) * segment[symb].left
        left = newLeft
        right = newRight
    return (left + right) / 2

Замечание: для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона [math][left; right][/math] число, содержащее наименьшее количество знаков в двоичной записи.

Декодирование

Алгоритм по вещественному числу восстанавливает исходный текст.

  1. Выберем на отрезке [math][0; 1)[/math], разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
  2. Нормируем подотрезок и вещественное число.
  3. Повторим пункты [math]1[/math][math]2[/math] до тех пор, пока не получим ответ.

Псевдокод

  • [math]\mathtt{code}\,[/math] — вещественное число, подаваемое на вход;
  • [math]\mathtt{n}\,[/math] — длина восстанавливаемого текста;
  • [math]\mathtt{m}\,[/math] — мощность алфавита исходного текста;
  • [math]\mathtt{letters[m]}\,[/math] — массив символов, составляющих алфавит исходного текста;
  • [math]\mathtt{probability[m]}\,[/math] — массив вероятностей обнаружения символа в тексте;
  • [math]\mathtt{segment}\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math], соответствующего конкретному символу на основе частотного анализа. Имеет поля:
    • [math]\mathtt{left}\,[/math] — левая граница подотрезка;
    • [math]\mathtt{right}\,[/math] — правая граница подотрезка;
    • [math]\mathtt{character}\,[/math] — значение символа.
struct Segment:
    double left
    double right
    char character
Segment[m] defineSegments(letters: char[n], probability: double[n]):
   Segment[m] segment
   double l = 0
   for i = 0 to m - 1
       segment[i].left = l
       segment[i].right = l + probability[i]
       segment[i].character = letters[i]
       l = segment[i].right
   return segment
string arithmeticDecoding(letters: char[m], probability: double[m], code: double, n: int):
    Segment[m] segment = defineSegments(letters, probability) 
    string s = ""
    for i = 0 to n - 1
        for j = 0 to m - 1
            if code[math]\small{~\geqslant~}[/math]segment[j].left and code < segment[j].right
                s += segment[j].character
                code = (code – segment[j].left) / (segment[j].right – segment[j].left)
                break
    return s

Замечание: кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.

Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, [math]\dfrac{1}{3}[/math]), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его [math]m[/math] подотрезков, кратных по длине [math]n[/math], а всего итераций [math]n[/math], в конечном результате знаменатель дроби не превысит [math]n^{n}[/math], а поскольку сумма всех вероятностей встречи символов равна [math]1[/math], полученная дробь будет находиться в промежутке [math][0; 1)[/math].

Пример работы

Рассмотрим в качестве примера строку [math]abacaba[/math]:

Кодирование

Символ Частота появления

[math]a[/math]

[math]0.571429[/math]

[math]b[/math]

[math]0.285714[/math]

[math]c[/math]

[math]0.142857[/math]

Пример работы кодировщика
Считанный символ Левая граница отрезка Правая граница отрезка

[math]0[/math]

[math]1[/math]

[math]a[/math]

[math]0[/math]

[math]0.571429[/math]

[math]b[/math]

[math]0.326531[/math]

[math]0.489796[/math]

[math]a[/math]

[math]0.326531[/math]

[math]0.419825[/math]

[math]c[/math]

[math]0.406497[/math]

[math]0.419825[/math]

[math]a[/math]

[math]0.406497[/math]

[math]0.414113[/math]

[math]b[/math]

[math]0.410849[/math]

[math]0.413025[/math]

[math]a[/math]

[math]0.410849[/math]

[math]0.412093[/math]

Код: [math]0.411471[/math]

Декодирование

Код: [math]0.411471[/math]

Пример работы декодировщика
Декодируемый символ Код

[math]a[/math]

[math]0.411471[/math]

[math]b[/math]

[math]0.720074[/math]

[math]a[/math]

[math]0.520259[/math]

[math]c[/math]

[math]0.910454[/math]

[math]a[/math]

[math]0.373178[/math]

[math]b[/math]

[math]0.653061[/math]

[math]a[/math]

[math]0.285714[/math]

Замечание: при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.

Декодирование (второй способ)

Код: [math]0.411471[/math]

Пример работы декодировщика (второй способ)
Декодируемый символ Границы отрезка

[math]a[/math]

[math]0[/math]

[math]0.571429[/math]

[math]0.857143[/math]

[math]1[/math]

[math]b[/math]

[math]0[/math]

[math]0.326531[/math]

[math]0.489796 [/math]

[math]0.571429[/math]

[math]a[/math]

[math]0.326531 [/math]

[math]0.419825 [/math]

[math]0.466472 [/math]

[math]0.489796 [/math]

[math]c[/math]

[math]0.326531[/math]

[math]0.379842[/math]

[math]0.406497[/math]

[math]0.419825[/math]

[math]a[/math]

[math]0.406497[/math]

[math]0.414113[/math]

[math]0.417921 [/math]

[math]0.419825[/math]

[math]b[/math]

[math]0.406497[/math]

[math]0.410849[/math]

[math]0.413025[/math]

[math]0.414113[/math]

[math]a[/math]

[math]0.410849[/math]

[math]0.412093[/math]

[math]0.412714[/math]

[math]0.413025[/math]

Оценка длины кодового слова

Теорема:
При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
Доказательство:
[math]\triangleright[/math]

Условные обозначения:

  • [math]A(s)[/math] — размер кодового слова [math]s[/math],
  • [math]L[/math] — длина последнего отрезка в арифметическом кодировании [math]s[/math],
  • [math]l[/math] — длина исходной строки [math]s[/math],
  • [math]A(s)[/math] — размер кодового слова [math]s[/math],
  • [math]n[/math] — размер алфавита,
  • [math]f_i[/math] — частота встречаемости символа,
  • [math]p_i = \dfrac{f i}{l}[/math] — вероятность вхождения символа,
  • [math]H(p_1 \ldots p_n)[/math] — энтропия случайного источника с частотами [math](p_1 \ldots p_n)[/math].


Пусть в результате арифметического кодирования мы получили число [math]\dfrac{x}{2^q}[/math], где [math]q[/math] — количество бит в кодовом слове, т.е. [math]q = A(s)[/math].

Из алгоритма арифметического кодирования [math] L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math].

Тогда [math]A(s) = q \leq -\log_2 L = -\log_2 \prod\limits_{i=1}^n p_{i}^{f_{i}} = -\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 [/math].

Энтропия источника вычисляется по следующей формуле [math]H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i[/math].

Следовательно, [math]A(s) \leq l \cdot H(p_1 \ldots p_n)[/math].
[math]\triangleleft[/math]

Адаптивное арифметическое кодирование

Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, что декодировщику не нужно передавать вероятностные оценки для символов, он будет строить их по мере декодирования сообщения, что может сильно сократить вес такого сообщения.

Алгоритм кодирования

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

Псевдокод алгоритма

  • [math]\mathtt{in}[/math] — текст, подаваемый на вход
  • [math]\mathtt{n}[/math] — длина исходного текста
  • [math]\mathtt{Segment}[/math] — структура, задающая подотрезок отрезка [math][0, 1)[/math], соответствующая конкретному символу. Имеет следующие поля:
    • [math] \mathtt{left} [/math] — левая граница подотрезка
    • [math] \mathtt{right} [/math] — правая граница подотрезка
  • [math] \mathtt{m} [/math] — мощность алфавита
  • [math] \mathtt{weight} [/math] — веса символов алфавита
  • [math] \mathtt{segments} [/math] — набор подотрезков, соответствующих символам алфавита
  • [math] \mathtt{left, right} [/math] — границы отрезка, содержащие возможный результат арифметического кодирования
  • [math] \mathtt{getAlphabet(in : char[n])}[/math] — функция возвращает множество различных символов в тексте [math] \mathtt{in} [/math]

Подотрезок

struct Segment:
    double left;
    double right;

Определение начальных границ подотрезков

map<char, Segment> defineSegments(set<char> alphabet):
    // определяем размер подотрезков 
    double p = 1 / alphabet.size()    
    Segments[m] segments
    // задаём левую и правую границы каждого из отрезков 
    double curLeft = 0  
    double curRight = p
    // разбиваем отрезок [0,1) на подотрезки, соответсвующие символам алфавита 
    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>)
   // новая левая граница подотрезка
   double l = 0    
   // сумма весов символов алфавита
   int sum = 0    
   //  подсчет суммы весов символов алфавита
   for i = 0 to m - 1  
       sum = sum + weight[i] 
   // перестроение подотрезков, для символов алфавита
   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
   // проход по всем символам алфавита и установка начального веса
   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)
   // начальные границы отрезка
   double left = 0      
   double right = 1
   for i = 0 to n - 1
       char c = in[i]
       // увеличение веса символа строки
       weight[c]++  
       // определение новых границ диапазона с искомым кодом, с учётом полученного символа c
       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;

Алгоритм декодирования

При декодировании последовательности символов также используется множество весов [math]w[/math] символов алфавита [math]\sum[/math]. В начале работы алгоритма все веса символов равны [math]1[/math]. На каждом шаге определяется интевал, содержащий данный код, по интервалу находится символ, который потом записывается в выходную последовательность. Вес полученного символа [math]\alpha[/math] увеличивается на [math]1[/math]. Отрезки, соответствующие символам алфавита, перестраиваются в зависимости от изменённых весов символов и размера текущего подотрезка. При получении символа конца последовательности или обработки нужного числа символов алгоритм завершает работу.

Декодирование

  • [math]\mathtt{code}[/math] — вещественное число, подаваемое на вход;
  • [math]\mathtt{n}[/math] — длина декодируемой строки;
  • [math]\mathtt{m}[/math] — мощность алфавита;
  • [math]\mathtt{weight}[/math] — веса символов алфавита;
  • [math]\mathtt{segments}[/math] — веса символов алфавита;
string decode(code : double, alphabet : set<char>, int len):
   map<char, int> weight = defineWeights(alphabet)
   map<char, Segment> segments = defineSegments(alphabet)
   string ans = ""
   // декодирование строки
   for i = 0 to n - 1:
       // поиск нужного символа исходной строки по текущему значению кода
       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]++
               // вычисление следующего значения кода, с учетом декодированного символа c
               code = (code - segments[c].left) / segments[c].right - segments[c].left)
               // перестроение подотрезков, с учётом декодированного символа c 
               resizeSegments(alphabet, weight, segments)
               break;
   return ans

Оценка минимальной и максимальной длины кода

Теорема:
При адаптивном арифметическом кодировании строки длины [math]\mathtt{l}[/math], символы которой принадлежат алфавиту мощности [math]\mathtt{n}[/math], полученный код будет лежать в диапазоне [math][\dfrac{(n-1)!}{(n+l-1)!}, \dfrac{l!(n-1)!}{(n+l-1)!}][/math]
Доказательство:
[math]\triangleright[/math]

Во время кодирования строки алгоритм выбирает необходимый подотрезок, увеличивает вес символа и перестраивает подотрезки. Пусть [math]L[/math] — результат кодирования строки длины [math]l[/math], использующей алфавит длины [math]n[/math]. Код [math]L[/math] формируется следующим образом: на каждом из шагов [math]k=1, 2, \dots, l[/math] он изменяется в [math]\dfrac{w_{\alpha_k}}{n+k-1}[/math] раз. На каждом шаге [math]k[/math]-й символ [math]\alpha[/math] будет иметь вес [math]\alpha_k[/math] (каждый раз больший на [math]1[/math], потому что алгоритм адаптивный). Значит, на каждом шаге суммарный вес символов будет увеличиваться на [math]1[/math], т.е. на шаге [math]k[/math] суммарный вес символов будет равен [math]n+k-1[/math] Во время перестроения подотрезков, по алгоритму, каждому символу ствавится в соответствие подотрезок длины [math]\dfrac{w_{\alpha_k}}{n+k-1}[/math].

В общем виде его можно представить так:

[math] L = \prod_{i=1}^l \dfrac{w_{\alpha_i}}{n+i-1} [/math]

Знаменатель каждого следующего члена произведения будет увеличиваться на [math]1[/math], так как на каждом шаге увеличивается вес одного из символов алфавита. Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов. Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов. В таком случае вес каждого из полученных символов будет равен [math]1[/math], а значение кода на каждом из шагов [math]k=1, 2, \dots, l[/math] будет изменяться в [math]\dfrac{1}{n+k-1}[/math] раз.

Соответственно, формула примет вид:

[math] 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)!} [/math]

Можно записать, используя формулы комбинаторики:

[math] L_{min} = \dfrac{1}{{\binom{l}{n+l-1}}l!} = \dfrac{1}{C_{n+l-1}^{l}l!} [/math]

Верхняя граница

Для того, чтобы максимизировать произведение, необходимо увеличить числитель каждого члена произведения. Этого можно достичь, если передать на вход алгоритму строку, состоящую из одинаковых символов. В таком случае, на каждом из шагов [math]k=1, 2, \dots, l[/math] вес символа будет равен k, а значение кода будет изменяться в [math]\dfrac{k}{n+k-1}[/math] раз.

Соответственно, формула будет иметь следующий вид:

[math] L_{max} = \prod_{i=1}^l \dfrac{i}{n+i-1} = \dfrac{l!(n-1)!}{(n+l-1)!} [/math]

Можно записать, используя формулы комбинаторики:

[math] L_{max} = \dfrac{1}{\binom{n+l-1}{l}} = \dfrac{1}{C_{n+l-1}^{l}} [/math]
[math]\triangleleft[/math]
Утверждение:
При адаптивном арифметическом кодировании строки длины [math]l[/math], символы которой принадлежат алфавиту мощности [math]n[/math], количество бит, необходимых для кодирования сообщения будет лежать в диапазоне [math][-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}][/math]
[math]\triangleright[/math]

Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:

[math] log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1} [/math]

Все коды лежат в диапазоне [math][0, 1)[/math].

Таким образом:

Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:

[math] log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1} [/math]

Минимальное число бит будет затрачено в случае записи кода максимального размера:

[math] log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i} [/math]
[math]\triangleleft[/math]

См. также

Источники информации