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

Пусть 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> стоимостью <math>C_A(\mathcal{L}_k) = |s| H_k(s) + \eta |s| + O(|\Sigma|^k) \;</math>. Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием <math>\mathcal{L}_{min} \;</math>, общий размер выходного значения ограничени в терминах <math>|s| H_k(s) \;</math> для любого <math>k \ge 0 \;</math>. На деле <math>\sum_{u \in \mathcal{L}_{min}} C_A (\hat{s} \langle u \rangle ) = C_A(\mathcal{L}_{min}) \le C_A (\mathcal{L}_k) = |s| H_k(s) + \eta|s| + O(|\Sigma|^k)</math>.

1. Вычислить <math>\hat{s} = bwt(s) \;</math>;

2. Вычислить оптимальное листовое покрытие <math>\mathcal{L}_{min} \;</math> относительно <math>C_A \;</math> и разбиение <math>\hat{s} \;</math>, соответствующее <math>\mathcal{L}_{min} \;</math>;