Изменения

Convex hull trick {{Определение |definition='''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} один алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из методов оптимизации динамического программирования отрезка <tex>[[http:0; 1)<//neerctex>.ifmo.ru/wiki/index.php?title=Динамическое_программирование Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], использующий идею выпуклой оболочкито есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Позволяет улучшить ассимптотику решения некоторых задачьАрифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, решемых методом динамического программирования для данных с неравномерными распределениями вероятностей кодируемых символов.}}  == Принцип действия ==При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <mathtex>O(n^2)a</mathtex> до с вероятностью появления <tex>Op(n\cdot\log(n)a)</tex>. Техника впервые появилась допустимо ставить в 1995 году соответствие код длины <tex>-\log_2 p(задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированиюa). Массовую известность получила после IOI (международной олимпиады по программированию для школьников</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки) 2002. ==Пример задачи, решаемой методом convex hull trick= Кодирование === На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.# Рассмотрим задачу на ДП: {{Задача |definition = Есть <math>n</math> деревьев с высотами отрезок <tex>a_1, a_2, \dots, a_n[0; 1)</tex> (в метрах)на координатной прямой. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления. Но пила устроена так# Считаем символ из входного потока и рассмотрим отрезок, что она может спиливать только по 1 метру от дерева, к которому ее применилисоответствующий этому символу. Также после срубленного метра (любого дерева) пилу нужно заправлятьРазделим этот отрезок на части, платя за бензин определенной кол-во монетпропорциональные частотам встречаемости символов. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен # Повторим пункт <tex>i(3)</tex>до конца входного потока.# Выберем любое число из получившегося отрезка, то цена заправки равна <tex>c_i</tex>. Изначально пила заправленакоторое и будет результатом арифметического кодирования. Также известны следующие ограничения : <tex>c_n === Псевдокод == 0, a_1 = 1, a_i *</texmath> возрастают\mathtt{s}\, <tex>c_i</texmath> убывают. Изначально пила заправлена. (убывание и возрастание нестрогие) {{---}}текст, подаваемый на вход; (Задача H с Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf]) *</noincludemath> \mathtt{n}\,<includeonly/math>{{#if: {---}} длина исходного текста;*<math>\mathtt{m}\,</math> {{neat|}---}}| <div style="background-color: #fcfcfcмощность алфавита исходного текста; float:left;"> *<div style="background-color: #ddd;"math>'''Задача:'''\mathtt{letters[m]}\,</div> <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;"math>{{{definition---}}}</div>массив символов, составляющих алфавит исходного текста; *</divmath>| \mathtt{probability[m]}\,<table border="0" width="100%"/math>{{---}} массив вероятностей обнаружения символа в тексте; *<trmath>\mathtt{Segment}\,<td style="background/math> {{---color: #ddd">'''Задача:'''}} структура, задающая подотрезок отрезка </tdtex>[0; 1)</trtex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля: **<trmath>\mathtt{left}\,<td style="border:1px dashed #2f6fab; padding: 8px; background/math> {{--color: #fcfcfc; font-style: italic}} левая граница подотрезка;"**<math>\mathtt{right}\,</math> {{definition}---}}правая граница подотрезка;*</tdmath>\mathtt{left}\,</trmath> , </tablemath>\mathtt{right}} \,</includeonlymath>{{---}} границы отрезка, содержащего возможный результат арифметического кодирования.  '''struct''' Segment: '''double''' left '''double''' right ==Наивное решение== Сначала заметим важный факт '''Segment'''[m] defineSegments(letters: т.к. <tex>c'''char'''[m], probability: '''double'''[im]</tex> убывают (нестрого) и <tex>c: '''Segment'''[nm] segment '''double''' l = 0</tex>, то все <tex>c '''for''' i = 0 '''to''' m - 1 segment[letters[i]</tex> неотрицательны].left = l Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c segment[letters[i]].right = l + probability[ni] l = 0</tex>). Посчитаем следующую динамику : <tex>dpsegment[letters[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i.</tex> будет срублено.].right '''return''' segment  База динамики '''double''' arithmeticCoding(letters: <tex>dp'''char'''[1m], probability: '''double'''[m] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1s: '''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]. Поэтому перед <tex>i</tex>right '''double''' newLeft = left + (right -м деревом мы обязательно срубили какое-то left) * segment[symb].left left = newLeft right = newRight '''return''' (left + right) / 2 '''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>j[left; right]</tex>-ечисло, причем <содержащее наименьшее количество знаков в двоичной записи. === Декодирование ===Алгоритм по вещественному числу восстанавливает исходный текст.# Выберем на отрезке <tex>j \leqslant i - [0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Поэтому чтобы найти Символ, соответствующий этому подотрезку, дописываем в ответ.# Нормируем подотрезок и вещественное число.# Повторим пункты <tex>dp[i]1</tex> нужно перебрать все {{---}}<tex>1 \leqslant j \leqslant i - 12</tex> и попытаться использовать до тех пор, пока не получим ответ для дерева намер . === Псевдокод === *<texmath>j\mathtt{code}\,</texmath>. Итак, пусть перед {{---}} вещественное число, подаваемое на вход;*<texmath>i\mathtt{n}\,</texmath>{{---м деревом мы полностью срубили }} длина восстанавливаемого текста;*<texmath>j\mathtt{m}\,</texmath>{{---е, причем высота }} мощность алфавита исходного текста;*<texmath>i\mathtt{letters[m]}\,</texmath>{{--го дерева составляет -}} массив символов, составляющих алфавит исходного текста;*<texmath>a\mathtt{probability[im]}\,</texmath>, а т.к. последнее дерево, которое мы срубили имеет индекс {{---}} массив вероятностей обнаружения символа в тексте; *<tex>j</texmath>\mathtt{segment}\, то стоимость каждого метра <tex>i</texmath>{{-го дерева составит --}} структура, задающая подотрезок отрезка <tex>c[j]0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Поэтому на сруб Имеет поля:** <texmath>i\mathtt{left}\,</texmath>{{--го дерева мы потратим -}} левая граница подотрезка;** <texmath>a[i] \cdot c[j]mathtt{right}\,</texmath> монет. Также не стоит забывать, ситуацию, когда {{---}} правая граница подотрезка;** <texmath>j\mathtt{character}\,</texmath>{{---е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет}} значение символа. Итогвая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])</tex>. Посмотрим на код выше описанного решения: '''intstruct''' <tex>\mathtt{simpleDP}</tex>(Segment: '''double''' left '''double''' right '''char''' character  '''intSegment''' a[nm], defineSegments(letters: '''intchar''' c[n]) dp, probability: '''double'''[1n] = 0): dp '''Segment'''[2m] segment '''double''' l = dp[3] = ... = dp[n] = <tex>\infty</tex>0 '''for''' i = 1..n0 '''to''' m -1 dp segment[i] .left = <tex>l segment[i].right = l +\infty</tex>probability[i] segment[i].character = letters[i] l = segment[i].right '''forreturn''' j = 0..i-1segment  '''ifstring''' arithmeticDecoding(dpletters: '''char'''[jm] + a, probability: '''double'''[i] <tex>\cdot</tex> c[j] < dp[im], code: '''double''', n: '''int'''): dp '''Segment'''[im] segment = dp[j] + a[i] <tex>\cdot</tex> c[j]defineSegments(letters, probability) '''returnstring''' dp[n]s = "" Нетрудно видеть, что такая динамика работает за <tex>O( '''for''' i = 0 '''to''' n^2)</tex>.- 1 ==Ключевая идея оптимизации= '''for''' j =0 '''to''' m - 1 Для начала сделаем замену обозначений. Давайте обозначим '''if''' code<tex>dp[j]\small{~\geqslant~}</tex> за <tex>bsegment[j].left '''and''' code </tex>, <tex>asegment[ij]</tex> за <tex>x.right s += segment[ij]</tex>, а <tex>c.character code = (code – segment[j]<.left) /tex> за <tex>k(segment[j]</tex>. Теперь формула приняла вид <tex>dpright – segment[ij] = \min\limits_{j=0.left) '''break''' '''return''' s '''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу.Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.i '''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-1за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}}поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (k[j] например, <tex>\cdot x[i] + b[j])dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. Выражение В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>k[j] \cdot x + b[j]m</tex> {{---}} это подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в точности уравнение прямой вида конечном результате знаменатель дроби не превысит <tex>y = kx + bn^{n}</tex>. Сопоставим каждому , а поскольку сумма всех вероятностей встречи символов равна <tex>j1</tex>, обработанному ранее, прямую полученная дробь будет находиться в промежутке <tex>y[j](x0; 1) = k[j] \cdot x + b[j]<</tex>. Из условия « == Пример работы ==Рассмотрим в качестве примера строку <tex>c[i]abacaba</tex> убывают <tex>\Leftrightarrow k[j]</:=== Кодирование ==={|class="wikitable"!Символ||Частота появления|-|<p style="text-align:center;"><tex> уменьшаются с номером a</tex>j</p>||<p style="text-align:center;"><tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент0. Давайте нарисуем несколько таких прямых :571429</tex></p> |- [[Файл|<p style="text-align:picture1convexhull.png]] Выделим множество точек center;"><tex>(x0, y0)b</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</texp>, такой что ||<texp style="text-align:center;">y’(x0) < y0</tex>0. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)285714</tex>». Видно, что множество точек <math>(x, convex(x))</mathp> представляет собой выпуклую вверх функцию. |- |<p style==Цель нижней огибающей множества прямых== Пусть мы считаем динамику для "text-align:center;"><tex>ic</tex>-го дерева. Его задает <tex/p>x[i]||</texp style="text-align:center;">. Итак, нам нужно для данного <tex>x[i]0.142857</tex> найти <tex/p>\min\limits_{j=0..i-1}(k|}[j] \cdot x[iФайл:Code_png.png|thumb|right|200px|Пример работы кодировщика ] + b[i]) = \min\limits_{j|class=0..i"wikitable"!Считанный символ||Левая граница отрезка||Правая граница отрезка|-|||<p style="text-1}(y[j](x[i]))align:center;"></tex>. Это выражение есть 0<math/tex>convex(x[i])</mathp>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую ||<tex>x p style= x[i]</tex"text-align:center;">, можно найти бинарным поиском. Это потребует <tex>O(\log(n))1</tex> времени на поиск такого <tex>j</texp>, что |-|<texp style="text-align:center;">dp[i] = k[j] \cdot x[i] + b[j]</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять a</tex>i</texp>||<p style="text-align:center;">-ю прямую после того, как мы посчитали <tex>b[i] = dp[i]0</tex>. Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex/p>||<p style="text-align:center;">k[]</tex> и 0.571429</tex>b[]</texp>|-|<p style="text-align:center;">, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>ib</tex></p>||<p style="text-тую) прямую в множество. Пусть сейчас в множестве лежит align:center;"><tex>sz0.326531</tex> прямых (нумерация с 1). Пусть </p>||<p style="text-align:center;"><tex>(xL, yL)0.489796</tex> {{---}} точка пересечения <tex/p>sz |- 1|</texp style="text-align:center;">-й прямой множества и <tex>sza</tex>-й, а <tex</p>(xR, yR)||</tex> {{p style="text---}} точка пересечения новой прямой, которую мы хотим добавить в конец множества и <texalign:center;">sz</tex>-й0. Нас будут интересовать только их 326531</tex>x</texp>||<p style="text-овые координаты <texalign:center;">xL</tex> и 0.419825</tex>xR</texp>, соответственно. Если оказалось, что новая прямая пересекает |-|<texp style="text-align:center;">sz</tex>-ю прямую выпуклой оболочки позже, чем c</tex>sz</texp>||<p style="text-я align:center;"><tex>sz - 10.406497</tex></p>||<p style="text-ю, т.еalign:center;"><tex>0. 419825</tex>(xL \geqslant xR)</p>|-|<p style="text-align:center;"><tex>, то a</tex>sz</texp>||<p style="text-ю удалим из нашего множества, иначе {{---}} остановимсяalign:center;"><tex>0. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо 406497</tex>xL</texp>||<p style="text-align:center;"> не станет меньше <tex>xR0.414113</tex></p> |- Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно |<p style="text-align:center;"><mathtex>1b</mathtex> раз добавится в стек и максимум <math/p>1||</mathp style="text-align:center;"> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)0.410849</tex> суммарно. [[Файл</p>||<p style="text-align:picture2convexhullcenter;"><tex>0.png]]413025</tex></p> [[Файл:picture3convexhull.png]] {{Теорема |id=th1239.- |statement<p style=Алгоритм построения нижней огибающей множества прямых корректен. |proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя {{"text---}} предпоследнюю. Пусть align:center;"><tex>Y(x) = Kx + Ba</tex> {{</p>||<p style="text---}} уравнение новой прямой, <texalign:center;">y[i](x) = K[i]x + B[i]</tex> {{---}} уравнения прямых множества. Тогда т.к0. 410849</tex>K < K[sz]</texp>, то при ||<tex>x \in [p style="text- \inftyalign:center; xR] : y[sz](x) "><= Y(x)</tex>, а т.к0. 412093</tex> K[sz] < K[sz - 1]</texp>, то при |}Код: <tex>x \in [xL; + \infty] : y[sz - 1](x) \geqslant y[sz](x)0.411471</tex>. Если  === Декодирование ===Код: <tex>xL < xR0.411471</tex>, то при <tex>x \in [[xL; xR] Файл: y[sz - 1] \geqslant y[szdecode1_png.png|thumb|right|200px|Пример работы декодировщика ](x) и Y(x) \geqslant y[sz](x){|class="wikitable"!Декодируемый символ||Код|-|<p style="text-align:center;"><tex>a</tex>, т.е. на отрезке <tex/p>[xL||<p style="text-align:center; xR]"></tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве0. Если же 411471</tex>xL > xR</texp>, то она ниже всех на отрезке |-|<texp style="text-align:center;">[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества }} ==Детали реализации:== Будем хранить 2 массива : b</tex>front[]</texp> {{||<p style="text---}} align:center;"><tex>x0.720074</tex></p>|-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i|<p style="text-я прямая совпадает с выпуклой оболочкой текущего множества прямых при align:center;"><tex>xa</tex> <tex/p>||<p style="text-align:center;">\in</tex> 0.520259</tex>[front[i]; front[i + 1])</texp>|-|<p style="text-align:center;"> ) и <tex>st[]c</tex> {{</p>||<p style="text---}} номера деревьев, соответствующих прямым (т.е. align:center;"><tex>i0.910454</tex>-я прямая множества, где <tex/p>i|-|</texp style="text-align:center;"> <tex>\ina</tex> <tex/p>[1||<p style="text-align:center; sz]"></tex> соответствует дереву номер 0.373178</tex>sz[i]</texp>). Также воспользуемся тем, что |-|<texp style="text-align:center;">x[i] = a[i]</tex> возрастают (по условию задачи), а значит мы можем искать первое такое b</tex>j</texp>, что ||<texp style="text-align:center;">x[i] \geqslant front[j]</tex> не бинарным поиском, а методом двух указателей за 0.653061</tex>O(n)</texp> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х|-|<p style="text-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые align:center;"><tex>x[i]a</tex>, а значит если <tex>k</texp>-я прямая пересекается с ||<tex>k+1</tex>p style="text-й в точке <texalign:center;">z +</tex> <tex>\alpha0.285714</tex> (<math>z</mathp>-целое, <tex>\alpha|} '''Замечание:''' при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.=== Декодирование (второй способ)===Код: </tex> <tex>\in0.411471</tex> <tex>[[0;1Файл:decode2_png.png|thumb|right|200px|Пример работы декодировщика (второй способ)]]{|class="wikitable"!Декодируемый символ||colspan="4" |Границы отрезка|-|</texp style="text-align:center;">), то мы будем подставлять в их уравнения <tex>za</tex> или </p>||<p style="text-align:center;"><tex>z + 10</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с </p>||<p style="text-align:center;"><tex>x = z+10.571429</tex> ==Реализация=</p>||<p style= '''int''' "text-align:center;"><tex>\mathtt{ConvexHullTrick}0.857143</tex>('''int''' a[n], '''int''' c[n])</p>||<p style="text-align:center;"><tex>1</tex></p> st[1] = 1|- from[1] |<p style= "text-align:center;"><tex>\inftyb</tex><font color=green/p>// первая прямая покрывает все x||<p style="text-ы, начиная с -∞ align:center;"></fonttex> sz = 1 0<font color=green/tex>// текущий размер выпуклой оболочки </fontp> pos = 1 ||<font colorp style=green"text-align:center;"><tex>0.326531<// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] tex></font p> '''for''' i ||<p style= 2"text-align:center;"><tex>0..n '''while''' (front[pos] 489796 </tex>< x[i]) /p>||<font colorp style=green"text-align:center;"><tex>0.571429</tex></ метод 1 указателя (ищем первое pos, такое что x[i] покрывается p>|-|<p style="областью действияtext-align:center;" st[pos]-той прямой ></font tex> pos = pos + 1 j = st[pos] dp[i] = K[j]a<math/tex>\cdot</mathp>a[i] + B[j] '''if''' (i ||< n) p style="text-align:center;"><font color=greentex>0.326531 <// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку tex></font p> K[i] ||<p style= c[i] "text-align:center;"><font color=greentex>0.419825 <// наши переобозначения переменных tex></font p> B[i] = dp[i] ||<font colorp style=green"text-align:center;">// наши переобозначения переменных </font tex> x 0.466472 </tex></p>||<p style= "text-align:center;"><tex>\infty0.489796 </tex></p> '''while''' ''true'' |- j |<p style= st[sz] x = divide(B[j] - B[i], K[i] - K[j]) "text-align:center;"><font color=greentex>c<// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) tex></font p> '''if''' (x ||<p style="text-align:center;"> from[sz]) '''break''' <font color=greentex>0.326531<// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" tex></font p> sz ||<p style= sz "text- 1align:center;"><font color=greentex>0.379842<// удаляем последнюю прямую, если она лишняя tex></font p> st[sz + 1] = i from[sz + 1] = x ||<font colorp style=green"text-align:center;">// добавили новую прямую </font tex> sz 0.406497</tex></p>||<p style= sz + 1 '''return''' dp[n] Здесь функция "text-align:center;"><tex>\mathtt{divide}0.419825</tex>(a, b) возвращает нужное(*) округление a </ b. Приведем её код p>|-|<p style="text-align: '''int''' center;"><tex>\mathtt{divide}a</tex>('''int''' a, '''int''' b) delta </p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style= "text-align:center;"><tex>0 '''if''' (a '''mod''' b ≠ 0) delta .414113</tex></p>||<p style= 1 '''if''' ((a "text-align:center;"> 0 '''and''' b <tex> 0) '''or''' (a .417921 < 0 '''and''' b /tex>< 0)) '''return''' [a / b] + delta '''return''' -[p>|a| / |b|] Такая реализация будет работать за O(n). <p style==Динамический convex hull trick== Заметим, что условия на прямые, что "text-align:center;"><tex>k[i]0.419825</tex> возрастает/убывает и <tex>x[i]</texp> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой {{-|-|<p style="text-}} отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016[httpalign:center;"><tex>b</tex></neerc.ifmo.ru/school/campp>||<p style="text-2016/problems/20160318a.pdf]). Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за align:center;"><tex>O(\log(n))0.406497</tex> можем найти <tex/p>dp[i]||</texp style="text-align:center;">, но теперь вставку <tex>i0.410849</tex></p>||<p style="text-й прямой в оболочку уже нельзя выполнить описанным ранее способом за align:center;"><tex>0.413025</tex>O(1)</p>||<p style="text-align:center;"><tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис0. 4 : красная прямая {{-414113</tex></p>|-|<p style="text-}} та, которую мы хотим вставить в наше множество). Более формально align: теперь наша новая прямая будет ниже остальных при center;"><tex>x \in [x1; x2]a</tex>, где <tex>x1, x2 \in R</texp> {{||<p style="text---}} точки пересечения с некоторыми прямыми, причем align:center;"><tex>x20.410849</tex> не обязательно равно </p>||<p style="text-align:center;"><tex>+ \infty0.412093</tex> [[Файл:picture4convexhull.png]] Чтобы уметь вставлять прямую в множество будем хранить <math/p>||<p style="text-align:center;">std::set</mathtex> (или любой аналог в других языках программирования) пар 0.412714</tex>(k, st)</texp> ||<p style= "text-align:center;"><tex>(коэффицент прямой, ее номер в глобальной нумерации)0.413025</tex>. Когда приходит новая прямая, ищем последнюю прямую </p> |}== Оценка длины кодового слова =={{Теорема |statement=При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с меньшим угловым коэффицентомчастотами, чем у той прямойравными долям вхождения символа в строку, которую мы хотим добавить в множествоумноженной на длину строки. Поиск такой прямой занимает     ||proof=Условные обозначения:*<tex>O(\logA(n)s)</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа). Асимптотика решения составит {{---}} размер кодового слова <tex>O(\log(n))s</tex> на каждый из ,*<tex>nL</tex> запросов «добавить прямую» + <{{---}} длина последнего отрезка в арифметическом кодировании <tex>O(n\cdot\log(n))s</tex> суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает *<tex>O(\log(n))l</tex> времени. Итого {{---}} длина исходной строки <mathtex>O(n\cdot\log(n))s</mathtex>., == Альтернативный подход == Другой способ интерпретировать выражение *<tex>A(s)</tex>dp[i] = \min\limits_{j=0...i{---1}(c[j] \cdot a[i] + dp[j])} размер кодового слова <tex>s</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : *<tex>n</tex>dp[j] + a[i] \cdot c[j] = (dp[j]{{---}} размер алфавита, c[j]) \cdot (1, a[i])*<tex>f_i</tex>{{---}} частота встречаемости символа, т.е. запишем как скалярное произведение векторов *<tex>v[j] p_i = (dp[j], c[j])\dfrac{f i}{l}</tex> и {{---}} вероятность вхождения символа,*<tex >u[i] = H(1, a[i]p_1 \ldots p_n)</tex >. Вектора {{---}} энтропия случайного источника с частотами <tex >v[j] = (dp[j], c[j](p_1 \ldots p_n)</tex> хотелось бы организовать так, чтобы за .   Пусть в результате арифметического кодирования мы получили число <tex >O(\log(n))dfrac{x}{2^q}</tex> находить вектор, максимизирующий выражение где <tex>v[j] \cdot u[i]q</tex>{{---}} количество бит в кодовом слове, т. Посмотрим на рис. 5е. Заметим интуитивно очевидный факт : красная точка (вектор) <tex>jq = A(s)</tex> не может давать более оптимальное значение . Из алгоритма арифметического кодирования <tex>v[j] L = \prod\cdot u[limits_{i]</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]</tex>, а ответ на запрос =1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{---i}} это поиск <tex>v[j]</tex>, максимизирующего проекцию на . Тогда <tex>u[i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>(0, 0)</tex> в <tex>(1, a[i])</tex>). A(s) = q Ее можно решить за <tex>O(\log(leq -\log_2 L = -\log_2 \prod\limits_{i=1}^n))</tex> двумя бинарными или одним тернарным поиском Асимптотика алгоритма поp_{i}^{f_{i}} = -прежнему составит <tex>O(\sum\limits_{i=1}^n f_i\cdot \log(log_2 p_i = -l \cdot \sum\limits_{i=1}^n))p_i\cdot \log_2 p_i </tex> [[Файл:picture5convexhull.png]] Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются Энтропия источника вычисляется по следующей формуле <mathtex>3</math> вектора <math>a, b, cH(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</mathtex>, расположенные как на рис. 5 Следовательно, т.е. точка <mathtex>bA(s) \leq l \cdot H(p_1 \ldots p_n)</math> не лежит на выпуклой оболочке векторов <tex>0.}} == Адаптивное арифметическое кодирование == Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки символов сообщения не известны до начала работы алгоритма. Преимущество такого подхода кодирования заключается в том, aчто декодировщику не нужно передавать вероятностные оценки для символов, bон будет строить их по мере декодирования сообщения, c </tex> : <texчто может сильно сократить вес такого сообщения.  === Алгоритм кодирования === На вход алгоритму передаётся последовательность символов и алфавит. Каждому символу алфавита <tex> \Leftrightarrow |[a-b, b-c]| < 0 alpha \in \sum</tex>, то либо сопоставляется его вес <tex>(a, u[i])w_\alpha</tex> оптимальнее, чем . В начале работы алгоритма все веса символов равны <tex>(b, u[i])1</tex>, либо . Вероятность каждого символа <tex>(c, u[i])\alpha</tex> оптимальнее, чем {{---}} <tex>p(b, u[i]\alpha)</tex>. {{Теорема |idустанавливется равной его весу, делённому на суммарный вес всех символов: <tex dpi="180">p(\alpha) =th12392. |statement\dfrac{w_\alpha}{\sum_{i=Если есть <tex>31}^n w_i}</tex> вектора . После получения очередного символа и построения нужного интервала, вес символа увеличивается на <tex>a, b, c1</tex>. Когда все символы последовательности будут обработаны, таких что необходимо либо записать маркер конца последовательности, либо запомнить её длину, чтобы позже передать декодировщику. После получения нужных границ <tex>|[a-bl, b-cr]| < 0</tex> то либо , в котором будет лежать код, необходмо выбрать число <mathtex>(a, u) < (b, u)x</mathtex>, либо описывающее кодирование:<mathtex>(cx \in [l, u) < (b, u)r]</mathtex>, где вектор . Выбор числа <mathtex>u = (1; k)x</mathtex>производится также, как и в неадаптивном алгоритме. |proof=По условию теоремы известно, что Выбирается число вида <tex>|[a-b, b-c]| < 0 \Leftrightarrow (a_dfrac{x} - b_{2^p}: x}),p \cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) in \cdot (b_{x} - c_{x})mathbb N</tex> (*). Предположим (от противного), что  === Псевдокод алгоритма === * <tex>(b, u) < (a, u) \Leftrightarrow b_mathtt{xin} + k \cdot b_</tex> {y} < c_{x---} + k \cdot c_{y} текст, подаваемый на вход* <tex>\Leftrightarrow (b_mathtt{xn} - c_</tex> {x{---}}) длина исходного текста * < k tex>\cdot (c_{y} - b_mathtt{ySegment})</tex> и {{---}} структура, задающая подотрезок отрезка <tex>(b[0, u1) < (c/tex>, u) \Leftrightarrow b_{x} + k соответствующая конкретному символу. Имеет следующие поля:** <tex> \cdot b_mathtt{yleft} < a_/tex> {x} + k \cdot a_{y} \Leftrightarrow (a_{x---} - b_{x}) левая граница подотрезка** <tex> k \cdot (b_{y} - a_mathtt{yright})</tex>. {{---}} правая граница подотрезка Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_mathtt{ym})</tex>{{---}} мощность алфавита* <tex> \cdot (c_mathtt{yweight} - b_{y}) = k</tex>{{---}} веса символов алфавита* <tex> \cdot (b_mathtt{ysegments} - a_{y}) \cdot <</tex>{{---}} набор подотрезков, соответствующих символам алфавита* <tex>(b_\mathtt{y} - c_{yleft, right})</tex> <tex> < (a_{x{---} - b_{x})</tex>границы отрезка, содержащие возможный результат арифметического кодирования* <tex> \cdot mathtt{getAlphabet(b_{yin : char[n])} - c_{y})</tex><tex> < (a_{y{---} - b_{y}) \cdot функция возвращает множество различных символов в тексте </tex><tex>(b_\mathtt{x} - c_{xin})</tex> <tex>< k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие  ==== Подотрезок ====  '''struct''' Segment: '''double''' left; '''double''' right; ==== Определение начальных границ подотрезков ====  '''map<texchar,''' '''Segment'''>k \cdot defineSegments'''(a_{y} - b_{y}) \cdot (c_{y} - b_{y}'''set<char>''' alphabet) : < k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})font color=green>// определяем размер подотрезков </texfont> 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 Визуализатор арифметического кодирования] ==См. также== 1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull 2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование [[Категория:Дискретная математика и алгоритмы]] [[Категория: Динамическое программированиеТеория вероятности]] [[Категория: Способы оптимизации методов динамического программированияАлгоритмы сжатия]]