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

'''Пример 3.''' Рассмотрим суффиксное дерево на рис. 1. Листовой покрытие состоит из всех вершин, имеющих глубину 1. Разбиение <math>\hat{s}\;</math>, порожденное этим листовым покрытием, выглядит как {i, pssm, $; pi, ssii}.

Пусть A – алгоритм сжатия, такой, что для любой строки x размер ее выходного значения ограничен jxjH0(x) + r]\x\ + ji бит, где r\ и ji – константы. Определим функцию стоимости CA(x) = JXJH0(X) + 7]\x\ + ji. В работе [ ] Ферраджина и коллеги используют жадный алгоритм с линейным временем выполнения, вычисляющий оптимальное листовое покрытие Lmin относительно CA. Авторы работы [3] также показали, что для любого k > 0 существует листовое покрытие Lk стоимостью CA(Lk) = jsj Hk(s) + rj\s\ + O(|^7|fc). Эти два важнейших наблюдения показывают, что при использовании A для сжатия каждой подстроки в разбиении, порожденном оптимальным листовым покрытием Lmin, общий размер выходного значения ограничени в терминах jsj Hk(s) для любого k > 0. На деле