Усиление степени сжатия текста: различия между версиями

Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит, где <math>\eta \;</math> и <math>\mu \;</math> – константы. Определим функцию стоимости <math>C_A(x) = |x| H_0 (x) + \eta |x| + \mu \;</math>. В работе [3] Ферраджина и коллеги используют жадный алгоритм с линейным временем выполнения, вычисляющий оптимальное листовое покрытие <math>\mathcal{L}_{min} \;</math> относительно <math>C_A \;</math>. Авторы работы [3] также показали, что для любого <math>k \ge 0 \;</math> существует листовое покрытие <math>\mathcal{L}_k \;</math> стоимостью CA(Lk) = jsj Hk(s) + rj\s\ + O(|^7|fc). Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием Lmin, общий размер выходного значения ограничени в терминах jsj Hk(s) для любого k > 0. На деле