Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Версия от 00:48, 17 декабря 2010; Dgerasimov (обсуждение | вклад)
Содержание
Определение
Определение: |
Оптимальный префиксный код с сохранением порядка(англ. order-preserving code, alphabetic code).
Пусть у нас есть алфавит . Каждому символу сопоставим его код . Кодирование называется оптимальным префиксным с сохранением порядка, если соблюдаются:
|
Алгоритм
Алгоритм нахождения оптимального префиксного кода с сохранением порядка. Решим задачу, используя ДП на подотрезках. Пусть в ячейке
хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.Тогда пересчет
будет происходить так:
Базой динамики будет
Добавочный член
возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов также увеличиваются на 1.Тогда такое наибольшее k, на котором достигается этот минимум, называется точкой разреза для отрезка
. Пусть в ячейке хранится точка разреза на отрезке .Монотонность точки разреза
Теорема (Монотонность точки разреза): |
Доказательство: |
???? |