Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

Определение

Определение:

Оптимальный префиксный код с сохранением порядка(англ. 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] хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.

Тогда пересчет [math] D[i][j] [/math] будет происходить так:

[math] D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + \sum\limits_{t = i}^{j} f_t [/math]

Базой динамики будет [math] D[i][i] = 0 [/math]

Добавочный член [math] \sum\limits_{t = i}^{j} f_t [/math] возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов [math] c_i .. c_j [/math] также увеличиваются на 1.

Тогда такое наибольшее k, на котором достигается этот минимум, называется точкой разреза для отрезка [math] [i, j] [/math]. Пусть в ячейке [math] R[i][j] [/math] хранится точка разреза на отрезке [math] [i, j] [/math].

Монотонность точки разреза

Теорема (Монотонность точки разреза):

[math] R[i][j - 1] \leq R[i][j] \leq R[i + 1][j] [/math]

Доказательство:

[math]\triangleright[/math]

????

[math]\triangleleft[/math]