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

Садаканэ представляет и A, и T, используя полную функцию <math>\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 вычисление 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] дает улучшенное представление для <math>\Psi</math>, используя nH0 + O(n log log cr) бит, где H0 – энтропия T нулевого порядка.