Изменения

[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code'').

Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка(алфавитным), если соблюдаются:# Условие порядка {{--- }} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.# Условие оптимальности {{- --}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{--- }} минимально, где <tex> f_i </tex> {{--- }} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{- --}} длина его кода.

Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j</tex>.

Тогда такое ''наибольшее'' <tex> k</tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.

Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмена Хаффмана {{- --}} обходом по построенному дереву.

Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation)'''), если: <tex>\forall i \le leqslant i' \le leqslant j \le leqslant j' : a[i][j] + a[i'][j'] \le leqslant a[i'][j] + a[i][j']</tex>

<tex> w </tex> удовлетворяет неравенству четырехугольника.

Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{- --}} простая арифметическая сумма. Тогда:: <tex> w[i][j] + w[i'][j'] \le leqslant w[i'][j] + w[i][j']</tex>: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \le leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>Получили <tex> 0 \leq leqslant 0 </tex>, что является верным. Лемма доказана.

Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:

<tex>\forall i \le leqslant i' \le leqslant j \le leqslant j' : D[i][j] + D[i'][j'] \le leqslant D[i'][j] + D[i][j'] </tex>

#: <tex> D[i][j] + D[j][j'] \le leqslant D[i][j'] </tex>

## <tex> k \le leqslant j </tex>##: <tex> D[i][j] + D[j][j'] \le leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{- --}} по определению <tex> D[i][j] </tex>##: <tex> \le leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{- --}} так как <tex> w[i][j'] >= \geqslant w[i][j] </tex>##: <tex> \le leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{- --}} по индукционному предположению для <tex> D</tex>##: <tex> \le leqslant D[i][j'] </tex> {{- --}} по определению <tex> D[i][j'] </tex>## <tex> k \ge geqslant j </tex> {{--- }} аналогичный предыдущему случай.

## <tex> z \le leqslant y </tex>##: Получили <tex> i \le leqslant z \le leqslant y \le leqslant j </tex>. Запишем:##: <tex> D[i'][j'] + D[i][j] \le leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>##: <tex> \le leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{- --}} по неравенству четырехугольника для <tex> w </tex>##: <tex> \le leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{- --}} по индукционному предположению для <tex> D</tex>##: <tex> \le leqslant D[i][j'] + D[i'][j] </tex> {{- --}} по определению <tex> D</tex>## <tex> z \ge geqslant y </tex> доказывается аналогично.

Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:

<tex> \forall i \le leqslant j : R[i][j] \le leqslant R[i][j+1] \le leqslant R[i+1][j+1] </tex>

В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \le leqslant R[i][j+1] </tex>(вторая часть доказывается аналогично):

Так как <tex> R[i][j] </tex> {{--- }} максимальный индекс, в котором достигается минимум, достаточно показать, что:: <tex> \forall i < k \le leqslant k' \le leqslant j: [D_{k'}[i][j] \le leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le leqslant D_k[i][j+1]] </tex> {{--- }} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.

: <tex> \forall i < k \le leqslant k' \le leqslant j: D_k[i][j] - D_{k'}[i][j] \le leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>

: <tex> D_k[i][j] + D_{k'}[i][j+1] \le leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>

: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{- --}} по определению <tex> D</tex>

: <tex> D[k][j] + D[k'][j+1] \le leqslant D[k][j+1] + D[k'][j] </tex> {{- --}} получили неравенство четырехугольника для <tex> k \le leqslant k' \le leqslant j \le leqslant j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.

Рассмотрим матрицу <tex> R</tex>. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex>(так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.

Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \le leqslant R[i][j] \le leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{- --}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \le leqslant R[i+1][j+1] \le leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.

== Использованные материалы Источники информации ==[http://www.cs.ust.hk/mjg_lib/Library/Tut_BST.pdf S.V. Nagaraj {{- --}} Tutorial: Optimal binary search trees]

''Кнут Д. Э. Кнут '' {{--- }} Искусство программирования: , том 3. Сортировка и поиск. — М.: «Вильямс», Том 32005.