Convex hull trick {{Определение |definition='''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} один алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из методов оптимизации динамического программирования отрезка <tex>[[http:0; 1)<//neerctex>.ifmo.ru/wiki/index.php?title=Динамическое_программирование Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], использующий идею выпуклой оболочкито есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Позволяет улучшить ассимптотику решения некоторых задачьАрифметическое кодирование показывает более высокие результаты сжатия, решемых методом динамического программирования чем алгоритм Хаффмана, для данных с <math>Oнеравномерными распределениями вероятностей кодируемых символов.}} == Принцип действия ==При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (n^2)теоретически, символу <tex>a</mathtex> до с вероятностью появления <tex>Op(n\cdot\log(n)a)</tex>. Техника впервые появилась допустимо ставить в 1995 году соответствие код длины <tex>-\log_2 p(задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированиюa)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002. ==Пример задачи, решаемой методом convex hull trick= Кодирование === На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.# Рассмотрим задачу на ДП: {{Задача |definition = Есть <mathотрезок <tex>n[0; 1)</math> деревьев с высотами <tex>a_1на координатной прямой. # Поставим каждому символу текста в соответствие отрезок, a_2длина которого равна частоте его появления.# Считаем символ из входного потока и рассмотрим отрезок, \dotsсоответствующий этому символу. Разделим этот отрезок на части, a_nпропорциональные частотам встречаемости символов.# Повторим пункт </tex> (в метрах3)</tex> до конца входного потока. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так# Выберем любое число из получившегося отрезка, что она может спиливать только по 1 метру от дерева, к которому ее примениликоторое и будет результатом арифметического кодирования. Также после срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex=== Псевдокод === *<math>i\mathtt{s}\,</texmath>{{---}} текст, то цена заправкиподаваемый на вход; равна *<texmath>c_i\mathtt{n}\,</texmath>. Изначально пила заправлена.{{---}} длина исходного текста; Также известны следующие ограничения : *<texmath>c_n = 0\mathtt{m}\, a_1 = 1, a_i</texmath> возрастают, {{---}} мощность алфавита исходного текста;*<texmath>c_i\mathtt{letters[m]}\,</texmath> убывают. Изначально пила заправлена. (убывание и возрастание нестрогие) {{---}}массив символов, составляющих алфавит исходного текста; (Задача H с Санкт-Петербургских сборов к РОИ 2016*<math>\mathtt{probability[http:m]}\,<//neerc.ifmo.ru/school/campmath> {{---2016/problems/20160318a.pdf])}} массив вероятностей обнаружения символа в тексте; *</noincludemath> \mathtt{Segment}\,<includeonly/math>{{#if: {{{neat|---}}}| структура, задающая подотрезок отрезка <div style="background-color: #fcfcfc; float:left;"tex> <div style="background-color: #ddd[0;">'''Задача:'''1)</divtex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля: **<div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;"math>\mathtt{left}\,</math>{{{definition}---}}левая граница подотрезка;**</divmath> \mathtt{right}\,</divmath>|{{---}} правая граница подотрезка; *<table border="0" width="100%"math> \mathtt{left}\,<tr/math>, <td style="background-color: #ddd"math>'''Задача:'''\mathtt{right}\,</tdmath></tr> <tr><td style="border:1px dashed #2f6fab; padding: 8px; background{{--color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr>границы отрезка, содержащего возможный результат арифметического кодирования. '''struct''' Segment: </table>}} '''double''' left </includeonly> '''double''' right ==Наивное решение== Сначала заметим важный факт : т.к. <tex>c '''Segment'''[im]</tex> убывают defineSegments(нестрого) и <tex>cletters: '''char'''[nm] = 0</tex>, то все <tex>cprobability: '''double'''[im]</tex> неотрицательны.): Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c '''Segment'''[nm] segment '''double''' l = 0 '''for''' i = 0</tex>). Посчитаем следующую динамику : <tex>dp'''to''' m - 1 segment[letters[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>].left = l segment[letters[i]].</tex> будет срублено. База динамики : <tex>dpright = l + probability[1i] l = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачиsegment[letters[i]].right '''return''' segment Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые '''double''' arithmeticCoding(док-во этого факта оставляется читателям как несложное упражнениеletters: '''char'''[m], т.к. эта идея относится скорее к теме жадных алгоритмновprobability: '''double'''[m], чем к теме данной статьиs: '''char'''[n]). Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j \leqslant i - 1</tex>. Поэтому чтобы найти <tex>dp: '''Segment'''[im]</tex> нужно перебрать все <tex>segment = defineSegments(letters, probability) '''double''' left = 0 '''double''' right = 1 \leqslant j \leqslant '''for''' i = 0 '''to''' n - 1</tex> и попытаться использовать ответ для дерева намер <tex>j</tex>. Итак, пусть перед <tex> '''char''' symb = s[i</tex>-м деревом мы полностью срубили <tex>j</tex>] '''double''' newRight = left + (right -е, причем высота <tex>i</tex>-го дерева составляет <tex>aleft) * segment[isymb]</tex>, а т.к. последнее дерево, которое мы срубили имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>right '''double''' newLeft = left + (right -го дерева составит <tex>cleft) * segment[jsymb]</tex>. Поэтому на сруб <left left = newLeft right = newRight '''return''' (left + right) / 2 '''Замечание:''' для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона <tex>i[left; right]</tex>-го дерева мы потратим <tex>a[i] \cdot c[j]</tex> монетчисло, содержащее наименьшее количество знаков в двоичной записи. === Декодирование ===Алгоритм по вещественному числу восстанавливает исходный текст. Также не стоит забывать, ситуацию, когда # Выберем на отрезке <tex>j[0; 1)</tex>-е дерево полностью срублено, мы получили не бесплатноразделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, а за дописываем в ответ.# Нормируем подотрезок и вещественное число.# Повторим пункты <tex>dp[j]1</tex> монет. Итогвая формула пересчета : {{---}}<tex>2</tex>dp[i] = \minдо тех пор, пока не получим ответ. === Псевдокод === *<math>\limits_mathtt{j=1...i-1code} (dp[j] + a[i] \cdot c[j])</tex,</math>. Посмотрим {{---}} вещественное число, подаваемое на код выше описанного решения:вход; '''int''' *<texmath>\mathtt{simpleDPn}\,</texmath>('''int''' a[n]{{---}} длина восстанавливаемого текста;*<math>\mathtt{m}\, '''int''' c[n]) dp[1] = 0</math> {{---}} мощность алфавита исходного текста; dp*<math>\mathtt{letters[2m] = dp[3] = ... = dp[n] = <tex>}\infty,</texmath> '''for''' i = 1..n{{---1}} массив символов, составляющих алфавит исходного текста; dp*<math>\mathtt{probability[im] = <tex>+}\infty,</texmath> '''for''' j = 0..i{{---1}} массив вероятностей обнаружения символа в тексте; '''if''' (dp[j] + a[i] *<texmath>\cdotmathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex> c[j] < dp[i]0; 1) dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j], соответствующего конкретному символу на основе частотного анализа. Имеет поля: '''return''' dp[n] Нетрудно видеть, что такая динамика работает за ** <texmath>O(n^2)\mathtt{left}\,</texmath>. {{---}} левая граница подотрезка; ==Ключевая идея оптимизации== Для начала сделаем замену обозначений. Давайте обозначим ** <texmath>dp[j]\mathtt{right}\,</texmath> за {{---}} правая граница подотрезка;** <tex>b[j]</texmath>\mathtt{character}\, <tex>a[i]</texmath> за <tex>x[i]</tex>, а <tex>c[j]</tex> за <tex>k[j]</tex>.{{---}} значение символа. '''struct''' Segment: '''double''' left Теперь формула приняла вид <tex>dp '''double''' right '''char''' character '''Segment'''[im] = \min\limits_{j=0...i-1}defineSegments(k[j] \cdot xletters: '''char'''[in] + b, probability: '''double'''[jn])</tex>. Выражение <tex>k: '''Segment'''[jm] \cdot x segment '''double''' l = 0 '''for''' i = 0 '''to''' m - 1 segment[i].left = l segment[i].right = l + bprobability[ji]</tex> {{---}} это в точности уравнение прямой вида <tex>y segment[i].character = letters[i] l = kx + b</tex>segment[i].right '''return''' segment Сопоставим каждому <tex>j</tex>, обработанному ранее, прямую <tex>y '''string''' arithmeticDecoding(letters: '''char'''[jm](x) = k, probability: '''double'''[jm] \cdot x + b, code: '''double''', n: '''int'''): '''Segment'''[jm]</tex>. Из условия «<tex>c[segment = defineSegments(letters, probability) '''string''' s = "" '''for''' i]</tex> убывают <tex>\Leftrightarrow k[= 0 '''to''' n - 1 '''for''' j]= 0 '''to''' m - 1 '''if''' code</tex> уменьшаются с номером \small{~\geqslant~}</tex>segment[j</tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент].left '''and''' code < segment[j]. Давайте нарисуем несколько таких прямых :right s += segment[[Файл:picture1convexhullj].png]]character Выделим множество точек <tex> code = (x0, y0code – segment[j].left)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x0) < y0</tex>(segment[j].right – segment[j]. Иными словами возьмем «выпуклую (вверхleft) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, convex(x))</math> представляет собой выпуклую вверх функцию. '''break''' '''return''' s ==Цель нижней огибающей множества прямых== Пусть мы считаем динамику для <tex>i</tex>-го дерева'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Его задает <tex>x[i]</tex>Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен. Итак, нам нужно для данного < '''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>x[i]\dfrac{1}{3}</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]))<m</tex>. Это выражение есть подотрезков, кратных по длине <mathtex>convex(x[i])n</mathtex>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую а всего итераций <tex>x = x[i]n</tex>, можно найти бинарным поиском. Это потребует в конечном результате знаменатель дроби не превысит <tex>O(\log(n))^{n}</tex> времени на поиск такого <, а поскольку сумма всех вероятностей встречи символов равна <tex>j1</tex>, что полученная дробь будет находиться в промежутке <tex>dp[i] = k[j] \cdot x[i] + b[j]0; 1)</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять == Пример работы ==Рассмотрим в качестве примера строку <tex>iabacaba</tex>-ю прямую после того, как мы посчитали :=== Кодирование ==={|class="wikitable"!Символ||Частота появления|-|<p style="text-align:center;"><tex>b[i] = dp[i]a</tex>. Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex>k[]<</texp> и ||<texp style="text-align:center;">b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами0. Рассмотрим ситуацию, когда мы хотим добавить новую (571429</tex>i</texp>|-тую) прямую в множество. Пусть сейчас в множестве лежит |<texp style="text-align:center;">sz</tex> прямых (нумерация с 1). Пусть b</tex>(xL, yL)</texp> {{||<p style="text---}} точка пересечения align:center;"><tex>sz - 10.285714</tex></p>|-|<p style="text-й прямой множества и align:center;"><tex>szc</tex></p>||<p style="text-й, а align:center;"><tex>(xR, yR)0.142857</tex> </p>|}[[Файл:Code_png.png|thumb|right|200px|Пример работы кодировщика ]]{{|class="wikitable"!Считанный символ||Левая граница отрезка||Правая граница отрезка|-|||<p style="text--}} точка пересечения новой прямой, которую мы хотим добавить в конец множества и align:center;"><tex>sz0</tex></p>||<p style="text-й. Нас будут интересовать только их align:center;"><tex>x1</tex></p>|-овые координаты |<p style="text-align:center;"><tex>xLa</tex> и <tex/p>||<p style="text-align:center;">xR</tex>, соответственно. Если оказалось, что новая прямая пересекает 0</tex>sz</texp>||<p style="text-ю прямую выпуклой оболочки позже, чем align:center;"><tex>sz0.571429</tex>-я <tex/p>sz |- 1|<p style="text-align:center;"></tex>-ю, т.е. b</tex>(xL \geqslant xR)</p>||<p style="text-align:center;"><tex>, то 0.326531</tex>sz</texp>||<p style="text-ю удалим из нашего множества, иначе {{---}} остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо align:center;"><tex>xL0.489796</tex> не станет меньше <tex>xR.</texp> |- Асимптотика |<p style="text-align: аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <mathcenter;"><tex>a</tex>1</mathp> раз добавится в стек и максимум ||<mathp style="text-align:center;">1</mathtex> раз удалится0. Значит время работы перестройки выпуклой оболочки займет 326531</tex>O(n)</texp> суммарно. [[Файл||<p style="text-align:picture2convexhullcenter;"><tex>0.png]]419825</tex></p> [[Файл:picture3convexhull.png]] {{Теорема |id=th1239.- |statement<p style=Алгоритм построения нижней огибающей множества прямых корректен. |proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя {{"text---}} предпоследнюю. Пусть align:center;"><tex>Y(x) = Kx + Bc</tex> {{</p>||<p style="text---}} уравнение новой прямой, align:center;"><tex>y[i](x) = K[i]x + B[i]0.406497</tex> {{--</p>||<p style="text-}} уравнения прямых множества. Тогда т.к. align:center;"><tex>K < K[sz]0.419825</tex>, то при <tex/p>x \in [|- \infty; xR] : y[sz](x) |<p style= Y(x)"text-align:center;"><tex>a</tex>, а т.к. <tex/p> K[sz] ||< K[sz p style="text- 1]align:center;"><tex>0.406497</tex>, то при <tex/p>x \in [xL; + \infty] ||<p style="text-align: y[sz - 1](x) \geqslant y[sz](x)center;"></tex>0. Если 414113</tex>xL < xR</texp>, то при |-|<tex>x \in [xLp style="text-align:center; xR] : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex">, т.е. на отрезке <tex>[xL; xR]b</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex/p>xL ||<p style="text-align:center;"><tex> xR0.410849</tex>, то она ниже всех на отрезке <tex/p>[xL||<p style="text-align:center; xR] = \varnothing "></tex>, т0.е. её можно удалить из множества413025</tex></p> }}|- |<p style==Детали реализации:== Будем хранить 2 массива "text-align: center;"><tex>front[]a</tex> {{---}} <tex/p>x||</tex>p style="text-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (тalign:center;"><tex>0.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при 410849</tex>x</texp>||<p style="text-align:center;"> <tex>\in0.412093</tex> <tex/p>[front[i]; front[i + 1])|}Код: <tex>0.411471</tex> ) и === Декодирование ===Код: <tex>st[]0.411471</tex> {{---}} номера деревьев, соответствующих прямым (т.е[[Файл:decode1_png. png|thumb|right|200px|Пример работы декодировщика ]]{|class="wikitable"!Декодируемый символ||Код|-|<p style="text-align:center;"><tex>ia</tex>-я прямая множества, где <tex/p>i||</texp style="text-align:center;"> <tex>\in0.411471</tex> <tex/p>[1|-|<p style="text-align:center; sz]"></tex> соответствует дереву номер b</tex>sz[i]</texp>). Также воспользуемся тем, что ||<tex>x[i] p style= a[i]</tex"text-align:center;"> возрастают (по условию задачи), а значит мы можем искать первое такое <tex>j0.720074</tex>, что <tex/p>x[i] \geqslant front[j]|-|<p style="text-align:center;"><tex>a</tex> не бинарным поиском, а методом двух указателей за </p>||<p style="text-align:center;"><tex>O(n)0.520259</tex> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х</p>|-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые |<texp style="text-align:center;">x[i]</tex>, а значит если c</tex>k</texp>||<p style="text-align:center;">-я прямая пересекается с <tex>k+10.910454</tex>-й в точке <tex/p>z +|-|</texp style="text-align:center;"> <tex>\alphaa</tex> (<math/p>z||</mathp style="text-align:center;">-целое, <tex>\alpha0.373178</tex> <tex/p>\in|-|</texp style="text-align:center;"> <tex>[0;1)b</tex>), то мы будем подставлять в их уравнения <tex/p>z||</texp style="text-align:center;"> или <tex>z + 10.653061</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <tex>x = z+1</texp> |- ==Реализация|<p style="text-align:center;"><tex>a</tex></p>||<p style= '''int''' "text-align:center;"><tex>\mathtt{ConvexHullTrick}0.285714</tex>(</p>|} '''intЗамечание:''' a[n]при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, '''int''' c[n]но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода. st[1] = 1== Декодирование (второй способ)=== from[1] = -Код: <tex>\infty0.411471</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font> sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>[[Файл:decode2_png.png|thumb|right|200px|Пример работы декодировщика (второй способ) ]]{|class="wikitable" pos !Декодируемый символ||colspan= 1 "4" |Границы отрезка|-|<font colorp style=green"text-align:center;"><tex>a<// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] tex></font p> '''for''' i ||<p style= 2..n '''while''' (front[pos] "text-align:center;"><tex>0</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]-той прямой ><tex>0.857143</font tex> pos = pos + 1 j = st[pos] dp[i] = K[j]<math/p>\cdot||</mathp style="text-align:center;">a[i] + B[j] '''if''' (i < n) tex>1<font color=green/tex>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font p> K[i] = c[i] |-|<font colorp style=green"text-align:center;">// наши переобозначения переменных </font tex> B[i] = dp[i] b<font color=green/tex>// наши переобозначения переменных </font p> x ||<p style= "text-align:center;"><tex>\infty0</tex> '''while''' ''true'' j </p>||<p style= st[sz] x = divide(B[j] "text- B[i], K[i] - K[j]) align:center;"><font color=greentex>0.326531</tex></ xp>||<p style="text-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) align:center;"><tex>0.489796 </font tex> '''if''' (x </p> from[sz]) '''break''' ||<font colorp style=green"text-align:center;"><tex>0.571429<// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" tex></font p> sz = sz |- 1|<font colorp style=green"text-align:center;">// удаляем последнюю прямую, если она лишняя </font tex> st[sz + 1] = i from[sz + 1] = x a<font color=green/tex>// добавили новую прямую </font p> sz ||<p style= sz + 1 '''return''' dp[n] Здесь функция "text-align:center;"><tex>\mathtt{divide}0.326531 </tex>(a, b) возвращает нужное(*) округление a </ b. Приведем её код : '''int''' p>||<p style="text-align:center;"><tex>\mathtt{divide}0.419825 </tex>('''int''' a, '''int''' b) delta </p>||<p style="text-align:center;"><tex>0.466472 </tex></p>||<p style= "text-align:center;"><tex>0 '''if''' (a '''mod''' b ≠ 0) delta = 1 '''if''' ((a .489796 </tex> 0 '''and''' b </p>|-|<p style="text-align:center;"> 0) '''or''' (a < 0 '''and''' b tex>c</tex>< 0)) '''return''' [a / b] + delta '''return''' -[p>|a| <p style="text-align:center;"><tex>0.326531</tex></ p>|b|] Такая реализация будет работать за O(n). <p style==Динамический convex hull trick== Заметим, что условия на прямые, что "text-align:center;"><tex>k[i]0.379842</tex> возрастает</убывает и <texp>x[i]||<p style="text-align:center;"><tex>0.406497</tex> убывает</возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой {{p>||<p style="text---}} отсортировать входные данные нужным образом, не испортив свойств задачи (пример align: задача G c Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf]). Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за center;"><tex>O(\log(n))0.419825</tex> можем найти <tex>dp[i]</texp>|-|<p style="text-align:center;">, но теперь вставку <tex>ia</tex></p>||<p style="text-й прямой в оболочку уже нельзя выполнить описанным ранее способом за align:center;"><tex>O(1)0.406497</tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая {{</p>||<p style="text---}} та, которую мы хотим вставить в наше множество). Более формально align: теперь наша новая прямая будет ниже остальных при center;"><tex>x \in [x1; x2]0.414113</tex>, где <tex/p>||<p style="text-align:center;">x1, x2 \in R</tex> {{---}} точки пересечения с некоторыми прямыми, причем 0.417921 </tex>x2</p>||<p style="text-align:center;"><tex> не обязательно равно 0.419825</tex>+ \infty</texp> [[Файл:picture4convexhull.png]]|- Чтобы уметь вставлять прямую в множество будем хранить |<math>stdp style="text-align::set</mathcenter;"> (или любой аналог в других языках программирования) пар <tex>(k, st)b</tex> = <tex/p>||<p style="text-align:center;">(коэффицент прямой, ее номер в глобальной нумерации)</tex>0. Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает 406497</tex>O(\log(n))</texp>. Начиная с найденной прямой выполняем ||<p style="старыйtext-align:center;" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа)><tex>0. Асимптотика решения составит 410849</tex>O(\log(n))</texp>||<p style="text-align:center;"> на каждый из <tex>n0.413025</tex> запросов «добавить прямую» + <tex/p>O(n\cdot\log(n))||</tex> суммарно на удаление прямых, т.к. поp style="text-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из stdalign::set занимает center;"><tex>O(\log(n))0.414113</tex> времени. Итого <math>O(n\cdot\log(n))</mathp>. |- |<p style== Альтернативный подход == Другой способ интерпретировать выражение "text-align:center;"><tex>a</tex>dp[i] = \min\limits_{j</p>||<p style="text-align:center;"><tex>0...i-1}(c[j] \cdot a[i] + dp[j])410849</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек</p>||<p style="text-align:center;"><tex>0. Перепишем выражение средующим образом 412093</tex></p>||<p style="text-align: center;"><tex>dp[j] + a[i] \cdot c[j] = (dp[j], c[j]) \cdot (1, a[i])<0.412714</tex>, т.е. запишем как скалярное произведение векторов <tex/p>v[j] ||<p style= (dp[j], c[j])</tex"text-align:center;"> и <tex >u[i] = (1, a[i])0.413025</tex >. Вектора <tex /p>v[j] |}== Оценка длины кодового слова =={{Теорема |statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста. ||proof= (dp[j], c[j])Введём следующие обозначения: *<tex>l</tex> хотелось бы организовать так{{---}} длина текста, чтобы за *<tex >O(\log(n))</tex> находить вектор{{---}} размер алфавита, максимизирующий выражение *<tex>v[j] \cdot u[i]f_i</tex>. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) {{---}} частота встречаемости символа,*<tex>jp_i</tex> не может давать более оптимальное значение {{---}} вероятность вхождения символа. Размер сообщения <tex>v[j] \cdot u[i]L</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов можно найти по формуле: <tex>v[j]</tex>, а ответ на запрос L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{---i}} это поиск </tex>v[j] Число бит в закодированном тексте: </tex>, максимизирующего проекцию на <tex>u[\log_2 L = -\sum\limits_{i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>=1}^n f_i\cdot \log_2 p_i = -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(0, 0p_1 \ldots p_n)</tex> в <tex>(1, a[i}} == См. также ==* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]])</tex>). Ее можно решить за <tex>O(\log(n))</tex> двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]] * [[Файл:picture5convexhull.pngЭнтропия_случайного_источника | Энтропия случайного источника]] Докажем то, что описанный выше алгоритм корректен== Источники информации ==* [http://ru.wikipedia. Для этого достаточно показать, что если имеются <math>3<org/math> вектора <math>a, b, c<wiki/math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow |[a%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 Википедия {{--b, b-c}} Арифметическое кодирование]| < 0 <* [https://tex>, то либо <tex>(a, uen.wikipedia.org/wiki/Arithmetic_coding Wikipedia {{---}} Arithmetic coding]* [i])<http:/tex> оптимальнее, чем <tex>(b, u[i])</tex>, либо <tex>(c, u[i])<www.sernam.ru/tex> оптимальнее, чем <tex>(b, u[icod_3.php Арифметическое кодирование])</tex>. {{Теорема |id=th12392* [http://rain.ifmo.ru/cat/view. |statement=Если есть <tex>3<php/tex> вектора <tex>a, b, c<vis/tex>, таких что <tex>|[adata-compression/arithmetic-b, bcoding-c2006 Визуализатор арифметического кодирования]| < 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>. Подставим эти неравенства в (*). Получим цепочку неравенств : <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>. Значит предположение неверно, чтд. }} Из доказанной теоремы и следует корректность алгоритма. ==См. также== 1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull 2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование [[Категория:Дискретная математика и алгоритмы]] [[Категория: Динамическое программированиеТеория вероятности]] [[Категория: Способы оптимизации методов динамического программированияАлгоритмы сжатия]]
