| Определение: |
| Оптимальный префиксный код с сохранением порядка (англ. order-preserving code, alphabetic code).
Пусть у нас есть алфавит [math] \Sigma [/math]. Каждому символу [math]c_i [/math] сопоставим его код [math] p_i [/math]. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
- Условие порядка — [math] \forall i, j : c_i \lt c_j \iff p_i \lt p_j [/math]. То есть, если символ [math]c_i [/math] лексикографически меньше символа [math] c_j [/math], его код также будет лексикографически меньше, и наоборот.
- Условие оптимальности — [math] \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| [/math] — минимально, где [math] f_i [/math] — частота встречаемости символа [math] c_i [/math] в тексте, а [math] |p_i| [/math] — длина его кода.
|
Алгоритм
Решим задачу, используя ДП на подотрезках. Пусть в ячейке [math] D[i][j] [/math] хранится минимальная стоимость кодового дерева для отрезка алфавита от [math] i [/math] до [math] j [/math].
Тогда пересчет [math] D[i][j] [/math] будет происходить так:
[math] D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j][/math]
Базой динамики будет [math] D[i][i] = 0 [/math]
Добавочный член [math]w[i][j] = \sum\limits_{t = i}^{j} f_t [/math] возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на [math] 1 [/math], а значит, и длины всех кодов символов [math] c_i .. c_j [/math] также увеличиваются на [math] 1 [/math].
Тогда такое наибольшее [math] k [/math], на котором достигается этот минимум, называется точкой разреза для отрезка [math] i..j [/math]. Пусть в ячейке [math] R[i][j] [/math] хранится точка разреза на отрезке [math] i..j [/math].
Если разрез происходит по какому-то определенному индексу [math] q [/math] , такой разрез обозначим [math] D_q[i][j] [/math].
Таким образом, получили алгоритм, работающий за [math] O(n^3) [/math]. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана — обходом по построенному дереву.
Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до [math] O(n^2) [/math].
Монотонность точки разреза
Для доказательства этого сперва докажем несколько лемм.
| Определение: |
Функция [math] a [/math] удовлетворяет неравенству четырехугольника (англ. quadrangle inequation), если
- [math]\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j'][/math].
|
| Лемма: |
[math] w [/math] удовлетворяет неравенству четырехугольника. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Заметим, что [math] w[i][j] = w[i][t] + w[t+1][j] [/math], так как [math] w[i][j] [/math] — простая арифметическая сумма. Тогда:
- [math] w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j'][/math]
- [math] (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) [/math]
Получили [math] 0 \leqslant 0 [/math]. |
| [math]\triangleleft[/math] |
| Лемма: |
Если [math] w [/math] удовлетворяет неравенству четырехугольника и монотонна по включению (то есть $w[i'][j] \le w[i][j']$ при $i \leqslant i' \leqslant j \leqslant j'$), то [math] D [/math] также удовлетворяет неравенству четырехугольника, то есть:
[math]\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] [/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
При [math] i = i' [/math] или [math] j = j' [/math], очевидно, неравенство выполняется.
Рассмотрим два случая:
- [math] i' = j [/math]
- [math] i \lt i' = j \lt j' [/math]. Тогда неравенство четырехугольника сводится к:
- [math] D[i][j] + D[j][j'] \leqslant D[i][j'] [/math]
- Пусть [math] k = R[i][j'] [/math]. Получили два симметричных случая:
- [math] k \leqslant j [/math]
- [math] D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] [/math] — по определению [math] D[i][j] [/math]
- [math] \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] [/math] — так как [math] w[i][j'] \geqslant w[i][j] [/math] по монотонности
- [math] \leqslant w[i][j'] + D[i][k-1] + D[k][j'] [/math] — по индукционному предположению для [math] D [/math]
- [math] \leqslant D[i][j'] [/math] — по определению [math] D[i][j'] [/math]
- [math] k \geqslant j [/math] — аналогичный предыдущему случай.
- [math] i' \lt j [/math]
- [math] i \lt i' \lt j \lt j' [/math]
- Пусть [math] y = R[i'][j] [/math] и [math] z = R[i][j'] [/math]. Получили два симметричных случая:
- [math] z \leqslant y [/math]
- Получили [math] i \leqslant z \leqslant y \leqslant j [/math]. Запишем:
- [math] D[i'][j'] + D[i][j] \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] [/math]
- [math] \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] [/math] — по неравенству четырехугольника для [math] w [/math]
- [math] \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] [/math] — по индукционному предположению для [math] D [/math]
- [math] \leqslant D[i][j'] + D[i'][j] [/math] — по определению [math] D [/math]
- [math] z \geqslant y [/math] доказывается аналогично.
|
| [math]\triangleleft[/math] |
| Теорема (Монотонность точки разреза): |
Если [math] w [/math] удовлетворяет неравенству четырехугольника, то:
[math] \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] [/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
В случае [math] i = j [/math] неравенство, очевидно, выполняется. Рассматриваем случай [math] i \lt j [/math] и только случай [math] R[i][j] \leqslant R[i][j+1] [/math] (вторая часть доказывается аналогично):
Так как [math] R[i][j] [/math] — максимальный индекс, в котором достигается минимум, достаточно показать, что:
- [math] \forall i \lt k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] [/math] — фактически, это означает что если на отрезке [math] i..j [/math] разрез оптимальнее по [math] k' [/math], чем по [math] k [/math], то он также будет оптимальнее и на отрезке [math] i..j+1 [/math].
Докажем более сильное неравенство:
- [math] \forall i \lt k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] [/math]
- [math] D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] [/math]
- [math] (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]) [/math] — по определению [math] D [/math]
- [math] D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] [/math] — получили неравенство четырехугольника для [math] k \leqslant k' \leqslant j \leqslant j+1 [/math], что является верным из предыдущей леммы.
|
| [math]\triangleleft[/math] |
Объяснение квадратичной асимптотики
Рассмотрим матрицу [math] R [/math]. Так как отрезки [math] i..j [/math], где [math] i \gt j [/math] мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что [math] R[i][i] = i [/math] (так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента [math] R[i][j] [/math] его значения лежат между [math] R[i][j-1] [/math] (левый элемент в матрице) и [math] R[i+1][j] [/math] (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем [math] R [/math] для отрезков длины [math] 2 [/math], затем [math] 3 [/math], и так далее до [math] n [/math]. Фактически, мы будем обходить диагонали матрицы, количество которых равно [math] n [/math].
Рассмотрим элемент [math] R[i][j] [/math]. Для него выполняется [math] R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] [/math]. Следующий элемент, который мы будем пересчитывать — [math] R[i+1][j+1] [/math]. Для него выполняется [math] R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] [/math]. Таким образом, заполняя одну диагональ, алгоритм сделает не более [math] n [/math] шагов, а так как диагоналей [math] n [/math], получили асимптотику [math] O(n^2) [/math].
Источники информации
