Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
Версия от 04:39, 16 декабря 2010; Dgerasimov (обсуждение | вклад)
печальная статья. Определение: Оптимальный префиксный код с сохранением порядка(англ. order-preserving code, alphabetic code) Пусть у нас есть алфавит . Каждому символу сопоставим его код . Кодирование называется оптимальным префиксным с сохранением порядка, если:
- Условие порядка - лексикографически меньше, и наоборот. . То есть, если символ c_i лексикографически меньше символа c_j, его код также будет
- Условие оптимальности - - минимально, где f_i - количество(или вероятность) встретить символ c_i в тексте, а |p_i| - длина его кода.