1679
правок
Изменения
м
????Для доказательства этого сперва докажем несколько лемм:
Нет описания правки
Пусть у нас есть алфавит <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> D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + \sum\limits_{t = w[i}^{][j} f_t ]</tex>
Базой динамики будет <tex> D[i][i] = 0 </tex>
Добавочный член <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>.
== Монотонность точки разреза ==
Для доказательства этого сперва докажем несколько лемм.
{{Определение
| definition=
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
: <tex>\forall i \leq i' \leq j \leq j' : a[i][j] + a[i'][j'] \leq a[i'][j] + a[i][j']</tex>
}}
{{Определение
| definition=
Функция a является '''монотонной(monotone)''', если
: <tex>\forall i \leq i' < j \leq j' : a[i][j'] \leq a[i'][j] </tex>
}}
{{Лемма
| statement=
w удовлетворяет неравенству четырехугольника.
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> - простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leq w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leq (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leq 0 </tex>, что является верным. Лемма доказана.
}}
{{Лемма
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то D также удовлетворяет неравенству четырехугольника.
| proof=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
Рассмотрим два случая:
# i' = j
: i < i' = j < j'. Тогда неравенство четырехугольника
}}
{{Теорема
| about=
<tex> R[i][j - 1] \leq R[i][j] \leq R[i + 1][j] </tex>
| proof=
}}
