Индексирование сжатого текста: различия между версиями

Перейти к навигации Перейти к поиску
Строка 36: Строка 36:




Для локализации каждого такого вхождения <math>SA[i], sp_1 \le i \le ep_1</math>, можно вычислить последовательность i, LF[i], LF[LF[i]], ... до тех пор, пока не будет достигнут <math>LF^k [i]</math>, являющийся выбранной позицией суффиксного массива и, таким образом, явно хранящийся в структуре выборки, предназначенной для запросов display(i, j). Тогда <math>SA[i] = SA[LF^k[i]] + k</math>. Поскольку мы перемещаемся по тексту практически последовательно, мы не можем сделать в этом процессе более s шагов.
Для локализации каждого такого вхождения <math>SA[i], sp_1 \le i \le ep_1</math>, можно вычислить последовательность <math>i, LF[i], LF[LF[i]], ...</math> до тех пор, пока не будет достигнут <math>LF^k [i]</math>, являющийся выбранной позицией суффиксного массива и, таким образом, явно хранящийся в структуре выборки, предназначенной для запросов display(i, j). Тогда <math>SA[i] = SA[LF^k[i]] + k</math>. Поскольку мы перемещаемся по тексту практически последовательно, мы не можем сделать в этом процессе более s шагов.




Строка 48: Строка 48:




Теорема 3 (Макинен и Наварро, 2005 [3]). Задача CTI может быть решена с помощью так называемого сокращенного суффиксного массива (Succinct Suffix Array SSA) размером пЩ + o(n log cr) бит, выполняющего операцию count(P) за время O(m(1 + log a/ log log n)), locate(P) – за время O(log1+e n log al log log n) на одно вхождение, а display(i, j) – за время O((j - i + log1+e n) log cr/log log n). Здесь H0 – энтропия нулевого порядка для T,a = o(n), а e > 0 – произвольная константа.
'''Теорема 3 (Мэкинен и Наварро, 2005 [3]). Задача CTI может быть решена с помощью так называемого сокращенного суффиксного массива (Succinct Suffix Array, SSA) размером <math>nH_0 + o(n \; log \; \sigma)</math> бит, выполняющего операцию count(P) за время <math>O(m(1 + log \; \sigma / log \; log \; n))</math>, locate(P) – за время <math>O(log^{1 + \epsilon} \; n \; log \; \sigma / log \; log \; n)</math> на одно вхождение, а display(i, j) – за время <math>O((j - i + log^{1 + \epsilon} \; n) log \; \sigma / log \; log \; n)</math>. Здесь <math>H_0</math> – энтропия нулевого порядка для T, <math>\sigma = o(n)</math>, а <math>\epsilon > 0</math> – произвольная константа.'''




Ферраджина и др. [ ] разработали технику под названием «форсирование сжатия» (compression boosting), которая находит оптимальное разбиение <math>T^{bwt}</math>, такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов rankc() для отдельных деревьев вейвлетов:
Ферраджина и др. [2] разработали технику под названием ''форсирование сжатия'' (compression boosting), которая находит оптимальное разбиение <math>T^{bwt}</math>, такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов <math>rank_c()</math> для отдельных деревьев вейвлетов:




Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером nHk + o(n log cr) бит, имеющего ту же временную сложностьи те же ограничения, что и SSA при k < cdog^ n для любого константного 0 < a < 1.
'''Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером <math>nH_k + o(n \; log \; \sigma)</math> бит, имеющего ту же временную сложностьи те же ограничения, что и SSA, при <math>k \le \alpha \; log_{\sigma}\; n</math> для любого константного <math>0 < \alpha < 1</math>.'''




Недавно проведенный анализ [ ] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит nHk + o(n log a), что теоретически делает подход на базе форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее.
Недавно проведенный анализ [8] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит <math>nH_k + o(n \; log \; \sigma)</math>, что теоретически делает подход на базе форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее.


== Применение ==
== Применение ==
Источник — http://pco.iis.nsk.su/wega/index.php/Индексирование_сжатого_текста