1679
правок
Изменения
м
ураа
[[Оптимальный префиксный код]] с сохранением порядка(англ. ''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> \le 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 w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> - по индукционному предположению для D
##: <tex> \le D[i][j'] + D[i'][j] </tex> - по определению D.## <tex> z \ge y </tex> доказывается аналогично.
Лемма доказана.
}}
: <tex> D[k][j] + D[k'][j+1] \le D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
}}
== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу R. Так как отрезки <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> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем R для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.
Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] <= R[i][j] <= R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать - <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] <= R[i+1][j+1] <= R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.
