Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Версия от 03:18, 18 декабря 2010; Dgerasimov (обсуждение | вклад)
Содержание
Определение
Определение: |
Оптимальный префиксный код с сохранением порядка(англ. order-preserving code, alphabetic code).
Пусть у нас есть алфавит . Каждому символу сопоставим его код . Кодирование называется оптимальным префиксным с сохранением порядка, если соблюдаются:
|
Алгоритм
Алгоритм нахождения оптимального префиксного кода с сохранением порядка. Решим задачу, используя ДП на подотрезках. Пусть в ячейке
хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.Тогда пересчет
будет происходить так:
Базой динамики будет
Добавочный член
возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов также увеличиваются на 1.Тогда такое наибольшее k, на котором достигается этот минимум, называется точкой разреза для отрезка
. Пусть в ячейке хранится точка разреза на отрезке .Монотонность точки разреза
Для доказательства этого сперва докажем несколько лемм.
Определение: |
Функция a удовлетворяет неравенству четырехугольника(quadrangle inequation), если
|
Определение: |
Функция a является монотонной(monotone), если
|
Лемма: |
w удовлетворяет неравенству четырехугольника. |
Доказательство: |
Заметим, что , так как - простая арифметическая сумма. Тогда: |
Лемма: |
Если w удовлетворяет неравенству четырехугольника и монотонна, то D также удовлетворяет неравенству четырехугольника. |
Доказательство: |
При или , очевидно, неравенство выполняется.Рассмотрим два случая:
Пусть y = R[i'][j] и z = R[i][j]. Получили два различных симметричных случая: z \leq y или z \geq y. Рассмотрим первый из них. Получили z \leq y \leq j (по определению y) и i < z(по определению z). Получим: D[i'][j'] + D[i][j] \leq D_y[i'][j'] + D_z[i][j] |
Теорема (Монотонность точки разреза): |
Доказательство: |
Для доказательства этого сперва докажем несколько лемм: |