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

Первое решение проблемы предложили Гросси и Виттер [3], использовавшие свойство регулярности суффиксного массива посредством <math>\Psi</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.

Садаканэ представляет и 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 нулевого порядка.