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

'''Теорема 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>.'''

Как следствие, моделирование классического бинарного поиска [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]. Этого по-прежнему достаточно для использования алгоритма бинарного поиска для обнаружения вхождений шаблона.