Аноним

Сжатый суффиксный массив: различия между версиями

Материал из WEGA

Сжатый суффиксный массив (посмотреть исходный код)

Версия от 15:13, 18 июня 2020

168 байт добавлено ,  18 июня 2020
м
→‎Основные результаты
 
(не показано 8 промежуточных версий этого же участника)
Строка 9: Строка 9:




Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение и называется ''сжатым суффиксным массивом''. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения <math>A^{-1} [j] = i</math> для любого заданного j.
Формулировка связанной с суффиксными массивами задачи CFTI проста: необходимо найти экономичную по объему памяти структуру данных, поддерживающую эффективное извлечение значения A[i] для любого i. Такое решение называется ''сжатым суффиксным массивом''. Обычно сжатые суффиксные массивы также поддерживают получение обратного значения <math>A^{-1} [j] = i</math> для любого заданного j.




Строка 24: Строка 24:
2) асимптотически оптимально относительно размера текста, т. е. <math>n \; log \; \sigma (1 + o(1))</math> бит;
2) асимптотически оптимально относительно размера текста, т. е. <math>n \; log \; \sigma (1 + o(1))</math> бит;


3) пропорционально размеру ''сжатого'' текста, т. е. <math>O(nH_k)</math> бит, где <math>O(H_k)</math> — это (эмпирическая) ''энтропия k-го порядка'' строки T ''//где <math>H_k</math> — минимальное среднее количество бит, необходимых для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение//'';
3) пропорционально размеру ''сжатого'' текста, т. е. <math>O(nH_k)</math> бит, где <math>O(H_k)</math> — это (эмпирическая) ''энтропия k-го порядка'' строки T ''//где <math>H_k</math> — минимальное среднее количество бит, необходимое для кодирования одного символа с помощью любого алгоритма сжатия, который фиксирует кодовое слово на основе контекста k-го символа, следующего за кодируемым символом. В [6] дано более формальное определение//'';


или даже
или даже
4) асимптотически оптимально относительно размера сжатого текста, т. е. <math>O(nH_k) + o(n \; log \; \sigma)</math> бит.
4) асимптотически оптимально относительно размера сжатого текста, т. е. <math>nH_k + o(n \; log \; \sigma)</math> бит.


== Основные результаты ==
== Основные результаты ==
Первое решение проблемы предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством функции <math>\Psi</math>:
Первое решение задачи предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством функции <math>\Psi</math>:




Строка 36: Строка 36:




Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на <math>\Psi</math> ''//далее приводится описание, близкое к изложенному в [9]//''. рассмотрим первый уровень этой иерархической декомпозиции. Пусть <math>A_0 = A</math> – исходный суффиксный массив. Битовый вектор <math>B^0 [1, n]</math> определен таким образом, что <math>B^0 [i] = 1</math> в том и только том случае, если A[i] четно. Кроме того, пусть <math>\Psi_0 [1, \lceil n/2 \rceil ]</math> содержит последовательность значений <math>\Psi(i)</math> для тех аргументов i, для которых <math>B^0[i] = 0</math>. Наконец, пусть <math>A_1 [1, \lfloor n/2 \rfloor ]</math> будет подпоследовательностью <math>A_0 [1, n]</math>, образованной четными значениями <math>A_0[i]</math>, деленными на 2.
Гросси и Виттер используют иерархическую декомпозицию массива А, основанную на <math>\Psi</math> ''//далее приводится описание, близкое к изложенному в [9]//''.


Рассмотрим первый уровень этой иерархической декомпозиции. Пусть <math>A_0 = A</math> – исходный суффиксный массив. Битовый вектор <math>B^0 [1, n]</math> определен таким образом, что <math>B^0 [i] = 1</math> в том и только том случае, если A[i] четно. Кроме того, пусть <math>\Psi_0 [1, \lceil n/2 \rceil ]</math> содержит последовательность значений <math>\Psi(i)</math> для тех аргументов i, для которых <math>B^0[i] = 0</math>. Наконец, пусть <math>A_1 [1, \lfloor n/2 \rfloor ]</math> будет подпоследовательностью <math>A_0 [1, n]</math>, образованной четными значениями <math>A_0[i]</math>, деленными на 2.


