Сжатый суффиксный массив
Ключевые слова и синонимы
Создание сжатого полнотекстового индекса; сжатое суффиксное дерево
Постановка задачи
Пусть дана текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math] над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача создания сжатого полнотекстового индекса (compressed full-text indexing, CFTI) заключается в построении экономичной по объему памяти структуры данных, способной эффективно моделировать функциональность полнотекстового индекса, построенного на основе T.
Простым примером полнотекстового индекса является суффиксный массив A[1, n], содержащий перестановку интервала [1, n], такую, что T[A[i], n] < T[A[i + 1], n] для всех [math]\displaystyle{ 1 \le i \lt n }[/math], где отношение "<" между строками обозначает лексикографический порядок. Используя суффиксный массив, можно найти вхождения заданного шаблона [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math] в строке T с помощью двух бинарных поисков за время O(m log n).
Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение называется сжатым суффиксным массивом. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения [math]\displaystyle{ A^{-1} [j] = i }[/math] для любого заданного j.
Если сжатый полнотекстовый индекс функционирует без текста и содержит достаточно информации для получения любой подстроки T, такой индекс называется самоиндексом, так как его можно использовать в качестве представления T. См. статью «Индексирование сжатого текста» с изложением альтернативного подхода к самоиндексированию, а также работу [9] с исчерпывающим обзором по данной теме.
Задача CFTI может быть сформулирована для любого полнотекстового индекса при условии, что набор операций, которые должна поддерживать структура данных, строго определен. Например, сжатое суффиксное дерево должно воспроизводить все операции классических суффиксных деревьев.
Классические полнотекстовые индексы занимают [math]\displaystyle{ O(n \; log \; n) }[/math] бит, обычно с поправкой на довольно большой константный коэффициент. Типичные цели задачи CFTI могут быть охарактеризованы степенью амбициозности; например, необходимо найти структуру, удовлетворяющую одному из следующих требований к объему памяти:
1) пропорционально размеру текста, т. е. [math]\displaystyle{ O(n \; log \; \sigma) }[/math] бит;
2) асимптотически оптимально относительно размера текста, т. е. [math]\displaystyle{ n \; log \; \sigma (1 + o(1)) }[/math] бит;
3) пропорционально размеру сжатого текста, т. е. [math]\displaystyle{ O(nH_k) }[/math] бит, где [math]\displaystyle{ O(H_k) }[/math] — это (эмпирическая) энтропия k-го порядка строки T //где [math]\displaystyle{ H_k }[/math] — минимальное среднее количество бит, необходимое для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение//;
или даже 4) асимптотически оптимально относительно размера сжатого текста, т. е. [math]\displaystyle{ nH_k + o(n \; log \; \sigma) }[/math] бит.
Основные результаты
Первое решение задачи предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством функции [math]\displaystyle{ \Psi }[/math]:
Определение 1. Пусть дан суффиксный массив A[1, n]. Функция [math]\displaystyle{ \Psi : [1, n] \to [1, n] }[/math] определена таким образом, что для всех [math]\displaystyle{ 1 \le i \lt n }[/math] выполняется соотношение [math]\displaystyle{ A[\Psi(i)] = A[i] + 1 }[/math]. Исключением является A[1] = n, в этом случае имеет место [math]\displaystyle{ A[\Psi(1)] = 1 }[/math], так что функция [math]\displaystyle{ \Psi }[/math] является перестановкой.
Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на [math]\displaystyle{ \Psi }[/math] //далее приводится описание, близкое к изложенному в [9]//.
Рассмотрим первый уровень этой иерархической декомпозиции. Пусть [math]\displaystyle{ A_0 = A }[/math] – исходный суффиксный массив. Битовый вектор [math]\displaystyle{ B^0 [1, n] }[/math] определен таким образом, что [math]\displaystyle{ B^0 [i] = 1 }[/math] в том и только том случае, если A[i] четно. Кроме того, пусть [math]\displaystyle{ \Psi_0 [1, \lceil n/2 \rceil ] }[/math] содержит последовательность значений [math]\displaystyle{ \Psi(i) }[/math] для тех аргументов i, для которых [math]\displaystyle{ B^0[i] = 0 }[/math]. Наконец, пусть [math]\displaystyle{ A_1 [1, \lfloor n/2 \rfloor ] }[/math] будет подпоследовательностью [math]\displaystyle{ A_0 [1, n] }[/math], образованной четными значениями [math]\displaystyle{ A_0[i] }[/math], деленными на 2.
Тогда [math]\displaystyle{ A = A_0 }[/math] может быть представлен с использованием только [math]\displaystyle{ \Psi_0, B^0 }[/math] и [math]\displaystyle{ A_1 }[/math]. Чтобы извлечь A[i], сначала проверим, выполняется ли [math]\displaystyle{ B^0[i] = 1 }[/math]. Если это так, то A[i] (деленное на 2) встречается где-то в [math]\displaystyle{ A_1 }[/math]. Точное положение зависит от того, сколько единиц встречается в [math]\displaystyle{ B^0 }[/math] до позиции i, обозначенной как [math]\displaystyle{ rank(B^0, i) }[/math], т. е. [math]\displaystyle{ A[i] = 2 \cdot A_1[rank_1(B^0, i)] }[/math]. Если [math]\displaystyle{ B^0[i] = 0 }[/math], то элемент A[i] является нечетным и не представлен в [math]\displaystyle{ A_1 }[/math]. Однако в этом случае элемент [math]\displaystyle{ A[i] + 1 = A[\Psi(i)] }[/math] должен быть четным и, таким образом, должен быть представлен в [math]\displaystyle{ A_1 }[/math]. Так как [math]\displaystyle{ \Psi_0 }[/math] содержит только значения [math]\displaystyle{ \Psi }[/math], у которых [math]\displaystyle{ B^0[i] = 0 }[/math], из этого следует, что [math]\displaystyle{ A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]] }[/math]. После вычисления [math]\displaystyle{ A[\Psi(i)] }[/math] (для четных [math]\displaystyle{ \Psi(i) }[/math]) элементарно получаем [math]\displaystyle{ A[i] = A[\Psi(i)] - 1 }[/math].
Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять [math]\displaystyle{ A_1 }[/math], заменим его на [math]\displaystyle{ B^2 }[/math], [math]\displaystyle{ \Psi_2 }[/math] и [math]\displaystyle{ A_2 }[/math]. Продолжаем процесс до тех пор, пока [math]\displaystyle{ A_h }[/math] не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции rank за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы rank могли быть даны за постоянное время [4,7].
Удобно использовать [math]\displaystyle{ h = \lceil log \; log \; n \rceil }[/math], такое, что [math]\displaystyle{ n/2^h }[/math] записей [math]\displaystyle{ A_h }[/math], каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы [math]\displaystyle{ B^{\ell} }[/math] добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры rank добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов [math]\displaystyle{ \Psi_{\ell} }[/math]. Можно использовать следующую закономерность, обусловленную лексикографическим порядком:
Лемма 1. Пусть даны текст T[1, n], его суффиксный массив A[1, n] и соответствующая функция [math]\displaystyle{ \Psi }[/math]. Тогда неравенство [math]\displaystyle{ \Psi(i) \lt \Psi(i + 1) }[/math] выполняется всякий раз, когда [math]\displaystyle{ T_{A[i]} = T_{A[i+1]} }[/math].
Это свойство кусочно-линейного увеличения [math]\displaystyle{ \Psi }[/math] может быть использовано для представления каждого уровня [math]\displaystyle{ \Psi }[/math] при помощи [math]\displaystyle{ \frac{1}{2} \; n \; log \; \sigma }[/math] бит [3]. При использовании различного числа уровней возможны другие компромиссы:
Теорема 2 (Гросси и Виттер, 2005 [3]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение [math]\displaystyle{ A[i] }[/math] либо за время [math]\displaystyle{ O(log \; log \; n) }[/math] с использованием [math]\displaystyle{ n \; log \; \sigma \; log \; log \; n + O(n \; log \; log \; \sigma) }[/math] бит памяти, либо за время [math]\displaystyle{ O(log^{\epsilon} \; n) }[/math] с использованием [math]\displaystyle{ \frac{1}{\epsilon} \; n \; log \; \sigma + O(n \; log \; log \; \sigma) }[/math] бит памяти для любого [math]\displaystyle{ 0 \lt \epsilon \lt 1 }[/math].
Как следствие, моделирование классического бинарного поиска [5] для определения диапазона суффиксного массива, содержащего все вхождения шаблона P[1, m] в T[1, n], может быть выполнено за время [math]\displaystyle{ O(m \; log^{1 + \epsilon} \; n) }[/math] с использованием объема памяти, пропорционального размеру текста. Для сообщений о нахождении [math]\displaystyle{ occ }[/math] позиций вхождения требуется [math]\displaystyle{ occ \times log^{\epsilon} \; n }[/math] времени. При достаточно большом m этот процесс может быть ускорен [3].
Гросси и Виттер также демонстрируют, как модифицировать экономичное по объему памяти суффиксное дерево [8] для того, чтобы получить время поиска [math]\displaystyle{ O(m / log_{\sigma} \; n + log^{\epsilon} \; n) }[/math] для любой константы [math]\displaystyle{ 0 \lt \epsilon \lt 1 }[/math], используя [math]\displaystyle{ O(n \; log \; \sigma) }[/math] бит памяти.
Садаканэ [10] показал, как вышеприведенный сжатый суффиксный массив может быть преобразован в самоиндексируемый и одновременно может быть оптимизирован несколькими способами. Он обеспечивает прямой доступ не к A[i], а к любому префиксу T[A[i], n]. Этого по-прежнему достаточно для использования алгоритма бинарного поиска для обнаружения вхождений шаблона.
Садаканэ представляет и A, и T, используя полную функцию [math]\displaystyle{ \Psi }[/math] и несколько дополнительных структур. Предположим, что требуется сравнить P с T[A[i], n]. Для бинарного поиска необходимо извлечь из T[A[i], n] достаточное количество символов, чтобы его лексикографическое отношение к P стало понятным. Получить символ T[A[i]] легко: для этого можно использовать битовый вектор F[1, n], отмечающий суффиксы A[i], у которых первый символ отличается от такого же символа в A[i - 1]. После предварительной обработки вектора F для запросов rank вычисление [math]\displaystyle{ j = rank_1(F, i) }[/math] дает [math]\displaystyle{ T[A[i]] = c_j }[/math], где [math]\displaystyle{ c_j }[/math] – это j-ый наименьший символ алфавита. Как только [math]\displaystyle{ T[A[i]] = c_j }[/math] будет определен таким образом, необходимо получить следующий символ, [math]\displaystyle{ T[A[i] + 1] }[/math]. Но [math]\displaystyle{ T[A[i] + 1] = T[A[\Psi(i)]] }[/math], поэтому можно просто перейти к [math]\displaystyle{ i' = \Psi(i) }[/math] и продолжать извлекать символы тем же способом, сколько потребуется. Следует отметить, что в большинстве случаев |P| = m символов достаточно для сравнения с P. Таким образом, моделирование бинарного поиска выполняется за время O(m log n).
До этого момента было использовано [math]\displaystyle{ n + o(n) + \sigma \; log \; \sigma }[/math] бит памяти для [math]\displaystyle{ F }[/math] и [math]\displaystyle{ \Sigma }[/math]. Садаканэ [10] дает улучшенное представление для [math]\displaystyle{ \Psi }[/math], используя [math]\displaystyle{ nH_0 + O(n \; log \; log \; \sigma) }[/math] бит, где [math]\displaystyle{ H_0 }[/math] – энтропия T нулевого порядка.
Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения [math]\displaystyle{ A^{-1} [j] }[/math]. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя [math]\displaystyle{ i = A^{-1}[p] }[/math], а затем, как и прежде, продолжая извлекать r - p + 1 первых символов суффикса T[A[i], n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый:
Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ представляет собой самоиндекс, занимающий [math]\displaystyle{ \frac{1}{\epsilon}nH_0 + O(n \; log \; log \; \sigma) }[/math] бит и поддерживающий извлечение значений [math]\displaystyle{ A[i] }[/math] и [math]\displaystyle{ A^{-1}[j] }[/math] за время [math]\displaystyle{ O(log^{\epsilon} \; n) }[/math], подсчет вхождений шаблона за время [math]\displaystyle{ O(m \; log \; n) }[/math] и отображение любой подстроки T длины [math]\displaystyle{ \ell }[/math] за время [math]\displaystyle{ O(\ell + log^{\epsilon} \; n) }[/math], где [math]\displaystyle{ 0 \lt \epsilon \le 1 }[/math] — произвольная константа.
Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых [math]\displaystyle{ \Psi }[/math]–функцией, в сочетании с возможностями индексирования их новой элегантной структуры данных – дерева вейвлетов. Им удалось, помимо прочих результатов, получить следующий компромисс:
Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупта и Виттера представляет собой самоиндекс, занимающий [math]\displaystyle{ \frac{1}{\epsilon}nH_k + o(n \; log \; \sigma) }[/math] бит и поддерживающий извлечение значений [math]\displaystyle{ A[i] }[/math] и [math]\displaystyle{ A^{-1}[j] }[/math] за время [math]\displaystyle{ O(log^{1 + \epsilon} n) }[/math], подсчет вхождений шаблона за время [math]\displaystyle{ O(m \; log \; \sigma + log^{2 + \epsilon} n) }[/math] и отображение любой подстроки T длины [math]\displaystyle{ \ell }[/math] за время [math]\displaystyle{ O(\ell / log_{\sigma} n + log^{1+\epsilon} n) }[/math]. Здесь [math]\displaystyle{ 0 \lt \epsilon \le 1 }[/math] — произвольная константа, [math]\displaystyle{ k \le \alpha log_{\sigma} n }[/math] для некоторой константы [math]\displaystyle{ 0 \lt \alpha \lt 1 }[/math].
В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии они отметили, что простая кодировка [math]\displaystyle{ \Psi }[/math]-значений дает одну и ту же границу [math]\displaystyle{ nH_k }[/math], не требуя предварительного фиксирования k [1].
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает <nath>O(n \; log \; \sigma)</math> бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n).
Применение
Сжатые суффиксные массивы можно применять в тех же областях, что и классические суффиксные массивы и деревья, с дополнительным преимуществом масштабирования до наборов данных значительно большей величины.
Ссылка на код
В соответствующем разделе статьи «Индексирование сжатого текста» см. ссылки на реализации сжатых суффиксных массивов, см. также в http://www.cs.helsinki.fi/group/suds/cst реализацию сжатых суффиксных деревьев Садаканэ.
См. также
Литература
1. Foschini, L., Grossi, R., Gupta, A., Vitter, J.S.: When indexing equals compression: Experiments with compressing suffix arrays and applications. ACM Trans. Algorithms 2(4), 611-639 (2006)
2. Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, 12-14 January, pp. 841-850 (2003)
3. Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378^07 (2006)
4. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, 30 October - 1 November, pp. 549-554(1989)
5. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935-948 (1993)
6. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407-430 (2001)
7. Munro, I.: Tables. In: Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LNCS, vol. 1180, Hyderabad, 18-20 December, pp. 37^2(1996)
8. Munro, I., Raman, V., Rao, S.: Space efficient suffix trees. J. Algorithms 39(2), 205-222 (2001)
9. Navarro, G., Makinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), Article 2 (2007)
10. Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294-313 (2003)
11. Sadakane, K.: Compressed suffix trees with full functionality. Theor. Comput. Syst. 41,589-607 (2007)