4551
правка
Усиление степени сжатия текста: различия между версиями
Перейти к навигации
Перейти к поиску
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 23:50, 12 января 2017
, 12 января 2017→Алгоритм усиления степени сжатия
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 76: | Строка 76: | ||
Усиление степени сжатия текста, рис. 1 | Усиление степени сжатия текста, рис. 1 | ||
Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, s = bwt(s) = ipssm$pissii | Матрица bwt (слева) и суффиксное дерево (справа) для строки s = mississippi$. Выходным значением алгоритма bwt является последний столбец матрицы bwt, т.е., в данном случае, s = bwt(s) = ipssm$pissii | ||
Обозначим за C функцию, которая ассоциирует с каждой строкой x над S [ f$g положительное вещественное значение C(x). Для любого листового покрытия L определим его стоимость как C(L) = Pu2L С(Чи)) – иными словами, стоимость листового покрытия L равна сумме стоимостей строк в разбиении, порожденном L. Листовое покрытие Lmin называется оптимальным относительно C если C(Lmin) < C(L) для любого листового покрытия L. | |||
Пусть 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. На деле | |||
CA(s(u}) =CA(Lmin) < CA(Lk) in u2Lmin О(\Е\к) = jsjHk(s)+ | |||
Суммируя все вышесказанное, усиление алгоритма сжатия A над строкой s состоит из трех основных этапов: | |||
1. Вычислить d = bwt(s); | |||
2. Вычислить оптимальное листовое покрытие Lmin относительно CA, и разбиение J, соответствующее Lmin; | |||
3. Сжать каждую подстроку разбиения при помощи алгоритма A. | |||
Таким образом, парадигма усиления сводит разработку эффективных алгоритмов сжатия, использующих информацию контексте, к (обычно более простой) разработке алгоритмов сжатия нулевого порядка. Эффективность этой парадигмы описывается следующей теоремой. | |||
Теорема 1 ([Ферраджина и др., 2005). Пусть A – алгоритм сжатия, который сжимает любую строку x до размера не более jxjH0(x) + r]\x\ + fi бит. | |||
Механизм усиления степени сжатия, примененный к A, дает выходное значение, размер которого ограничен jsj Hk(s) + log jsj + r)\s\ + O{\S\k) бит одновременно для всех k > 0. Учитывая A, механизм усиления привносит в процесс сжатия дополнительные накладные расходы на память в размере O(jsj log jsj) бит, но не вносит дополнительных затрат времени. □ | |||
Аналогичный результат имеет место и для модифицированной энтропии (однако доказать его намного сложнее): пусть дан алгоритм сжатия A, который сжимает любую строку x до не более чем X\x\ H*(x) + fi бит. Механизм усиления степени сжатия дает выходное значение, размер которого ограничен A|s| H*(s) + log jsj + O(\E\k) ) бит одновременно для всех k > 0. В работе [ ] авторы также показали, что ни один алгоритм сжатия, удовлетворяющий некоторым мягким предположениям относительно его внутренних принципов работы, не способен получить схожую границу, не включающую одновременно мультипликативный коэффициент Я и аддитивный логарифмический терм. Кроме того, в [ ] была предложена конкретизация усилителя, которая сжимает любую строку s до не более чем 2:5|s|H*(s) +log jsj + O(\E\k) бит. Эта граница аналитически превосходит границы, доказанные для лучших существующих алгоритмов сжатия, включая алгоритмы Лемпеля-Зива и Барроуза-Уилера и алгоритм PPM. | |||
== Применение == | |||
Помимо естественного применения в области сжатия данных, механизмы повышения степени сжатия также использовались для разработки сжатых полнотекстовых индексов [8]. | |||
== Открытые вопросы == | |||