4446
правок
Индексирование сжатого текста: различия между версиями
Материал из WEGA
Индексирование сжатого текста (посмотреть исходный код)
Версия от 17:39, 21 апреля 2020
, 21 апреля 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице | Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице размером <math>\sigma \; log_2 \; n</math> бит. <math>T^{bwt}[i]</math> можно вычислить за время <math>O(\sigma)</math> путем проверки, для какого c выполняется утверждение <math>rank_c(i) \ne rank_c(i - 1)</math>. Частоту выборки можно взять в виде <math>s = \Theta(log^{1 + \epsilon} \; n)</math>, так что для выборок потребуется o(n) бит. Единственная реальная проблема заключается в предварительной обработке текста для запросов <math>rank_c()</math>. В последние годы в этой области велись интенсивные исследования и было предложено множество решений. Первый предложенный алгоритм строит несколько маленьких структур данных с частичной суммой поверх сжатого BWT и достигает следующего результата: | ||
Теорема 2 (Ферраджина и Манзини, 2005 [3]). Задача CTI может быть решена с помощью так называемого FM-индекса (FM-Index, FMI) размером | '''Теорема 2 (Ферраджина и Манзини, 2005 [3]). Задача CTI может быть решена с помощью так называемого FM-индекса (FM-Index, FMI) размером <math>5 n H_k + o(n \; log \; \sigma)</math> бит, выполняющего операцию count(P) за время O(m), locate(P) за время <math>O(\sigma \; log^{1 + \epsilon} \; n)</math> на одно вхождение, а display(i, j) – за время <math>O(\sigma(j - i + log^{1 + \epsilon} \; n))</math>. Здесь <math>H_k</math> – эмпирическая энтропия строки T k-го порядка, <math>\sigma = o(log \; n / log \; log \; n), k \le log_{\sigma}(n / log \; n) - \omega(1)</math>, а <math> \epsilon > 0</math> – произвольная константа.''' | ||
