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