4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 41: | Строка 41: | ||
Тогда <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 = 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>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>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>. Можно использовать следующую закономерность, обусловленную лексикографическим порядком: | ||
Строка 53: | Строка 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>.''' | ||
Строка 62: | Строка 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> бит памяти. | ||
Строка 74: | Строка 74: | ||
Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r | Садаканэ также показывает, как можно извлечь 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]). Сжатый суффиксный массив Садаканэ | '''Теорема 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> — произвольная константа.''' | ||
Строка 83: | Строка 83: | ||
'''Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, | '''Теорема 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 должно быть зафиксировано до построения индекса. Впоследствии | В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии авторы отметили, что простая кодировка <math>\Psi</math>-значений дает ту же границу <math>nH_k</math>, не требуя предварительного фиксирования k [1]. | ||
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает < | Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает <math>O(n \; log \; \sigma)</math> бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n). | ||
== Применение == | == Применение == |
правок