19
правок
Изменения
м
__TOC__
== Определение ==
Исправил замечания
{{Определение
| definition =
'''[[Оптимальный префиксный код с длиной кодового слова не более 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> {{---}} длина его кода.
}}
__TOC__
== Алгоритм ==
Базой динамики будет <tex> D[i][i] = 0 </tex>
Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на <tex> 1</tex>, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на <tex> 1</tex>.
Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> 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]) \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] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \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> для отрезков длины <tex> 2</tex>, затем <tex> 3</tex>, и так далее до <tex> n</tex>. Фактически, мы будем обходить диагонали матрицы, количество которых равно <tex> n</tex>.
Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более <tex> n </tex> шагов, а так как диагоналей <tex> n</tex>, получили асимптотику <tex> O(n^2) </tex>.
==Источники информации ==
* [http://www.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]
* ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005, стр.486 - 488
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]
