4551
правка
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых | Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых <math>\Psi</math>–функцией, в сочетании с возможностями индексации их новой элегантной структуры данных – ''дерева вейвлетов''. Им удалось, помимо прочих результатов, получить следующий компромисс: | ||
Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупта и Виттера представляет собой самоиндекс, занимающий | '''Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупта и Виттера представляет собой самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_k + o(n \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{1 + \epsilon} n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; \sigma + log^{2 + \epsilon} n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell / log_{\sigma} n + log^{1+\epsilon} n)</math>. Здесь <math>0 < \epsilon \le 1</math> — произвольная константа, <math>k \le \alpha log_{\sigma} n</math> для некоторой константы <math>0 < \alpha < 1</math>.''' | ||
В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии они отметили, что простая кодировка <math>\Psi</math>-значений дает одну и ту же границу nHk, не требуя предварительного фиксирования k [1]. | |||
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает O(n log cr) бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n). | Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает O(n log cr) бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n). | ||
