4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 74: | Строка 74: | ||
Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r | Садаканэ также показывает, как можно извлечь A[i] с помощью использования иерархической схемы Гросси и Виттера. Он добавляет к схеме извлечение обратного значения <math>A^{-1} [j]</math>. Это обратное значение используется для извлечения произвольных подстрок текста T[p, r], вначале применяя <math>i = A^{-1}[p]</math>, а затем, как и прежде, продолжая извлекать r - p + 1 первых символов суффикса T[A[i], n]. Эта возможность превращает сжатый суффиксный массив в самоиндексируемый: | ||
'''Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ | '''Теорема 3 (Садаканэ [10]). Сжатый суффиксный массив Садаканэ представляет собой самоиндекс, занимающий <math>\frac{1}{\epsilon}nH_0 + O(n \; log \; log \; \sigma)</math> бит и поддерживающий извлечение значений <math>A[i]</math> и <math>A^{-1}[j]</math> за время <math>O(log^{\epsilon} \; n)</math>, подсчет вхождений шаблона за время <math>O(m \; log \; n)</math> и отображение любой подстроки T длины <math>\ell</math> за время <math>O(\ell + log^{\epsilon} \; n)</math>, где <math>0 < \epsilon \le 1</math> — произвольная константа.''' | ||
Строка 83: | Строка 83: | ||
'''Теорема 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 должно быть зафиксировано до построения индекса. Впоследствии | В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии авторы отметили, что простая кодировка <math>\Psi</math>-значений дает ту же границу <math>nH_k</math>, не требуя предварительного фиксирования k [1]. | ||
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает < | Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает <math>O(n \; log \; \sigma)</math> бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n). | ||
== Применение == | == Применение == |
правок