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