1679
правок
Изменения
м
Алгоритм нахождения оптимального префиксного кода с сохранением порядка.
База индукции: при При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
Индукционный шаг завершен, лемма Лемма доказана.
Нет описания правки
Пусть у нас есть алфавит <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> хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.
Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.
Тогда такое ''наибольшее'' k, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> [i, ..j] </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> [i, ..j] </tex>.
Если разрез происходит по какому - то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.
Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмена - обходом по построенному дереву.
Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.
== Монотонность точки разреза ==
: <tex>\forall i \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + a[i][j']</tex>
}}
{{Лемма
<tex>\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] </tex>
| proof=
Рассмотрим два случая:
##: <tex> \le D[i][j'] + D[i'][j] </tex> - по определению D.
## <tex> z \ge y </tex> доказывается аналогично
}}
{{Теорема