Тогда <math>A = A_0</math> может быть представлен с использованием только <math>\Psi_0, B^0</math> и <math>A_1</math>. Чтобы извлечь A[i], сначала проверим, выполняется ли <math>B^0[i] = 1</math>. Если это так, то A[i] было разделено на 2 где-то в <math>A_1</math>. Точное положение зависит от того, сколько единиц встречается в <math>B^0</math> до позиции i, обозначенной как <math>rank(B^0, i)</math>, т. е. <math>A[i] = 2 \cdot A_1[rank_1(B^0, i)]</math>. Если B°[i] = 0, то A[i] является нечетным и не представлен в <math>A_1</math>. Однако в этом случае элемент <math>A[i] + 1 = A[\Psi(i)]</math> должен быть четным и, таким образом, должен быть представлен в <math>A_1</math>. Так как <math>\Psi_0</math> содержит только значения <math>\Psi</math>, у которых <math>B^0[i] = 0</math>, из этого следует, что <math>A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]]</math>. После вычисления <math>A[\Psi(i)]</math> (для четных <math>\Psi(i)</math>) элементарно получаем <math>A[i] = A[\Psi(i)] - 1</math>.


Тогда <math>A = A_0</math> может быть представлен с использованием только <math>\Psi_0, B^0</math> и <math>A_1</math>. Чтобы извлечь A[i], сначала проверим, выполняется ли <math>B^0[i] = 1</math>. Если это так, то A[i] (деленное на 2) встречается где-то в <math>A_1</math>. Точное положение зависит от того, сколько единиц встречается в <math>B^0</math> до позиции i, обозначенной как <math>rank(B^0, i)</math>, т. е. <math>A[i] = 2 \cdot A_1[rank_1(B^0, i)]</math>. Если <math>B^0[i] = 0</math>, то элемент A[i] является нечетным и не представлен в <math>A_1</math>. Однако в этом случае элемент <math>A[i] + 1 = A[\Psi(i)]</math> должен быть четным и, таким образом, должен быть представлен в <math>A_1</math>. Так как <math>\Psi_0</math> содержит только значения <math>\Psi</math>, у которых <math>B^0[i] = 0</math>, из этого следует, что <math>A[\Psi(i)] = A[\Psi_0[rank_0(B^0, i)]]</math>. После вычисления <math>A[\Psi(i)]</math> (для четных <math>\Psi(i)</math>) элементарно получаем <math>A[i] = A[\Psi(i)] - 1</math>.


Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять <math>A_1</math>, замените его на <math>B^2</math>, <math>\Psi_2</math> и <math>A_2</math>. Продолжайте процесс до тех пор, пока <math>A_h</math> не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции rank за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы rank могли быть даны за постоянное время [4,7].


Эта идея может быть использована рекурсивно. Вместо того, чтобы представлять <math>A_1</math>, заменим его на <math>B^2</math>, <math>\Psi_2</math> и <math>A_2</math>. Продолжаем процесс до тех пор, пока <math>A_h</math> не станет достаточно мал, чтобы быть представленным в явном виде. Сложность будет равна O(h), предполагая выполнение операции ''rank'' за постоянное время; к битовому вектору длины n можно прикрепить o(n) бит структур данных так, чтобы ответы на запросы ''rank'' могли быть даны за постоянное время [4,7].


Удобно использовать <math>h = \lceil log \; log \; n \rceil</math>, так что <math>n/2^h</math> записей <math>A_h</math>, каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы <math>B^{\ell}</math> добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры rank добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов <math>\Psi_{\ell}</math>. Можно использовать следующую закономерность, обусловленную лексикографическим порядком:
 
Удобно использовать <math>h = \lceil log \; log \; n \rceil</math>, такое, что <math>n/2^h</math> записей <math>A_h</math>, каждая из которых требует O(log n) бит, занимают суммарно O(n) бит. Все массивы <math>B^{\ell}</math> добавляют максимум 2n бит, так как их длина уменьшается вдвое на каждом следующем уровне, а их дополнительные структуры ''rank'' добавляют дополнительно o(n) бит. Единственной нерешенной задачей остается представление массивов <math>\Psi_{\ell}</math>. Можно использовать следующую закономерность, обусловленную лексикографическим порядком:




Строка 51: Строка 53:




Это свойство кусочно-линейного увеличения <math>\Psi</math> может быть использовано для представления каждого уровня <math>\Psi</math> при помощи <math>\frac{1}{2} \; n \; log \; \sigma</math> бит [3 ]. При использовании различного числа уровней возможны другие компромиссы:
Это свойство кусочно-линейного увеличения <math>\Psi</math> может быть использовано для представления каждого уровня <math>\Psi</math> при помощи <math>\frac{1}{2} \; n \; log \; \sigma</math> бит [3]. При использовании различного числа уровней возможны другие компромиссы:




