Индексирование сжатого текста: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Экономичное по объему памяти индексирование текста; полнотекстовое индексирование сжатого текста; само-индексирование | |||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача '' | Пусть дана ''текстовая строка'' <math>T = t_1 t_2... t_n</math> над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''индексирования сжатого текста'' (compressed text indexing, CTI) заключается в ''замене'' строки T экономичной с точки зрения используемой памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса: | ||
• count(P): подсчитать, сколько раз заданная ''строка шаблона'' <math>P = p_1 p_2... p_m</math> встречается в T. | • count(P): подсчитать, сколько раз заданная ''строка шаблона'' <math>P = p_1 p_2... p_m</math> встречается в T. | ||
| Строка 12: | Строка 12: | ||
== Основные результаты == | == Основные результаты == | ||
Изящное решение задачи достигается за счет применения комбинации | Изящное решение задачи достигается за счет применения комбинации [[Преобразование Барроуза-Уилера|преобразования Барроуза-Уилера]] (Burrows-Wheeler Transform, BWT) [1] и структуры данных в виде суффиксного массива [9]. Суффиксный массив SA[1, n] строки T представляет собой перестановку текстовых позиций (1...n), в которой ''суффиксы'' T[i, n] перечислены в лексикографическом порядке. Таким образом, T[SA[i], n] – наименьший i-й суффикс. BWT определяется, во-первых, перестановкой <math>T^{bwt}</math> строки T, определяемой как <math>T^{bwt}[i] = T[SA[i] - 1]</math>, где T[0] = T[n], и во-вторых – числом <math>i^* = SA^{-1}</math>[1]. | ||
BWT обладает свойством, заключающимся в том, что символы, имеющие одинаковый контекст (т. е. строки, следующие за ними в T), в <math>T^{bwt}</math> являются последовательными. Это упрощает сжатие <math>T^{bwt}</math>, | BWT обладает свойством, заключающимся в том, что символы, имеющие одинаковый контекст (т. е. строки, следующие за ними в T), в <math>T^{bwt}</math> являются последовательными. Это упрощает сжатие <math>T^{bwt}</math>, позволяя достигать объема памяти, близкого к эмпирическим энтропиям высокого порядка [10]. С другой стороны, суффиксный массив является универсальным текстовым индексом, позволяющим, например, вести подсчет запросов за время O(m log n) (с использованием двух операций бинарного поиска в массиве SA), после чего можно локализовать вхождения за оптимальное время. | ||
Ферраджина и Манзини [3] обнаружили способ объединить высокую сжимаемость BWT и индексирующие свойства суффиксного массива. | Ферраджина и Манзини [3] обнаружили способ объединить высокую сжимаемость BWT и индексирующие свойства суффиксного массива. Предложенная ими структура, в сущности, представляет собой сжатое представление BWT плюс некоторые небольшие дополнительные структуры, делающие его пригодным для поиска. | ||
Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки | Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки запроса display(1, n)) достаточно инвертировать BWT. Для этого рассмотрим таблицу LF[1, n], определенную таким образом, что если выполнить перестановку T[i] в <math>T^{bwt}[j]</math>, а T[i - 1] – в <math>T^{bwt}[j']</math>, то LF[j] = j'. После этого можно сразу же извлечь T ''в обратном порядке'', напечатав <math>T^{bwt}[i^*] \cdot T^{bwt}[LF[i^*]] \cdot T^{bwt}[LF[LF[i^*]]]</math>... (по определению <math>T^{bwt}[i^*]</math> соответствует T[n]). | ||
| Строка 27: | Строка 27: | ||
'''Лемма 1 (Ферраджина и Манзини, 2005 [3])'''. <math>LF[i] = C(c) + rank_c(i)</math>, где <math>c = T^{bwt}[i]</math>, C(c) | '''Лемма 1 (Ферраджина и Манзини, 2005 [3])'''. <math>LF[i] = C(c) + rank_c(i)</math>, где <math>c = T^{bwt}[i]</math>, C(c) указывает, сколько раз в <math>T^{bwt}</math> встречаются символы меньше <math>c</math>, а <math>rank_c(i)</math> – сколько раз символ <math>c</math> встречается в <math>T^{bwt}[1, i]</math>. | ||
Запросы 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), вообще не требуя наличия суффиксного массива. | ||
Для локализации каждого такого вхождения <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 шагов. | ||
Теперь рассмотрим потребность в памяти. Значения 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>. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат: | ||
Теорема 3 ( | '''Теорема 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> – произвольная константа.''' | ||
Ферраджина и др. [ ] разработали технику под названием | Ферраджина и др. [2] разработали технику под названием ''форсирование сжатия'' (compression boosting), которая находит оптимальное разбиение <math>T^{bwt}</math>, такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов <math>rank_c()</math> для отдельных деревьев вейвлетов: | ||
Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером | '''Теорема 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 ограничены тем же количеством бит | Недавно проведенный анализ [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) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и результаты экспериментальных сравнений. | ||
== См. также == | == См. также == | ||
| Строка 69: | Строка 69: | ||
* [[Сжатый суффиксный массив]] | * [[Сжатый суффиксный массив]] | ||
* [[Последовательное точное сравнение строк]] | * [[Последовательное точное сравнение строк]] | ||
* [[ | * [[Индексирование текста]] | ||
== Литература == | == Литература == | ||
Текущая версия от 14:26, 7 апреля 2021
Ключевые слова и синонимы
Экономичное по объему памяти индексирование текста; полнотекстовое индексирование сжатого текста; само-индексирование
Постановка задачи
Пусть дана текстовая строка [math]\displaystyle{ T = t_1 t_2... t_n }[/math] над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача индексирования сжатого текста (compressed text indexing, CTI) заключается в замене строки T экономичной с точки зрения используемой памяти структурой данных, способной эффективно отвечать на основные запросы по сравнению строк и подстрок над T. Примеры типичных запросов, требующих ответов с использованием подобного индекса:
• count(P): подсчитать, сколько раз заданная строка шаблона [math]\displaystyle{ P = p_1 p_2... p_m }[/math] встречается в T.
• locate(P): вернуть местоположения всех вхождений P в T.
• display(i, j): вернуть T[i, j].
Основные результаты
Изящное решение задачи достигается за счет применения комбинации преобразования Барроуза-Уилера (Burrows-Wheeler Transform, BWT) [1] и структуры данных в виде суффиксного массива [9]. Суффиксный массив SA[1, n] строки T представляет собой перестановку текстовых позиций (1...n), в которой суффиксы T[i, n] перечислены в лексикографическом порядке. Таким образом, T[SA[i], n] – наименьший i-й суффикс. BWT определяется, во-первых, перестановкой [math]\displaystyle{ T^{bwt} }[/math] строки T, определяемой как [math]\displaystyle{ T^{bwt}[i] = T[SA[i] - 1] }[/math], где T[0] = T[n], и во-вторых – числом [math]\displaystyle{ i^* = SA^{-1} }[/math][1].
BWT обладает свойством, заключающимся в том, что символы, имеющие одинаковый контекст (т. е. строки, следующие за ними в T), в [math]\displaystyle{ T^{bwt} }[/math] являются последовательными. Это упрощает сжатие [math]\displaystyle{ T^{bwt} }[/math], позволяя достигать объема памяти, близкого к эмпирическим энтропиям высокого порядка [10]. С другой стороны, суффиксный массив является универсальным текстовым индексом, позволяющим, например, вести подсчет запросов за время O(m log n) (с использованием двух операций бинарного поиска в массиве SA), после чего можно локализовать вхождения за оптимальное время.
Ферраджина и Манзини [3] обнаружили способ объединить высокую сжимаемость BWT и индексирующие свойства суффиксного массива. Предложенная ими структура, в сущности, представляет собой сжатое представление BWT плюс некоторые небольшие дополнительные структуры, делающие его пригодным для поиска.
Сначала мы обратимся к извлечению произвольных подстрок из этого сжатого текстового представления, а затем рассмотрим возможности поиска. Для извлечения из структуры всего текста (то есть для поддержки запроса display(1, n)) достаточно инвертировать BWT. Для этого рассмотрим таблицу LF[1, n], определенную таким образом, что если выполнить перестановку T[i] в [math]\displaystyle{ T^{bwt}[j] }[/math], а T[i - 1] – в [math]\displaystyle{ T^{bwt}[j'] }[/math], то LF[j] = j'. После этого можно сразу же извлечь T в обратном порядке, напечатав [math]\displaystyle{ T^{bwt}[i^*] \cdot T^{bwt}[LF[i^*]] \cdot T^{bwt}[LF[LF[i^*]]] }[/math]... (по определению [math]\displaystyle{ T^{bwt}[i^*] }[/math] соответствует T[n]).
При поиске экономичного по памяти представления пространства массива LF Ферраджина и Манзини заметили, что каждый элемент LF[i] может быть выражен следующим образом:
Лемма 1 (Ферраджина и Манзини, 2005 [3]). [math]\displaystyle{ LF[i] = C(c) + rank_c(i) }[/math], где [math]\displaystyle{ c = T^{bwt}[i] }[/math], C(c) указывает, сколько раз в [math]\displaystyle{ T^{bwt} }[/math] встречаются символы меньше [math]\displaystyle{ c }[/math], а [math]\displaystyle{ rank_c(i) }[/math] – сколько раз символ [math]\displaystyle{ c }[/math] встречается в [math]\displaystyle{ T^{bwt}[1, i] }[/math].
Запросы display(i, j) общего вида основываются на регулярной выборке из текста. Каждая текстовая позиция вида [math]\displaystyle{ j' \cdot s }[/math], где s – частота дискретизации, хранится вместе с [math]\displaystyle{ SA^{-1} [j \cdot s] }[/math], указывающей на нее позицией суффиксного массива. Для выполнения запроса display(i, j) мы начинаем с наименьшей выбранной текстовой позиции [math]\displaystyle{ j' \cdot s \gt j }[/math] и применяем обращение процедуры BWT, начиная с [math]\displaystyle{ SA^{-1} [j \cdot s] }[/math] вместо i*. Это дает нам символы с [math]\displaystyle{ j' \cdot s - 1 }[/math] до i в обратном порядке и требует не более j - i + s шагов.
Кроме того, оказывается, что то же самое двухкомпонентное выражение LF[i] позволяет эффективно выполнять запросы типа count(P). Идея заключается в том, что если известен диапазон суффиксного массива, скажем [math]\displaystyle{ SA[sp_i, ep_i] }[/math], такого что единственными суффиксами, содержащими P[i, m] в качестве префикса, являются суффиксы [math]\displaystyle{ T[SA[sp_i], n], T[SA[sp_i + 1], n], ..., T[SA[ep_i], n] }[/math], то новый диапазон [math]\displaystyle{ SA[sp_{i - 1}, ep_{i - 1}] }[/math], суффиксы которого содержат P[i – 1, m] в качестве префикса, можно вычислить следующим образом: [math]\displaystyle{ sp_{i - 1} = C(P[i - 1]) + rank_{p_{[i - 1]}}(sp_i - 1) + 1 }[/math] и [math]\displaystyle{ ep_{i - 1} = C(P[i - 1]) + rank_{p_{[i- 1]}}(ep_i) }[/math]. После этого достаточно просканировать шаблон в обратном порядке и вычислить значения C() и [math]\displaystyle{ rank_c() }[/math] 2m раз, чтобы определить (возможно, пустой) диапазон суффиксного массива, в котором все суффиксы начинаются с полной строки шаблона P. Возврат [math]\displaystyle{ ep_1 - sp_1 + 1 }[/math] отвечает на запрос count(P), вообще не требуя наличия суффиксного массива.
Для локализации каждого такого вхождения [math]\displaystyle{ SA[i], sp_1 \le i \le ep_1 }[/math], можно вычислить последовательность [math]\displaystyle{ i, LF[i], LF[LF[i]], ... }[/math] до тех пор, пока не будет достигнут [math]\displaystyle{ LF^k [i] }[/math], являющийся выбранной позицией суффиксного массива и, таким образом, явно хранящийся в структуре выборки, предназначенной для запросов display(i, j). Тогда [math]\displaystyle{ SA[i] = SA[LF^k[i]] + k }[/math]. Поскольку мы перемещаемся по тексту практически последовательно, мы не можем сделать в этом процессе более s шагов.
Теперь рассмотрим потребность в памяти. Значения C() можно тривиально хранить в таблице размером [math]\displaystyle{ \sigma \; log_2 \; n }[/math] бит. [math]\displaystyle{ T^{bwt}[i] }[/math] можно вычислить за время [math]\displaystyle{ O(\sigma) }[/math] путем проверки, для какого [math]\displaystyle{ c }[/math] выполняется утверждение [math]\displaystyle{ rank_c(i) \ne rank_c(i - 1) }[/math]. Частоту выборки можно взять в виде [math]\displaystyle{ s = \Theta(log^{1 + \epsilon} \; n) }[/math], так что для выборок потребуется o(n) бит. Единственная реальная проблема заключается в предварительной обработке текста для запросов [math]\displaystyle{ rank_c() }[/math]. В последние годы в этой области велись интенсивные исследования и было предложено множество решений. Первый предложенный алгоритм строит несколько маленьких структур данных с частичной суммой поверх сжатого BWT и достигает следующего результата:
Теорема 2 (Ферраджина и Манзини, 2005 [3]). Задача CTI может быть решена с помощью так называемого FM-индекса (FM-Index, FMI) размером [math]\displaystyle{ 5 n H_k + o(n \; log \; \sigma) }[/math] бит, выполняющего операцию count(P) за время O(m), locate(P) за время [math]\displaystyle{ O(\sigma \; log^{1 + \epsilon} \; n) }[/math] на одно вхождение, а display(i, j) – за время [math]\displaystyle{ O(\sigma(j - i + log^{1 + \epsilon} \; n)) }[/math]. Здесь [math]\displaystyle{ H_k }[/math] – эмпирическая энтропия строки T k-го порядка, [math]\displaystyle{ \sigma = o(log \; n / log \; log \; n), k \le log_{\sigma}(n / log \; n) - \omega(1) }[/math], а [math]\displaystyle{ \epsilon \gt 0 }[/math] – произвольная константа.
Исходный FM-индекс налагает серьезные ограничения на размер алфавита. В последующих работах эти ограничения были устранены. С концептуальной точки зрения самый простой способ получить более дружественный к алфавитам экземпляр FM-индекса заключается в построении дерева вейвлетов [5] на [math]\displaystyle{ T^{bwt} }[/math]. Это бинарное дерево над алфавитом [math]\displaystyle{ \Sigma }[/math], устроенное таким образом, что каждый узел v обрабатывает подмножество алфавита S(v), которое делит между своими детьми. Корень обрабатывает [math]\displaystyle{ \Sigma }[/math], а каждый лист обрабатывает один символ. Каждый узел v кодирует такие позиции i таким образом, что [math]\displaystyle{ T^{bwt}[i] \in S(v) }[/math]. Для этих позиций в узле v хранится только битовый вектор, указывающий, какая из них направляется налево, а какая – направо. Битовые векторы узла предварительно обрабатываются для выполнения запросов [math]\displaystyle{ rank_1() }[/math] за константное время, используя o(n)-битные структуры данных [6, 12]. Гросси и др. [4] показали, что дерево вейвлетов, построенное с использованием кодировки [12], занимает [math]\displaystyle{ nH_0 + o(n \; log \; \sigma) }[/math] бит. После этого легко смоделировать один запрос [math]\displaystyle{ rank_c() }[/math] при помощи [math]\displaystyle{ log_2 \; \sigma }[/math] запросов [math]\displaystyle{ rank_1() }[/math]. С теми же затратами можно получить [math]\displaystyle{ T^{bwt}[i] }[/math]. Более поздние усовершенствования улучшили требования по времени, позволив получить, например, следующий результат:
Теорема 3 (Мэкинен и Наварро, 2005 [3]). Задача CTI может быть решена с помощью так называемого сокращенного суффиксного массива (Succinct Suffix Array, SSA) размером [math]\displaystyle{ nH_0 + o(n \; log \; \sigma) }[/math] бит, выполняющего операцию count(P) за время [math]\displaystyle{ O(m(1 + log \; \sigma / log \; log \; n)) }[/math], locate(P) – за время [math]\displaystyle{ O(log^{1 + \epsilon} \; n \; log \; \sigma / log \; log \; n) }[/math] на одно вхождение, а display(i, j) – за время [math]\displaystyle{ O((j - i + log^{1 + \epsilon} \; n) log \; \sigma / log \; log \; n) }[/math]. Здесь [math]\displaystyle{ H_0 }[/math] – энтропия нулевого порядка для T, [math]\displaystyle{ \sigma = o(n) }[/math], а [math]\displaystyle{ \epsilon \gt 0 }[/math] – произвольная константа.
Ферраджина и др. [2] разработали технику под названием форсирование сжатия (compression boosting), которая находит оптимальное разбиение [math]\displaystyle{ T^{bwt} }[/math], такое, что при сжатии каждого элемента по отдельности с использованием его модели нулевого порядка результат пропорционален энтропии k-го порядка. Этот подход можно совместить с идеей SSA, построив дерево вейвлетов отдельно для каждого отрезка и некоторые дополнительные структуры для решения глобальных запросов [math]\displaystyle{ rank_c() }[/math] для отдельных деревьев вейвлетов:
Теорема 4 ([Ферраджина и др. [4]). Задача CTI может быть решена с помощью так называемого дружественного к алфавитам FM-индекса (Alphabet-Friendly FM-Index, AF-FMI) размером [math]\displaystyle{ nH_k + o(n \; log \; \sigma) }[/math] бит, имеющего ту же временную сложность и те же ограничения, что и SSA, при [math]\displaystyle{ k \le \alpha \; log_{\sigma}\; n }[/math] для любого константного [math]\displaystyle{ 0 \lt \alpha \lt 1 }[/math].
Недавно проведенный анализ [8] показал, что требования к памяти простого алгоритма SSA ограничены тем же количеством бит [math]\displaystyle{ nH_k + o(n \; log \; \sigma) }[/math], что теоретически делает использование форсирования для достижения того же результата излишним. На практике реализации в работах [4, 7] намного превосходят реализации, построенные непосредственно на этой упрощенной идее.
Применение
Анализ последовательностей в биоинформатике, поиск и извлечение в запросах на восточных и агглютинирующих языках, мультимедийных потоках и даже сценариях работы со структурированными и традиционными базами данных.
Ссылки на код и наборы данных
Сайт Pizza-Chili (http://pizzachili.dcc.uchile.cl или http://pizzachili.di.unipi.it) содержит подборку стандартизированных реализаций библиотек, а также наборы данных и результаты экспериментальных сравнений.
См. также
- Преобразование Барроуза-Уилера
- Сжатый суффиксный массив
- Последовательное точное сравнение строк
- Индексирование текста
Литература
1. Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)
2. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52(4), 688-713(2005)
3. Ferragina, P. Manzini, G.: Indexing compressed texts. J. ACM 52(4), 552-581 (2005)
4. Ferragina, P., Manzini, G., Makinen, V., Navarro, G.: Compressed representation of sequences and full-text indexes. ACM Trans. Algorithms 3(2) Article 20 (2007)
5. Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841-850 (2003)
6. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549-554 (1989)
7. Makinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1),40-66 (2005)
8. Makinen, V., Navarro, G.: Dynamic entropy-compressed se quences and full-text indexes. In: Proc. 17th Annual Symposium on Combinatorial Pattern Matching (CPM). LNCS, vol. 4009, pp. 307-318 (2006) Extended version as TR/DCC-2006-10, Department of Computer Science, University of Chile, July 2006
9. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935-948 (1993)
10. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407-430 (2001)
11. Navarro, G., Makinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1) Article 2 (2007)
12. Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242 (2002)