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

Это свойство кусочно-линейного увеличения <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>.'''

Гросси и Виттер также демонстрируют, как модифицировать экономичное по объему памяти суффиксное дерево [8], чтобы получить время поиска <math>O(m / log_{\sigma} \; n + log^{\epsilon} \; n)</math> для любой константы <math>0 < \epsilon < 1</math>, используя <math>O(n \; log \sigma)</math> бит памяти.