'''Теорема 2 (Гросси и Виттер, 2005 [3]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение A[i] либо за время <math>O(log \; log \; n)</math> с использованием  <math>n \; log \; \sigma \; log \; log \; n + O(n \; log \; log \; \sigma)</math> бит памяти, либо за время <math>O(log^{\epsilon} \; n)</math> с использованием <math>\frac{1}{\epsilon} \; n \; log \; \sigma + O(n \; log \; log \; \sigma)</math> бит памяти для любого <math>0 < \epsilon < 1</math>.'''
'''Теорема 2 (Гросси и Виттер, 2005 [3]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение <math>A[i]</math> либо за время <math>O(log \; log \; n)</math> с использованием  <math>n \; log \; \sigma \; log \; log \; n + O(n \; log \; log \; \sigma)</math> бит памяти, либо за время <math>O(log^{\epsilon} \; n)</math> с использованием <math>\frac{1}{\epsilon} \; n \; log \; \sigma + O(n \; log \; log \; \sigma)</math> бит памяти для любого <math>0 < \epsilon < 1</math>.'''




Строка 60: Строка 62:




Гросси и Виттер также демонстрируют, как модифицировать экономичное по объему памяти суффиксное дерево [8], чтобы получить время поиска <math>O(m / log_{\sigma} \; n + log^{\epsilon} \; n)</math> для любой константы <math>0 < \epsilon < 1</math>, используя <math>O(n \; log \sigma)</math> бит памяти.
Гросси и Виттер также демонстрируют, как модифицировать экономичное по объему памяти суффиксное дерево [8] для того, чтобы получить время поиска <math>O(m / log_{\sigma} \; n + log^{\epsilon} \; n)</math> для любой константы <math>0 < \epsilon < 1</math>, используя <math>O(n \; log \; \sigma)</math> бит памяти.


   
   
Строка 72: Строка 74:




Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r — p + 1 первых символов суффикса T[A[i], n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый:
Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r - p + 1 первых символов суффикса T[A[i], n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый:




'''Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ — это самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_0 + O(n \; log \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{\epsilon} \; n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell + log^{\epsilon} \; n)</math>, где <math>0 < \epsilon < 1</math> — произвольная константа.'''
'''Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ представляет собой самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_0 + O(n \; log \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{\epsilon} \; n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell + log^{\epsilon} \; n)</math>, где <math>0 < \epsilon \le 1</math> — произвольная константа.'''




Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых <math>\Psi</math>–функцией, в сочетании с возможностями индексации их новой элегантной структуры данных – ''дерева вейвлетов''. Им удалось, помимо прочих результатов, получить следующий компромисс:
Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых <math>\Psi</math>–функцией, в сочетании с возможностями индексирования их новой элегантной структуры данных – ''дерева вейвлетов''. Им удалось, помимо прочих результатов, получить следующий компромисс:




'''Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупта и Виттера представляет собой самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_k + o(n \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{1 + \epsilon} n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; \sigma + log^{2 + \epsilon} n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell / log_{\sigma} n + log^{1+\epsilon} n)</math>. Здесь <math>0 < \epsilon \le 1</math> — произвольная константа, <math>k \le \alpha log_{\sigma} n</math> для некоторой константы <math>0 < \alpha < 1</math>.'''
'''Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупты и Виттера представляет собой самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_k + o(n \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{1 + \epsilon} n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; \sigma + log^{2 + \epsilon} n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell / log_{\sigma} n + log^{1+\epsilon} n)</math>. Здесь <math>0 < \epsilon \le 1</math> — произвольная константа, <math>k \le \alpha \; log_{\sigma} n</math> для некоторой константы <math>0 < \alpha < 1</math>.'''




В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии они отметили, что простая кодировка <math>\Psi</math>-значений дает одну и ту же границу nHk, не требуя предварительного фиксирования k [1].
В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии авторы отметили, что простая кодировка <math>\Psi</math>-значений дает ту же границу <math>nH_k</math>, не требуя предварительного фиксирования k [1].




Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает O(n log cr) бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n).
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает <math>O(n \; log \; \sigma)</math> бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n).


== Применение ==
== Применение ==
Строка 93: Строка 95:


== Ссылка на код ==
== Ссылка на код ==
В соответствующем разделе статьи «[[Индексация сжатого текста]]» см. ссылки на реализации сжатых суффиксных массивов, см. также в http://www.cs.helsinki.fi/group/suds/cst реализацию сжатых суффиксных деревьев Садаканэ.
В соответствующем разделе статьи «[[Индексирование сжатого текста]]» см. ссылки на реализации сжатых суффиксных массивов, см. также в http://www.cs.helsinki.fi/group/suds/cst реализацию сжатых суффиксных деревьев Садаканэ.


== См. также ==
== См. также ==
* [[Индексация сжатого текста]]
* [[Индексирование сжатого текста]]
* [[Последовательное точное сравнение строк]]
* [[Последовательное точное сравнение строк]]
* [[Индексация текста]]
* [[Индексирование текста]]


== Литература ==
== Литература ==
Irina
4446

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/14426...14435