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

Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>.

Обозначим за C функцию, которая ассоциирует с каждой строкой x над <math>\Sigma \cup \{ $ \} \;</math> положительное вещественное значение C(x). Для любого листового покрытия <math>\mathcal{L} \;</math> определим его стоимость как <math>C(\mathcal{L}) = \sum_{u \in \mathcal{L}} C( \hat{s} \langle u \rangle) \;</math> – иными словами, стоимость листового покрытия <math>\mathcal{L} \;</math> равна сумме стоимостей строк в разбиении, порожденном <math>\mathcal{L} \;</math>. Листовое покрытие <math>\mathcal{L}_min \;</math> называется ''оптимальным'' относительно <math>C если C(\mathcal{L}_min) \le C(\mathcal{L}) \;</math> для любого листового покрытия <math>\mathcal{L} \;</math>.

Пусть 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 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более <math>|x| H_0(x) + \eta |x| + \mu \;</math> бит. Механизм усиления степени сжатия, примененный к A, дает выходное значение, размер которого ограничен <math>|s| H_k(s) + log |s| + \eta |s| + O(|\Sigma|^k) \;</math> бит одновременно для всех <math>k \ge 0 \;</math>. Учитывая A, механизм усиления привносит в процесс сжатия дополнительные накладные расходы на память в размере O(|s| log |s|) бит, но не вносит дополнительных затрат времени.'''