4551
правка
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 49: | Строка 49: | ||
Лемма 1. Пусть даны текст T[1, n], его суффиксный массив A[1, n] и соответствующая функция <math>\Psi</math>. Тогда неравенство <math>\Psi(i) < \Psi(i + 1)</math> выполняется всякий раз, когда <math>T_{A[i]} = T_{A[i+1]}</math>. | Лемма 1. Пусть даны текст T[1, n], его суффиксный массив A[1, n] и соответствующая функция <math>\Psi</math>. Тогда неравенство <math>\Psi(i) < \Psi(i + 1)</math> выполняется всякий раз, когда <math>T_{A[i]} = T_{A[i+1]}</math>. | ||
Это свойство кусочно-линейного увеличения 4> может быть использовано для представления каждого уровня ^ при помощи j n log a бит [ ]. При использовании различного числа уровней возможны другие компромиссы: | |||
Теорема 2 (Гросси и Виттер, 2005 [ ]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение A[i] за время (i) O(loglogn) с использованием nlogcrloglog n + O(n log log cr) бит памяти или за время (ii) O(loge n) с использованием ^ n log cr + O(n log log cr) бит памяти для любых 0 < e < 1. | |||
Как следствие, моделирование классического бинарного поиска [5] для определения диапазона суффиксного массива, содержащего все вхождения шаблона P[1; m] в T[1; n], может быть выполнено за время O(m log1+e n) с использованием объема памяти, пропорционального размеру текста. Сообщения об occ позиций вхождения требуют occ x loge n времени. При достаточно большом m этот процесс может быть ускорен [3]. | |||
Гросси и Виттер также демонстрируют, как модифицировать экономичное по объему памяти суффиксное дерево [ ], чтобы получить время поиска O(m/\oga n + loge n) для любой константы 0 < e < 1, используя O(n log cr) бит памяти. | |||
Садаканэ [10] показал, как вышеприведенный сжатый суффиксный массив может быть преобразован в самоиндексируемый и одновременно может быть оптимизирован несколькими способами. Он обеспечивает прямой доступ не к A[i], а к любому префиксу T[A[i]; n]. Этого по-прежнему достаточно для использования алгоритма бинарного поиска для обнаружения вхождений шаблона. | |||
Садаканэ представляет и A, и T, используя полную функцию 4' и несколько дополнительных структур. Предположим, что требуется сравнить P с T[A[i]; n]. Для бинарного поиска необходимо извлечь из T[A[i]; n] достаточное количество символов, чтобы его лексикографическое отношение к P стало понятным. Получить символ T[A[i]] легко: для этого можно использовать битовый вектор F[1; n], отмечающий суффиксы A[ i], у которых первый символ отличается от такого же символа в A[i — 1]. После предварительной обработки вектора F для запросов rank вычисление j = rank1(F; i) дает T[A[i]] = cj, где cj это j-ый наименьший символ алфавита. Как только T[A[i]] = cj будет определен таким образом, необходимо получить следующий символ, T[A[i] + 1]. Но T[A[i] + 1] = T[A[V{i)}}, поэтому можно просто перейти к i0 = ^(i) и продолжать извлекать символы тем же способом, сколько потребуется. Следует отметить, что в большинстве случаев jPj = m символов достаточно для сравнения с P. Таким образом, моделирование бинарного поиска выполняется за время O(m log n). | |||
До этого момента было использовано n + o(n) + a log a бит памяти для F и S. Садаканэ [10] дает улучшенное представление для 4>, используя nH0 + O(n log log cr) бит, где H0 – энтропия T нулевого порядка. | |||
Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения A"1 [j]. Это обратное значение используется для извлечения произвольных подстрок текста T[p;r], вначале применяя i = A~1[p], а затем, как и прежде, продолжая извлекать r — p + 1 первых символов суффикса T[A[i]; n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый: | |||
Теорема 3 (Садаканэ [ ]). Сжатый суффиксный массив Садаканэ — это самоиндекс, занимающий j-иНо + O(n log log cr) бит и поддерживающий извлечение значений A[i] и A~1[j] за время O(loge n), подсчет вхождений шаблона за время O(mlogn) и отображение любой подстроки T длины I за время O(l + loge n), где 0 < e < 1 — произвольная константа. | |||
