4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 30: | Строка 30: | ||
Запросы display(i, j) общего вида основываются на регулярной выборке из текста. Каждая текстовая позиция вида <math>j' \cdot s</math>, где s – частота дискретизации, хранится вместе с <math>SA^{-1} [j \cdot s]</math>, на | Запросы display(i, j) общего вида основываются на регулярной выборке из текста. Каждая текстовая позиция вида <math>j' \cdot s</math>, где s – частота дискретизации, хранится вместе с <math>SA^{-1} [j \cdot s]</math>, указывающей на нее позицией суффиксного массива. Для выполнения запроса display(i, j) мы начинаем с наименьшей выбранной текстовой позиции <math>j' \cdot s > j</math> и применяем обращение процедуры BWT, начиная с <math>SA^{-1} [j \cdot s]</math> вместо i*. Это дает нам символы с <math>j' \cdot s - 1</math> до i в обратном порядке и требует не более j - i + s шагов. | ||
Кроме того, оказывается, что то же самое двухкомпонентное выражение LF[i] позволяет эффективно выполнять запросы типа count(P). Идея заключается в том, что если известен диапазон суффиксного массива, скажем <math>SA[sp_i, ep_i]</math>, такого что единственными суффиксами, содержащими P[i, m] в качестве префикса, являются суффиксы <math>T[SA[sp_i], n], T[SA[sp_i + 1], n], ..., T[SA[ep_i], n]</math>, то новый диапазон <math>SA[sp_{i - 1}, ep_{i - 1}]</math>, суффиксы которого содержат P[i – 1, m] в качестве префикса, можно вычислить следующим образом: <math>sp_{i - 1} = C(P[i - 1]) + rank_{p_{[i - 1]}}(sp_i - 1) + 1</math> и <math>ep_{i - 1} = C(P[i - 1]) + rank_{p_{[i- 1]}}(ep_i)</math>. После этого достаточно просканировать шаблон ''в обратном порядке'' и вычислить значения C() и <math>rank_c()</math> 2m раз, чтобы определить (возможно, пустой) диапазон суффиксного массива, в котором все суффиксы начинаются с полной P. Возврат <math>ep_1 - sp_1 + 1</math> отвечает на запрос count(P), вообще не требуя наличия суффиксного массива. | Кроме того, оказывается, что то же самое двухкомпонентное выражение LF[i] позволяет эффективно выполнять запросы типа count(P). Идея заключается в том, что если известен диапазон суффиксного массива, скажем <math>SA[sp_i, ep_i]</math>, такого что единственными суффиксами, содержащими P[i, m] в качестве префикса, являются суффиксы <math>T[SA[sp_i], n], T[SA[sp_i + 1], n], ..., T[SA[ep_i], n]</math>, то новый диапазон <math>SA[sp_{i - 1}, ep_{i - 1}]</math>, суффиксы которого содержат P[i – 1, m] в качестве префикса, можно вычислить следующим образом: <math>sp_{i - 1} = C(P[i - 1]) + rank_{p_{[i - 1]}}(sp_i - 1) + 1</math> и <math>ep_{i - 1} = C(P[i - 1]) + rank_{p_{[i- 1]}}(ep_i)</math>. После этого достаточно просканировать шаблон ''в обратном порядке'' и вычислить значения C() и <math>rank_c()</math> 2m раз, чтобы определить (возможно, пустой) диапазон суффиксного массива, в котором все суффиксы начинаются с полной строки шаблона P. Возврат <math>ep_1 - sp_1 + 1</math> отвечает на запрос count(P), вообще не требуя наличия суффиксного массива. | ||
Строка 39: | Строка 39: | ||
Теперь рассмотрим потребность в памяти. Значения 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 и достигает следующего результата: | Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице размером <math>\sigma \; log_2 \; n</math> бит. <math>T^{bwt}[i]</math> можно вычислить за время <math>O(\sigma)</math> путем проверки, для какого <math>c</math> выполняется утверждение <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 и достигает следующего результата: | ||
Строка 45: | Строка 45: | ||
Исходный FM-индекс налагает серьезные ограничения на размер алфавита. В последующих работах эти ограничения были устранены. С концептуальной точки зрения самый простой способ | Исходный FM-индекс налагает серьезные ограничения на размер алфавита. В последующих работах эти ограничения были устранены. С концептуальной точки зрения самый простой способ получить более дружественный к алфавитам экземпляр FM-индекса заключается в построении ''дерева вейвлетов'' [5] на <math>T^{bwt}</math>. Это бинарное дерево над алфавитом <math>\Sigma</math>, устроенное таким образом, что каждый узел v обрабатывает подмножество алфавита S(v), которое делит между своими детьми. Корень обрабатывает <math>\Sigma</math>, а каждый лист обрабатывает один символ. Каждый узел v кодирует такие позиции i таким образом, что <math>T^{bwt}[i] \in S(v)</math>. Для этих позиций в узле v хранится только битовый вектор, указывающий, какая из них направляется налево, а какая – направо. Битовые векторы узла предварительно обрабатываются для выполнения запросов <math>rank_1()</math> за константное время, используя o(n)-битные структуры данных [6, 12]. Гросси и др. [4] показали, что дерево вейвлетов, построенное с использованием кодировки [12], занимает <math>nH_0 + o(n \; log \; \sigma)</math> бит. После этого легко смоделировать один запрос <math>rank_c()</math> при помощи <math>log_2 \; \sigma</math> запросов <math>rank_1()</math>. С теми же затратами можно получить <math>T^{bwt}[i]</math>. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат: | ||
Строка 54: | Строка 54: | ||
'''Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером <math>nH_k + o(n \; log \; \sigma)</math> бит, имеющего ту же временную | '''Теорема 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>.''' | ||
Недавно проведенный анализ [8] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит <math>nH_k + o(n \; log \; \sigma)</math>, что теоретически делает | Недавно проведенный анализ [8] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит <math>nH_k + o(n \; log \; \sigma)</math>, что теоретически делает использование форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее. | ||
== Применение == | == Применение == | ||
Строка 63: | Строка 63: | ||
== Ссылки на код и наборы данных == | == Ссылки на код и наборы данных == | ||
Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и | Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и результаты экспериментальных сравнений. | ||
== См. также == | == См. также == |
правок