4446
правок
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 76: | Строка 76: | ||
'''Теорема 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 < 1</math> — произвольная константа.''' | '''Теорема 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 < 1</math> — произвольная константа.''' | ||
Гросси, Гупта и Виттер [1, 2] оптимизировали требования сжатых суффиксных массивов к занимаемой памяти таким образом, чтобы они зависели от энтропии Т k-го порядка. Идея этого улучшения заключается в более тщательном анализе закономерностей, фиксируемых '/' –функцией, в сочетании с возможностями индексации их новой элегантной структуры данных – дерева вейвлетов. Им удалось, помимо прочих результатов, получить следующий компромисс: | |||
Теорема 4 (Гросси, Гупта и Виттер, 2003[2]). Сжатый суффиксный массив Гросси, Гупта и Виттера представляет собой самоиндекс, занимающий ^ nHk + o(n\oga) бит и поддерживающий извлечение значений A[i] и A~l[j] за время O(log1+e n), подсчет вхождений шаблона за время O(m log cr + log и) и отображение любой подстроки T длины I за время O(l/log0 n + log1+e n). Здесь 0 < e < 1 — произвольная константа, k < a log^ n для некоторой константы 0 < a < 1 | |||
В вышеприведенном случае значение k должно быть зафиксировано до построения индекса. Впоследствии они отметили, что простая кодировка '/'-значений дает одну и ту же границу nHk, не требуя предварительного фиксирования k [1]. | |||
Наконец, сжатые суффиксные массивы служат строительными блоками при решении других задач CFTI. Например, Садаканэ [11] создал полнофункциональное сжатое суффиксное дерево, объединив сжатый суффиксный массив и экономичное по объему памяти суффиксное дерево Мунро, Рамана и Рао [8]. Это сжатое суффиксное дерево занимает O(n log cr) бит памяти, моделируя все операции суффиксного дерева с замедлением не более O(log n). | |||
== Применение == | |||
Сжатые суффиксные массивы можно применять в тех же областях, что и классические суффиксные массивы и деревья, с дополнительным преимуществом масштабирования до наборов данных значительно большей величины. | |||
== Ссылка на код == | |||
В соответствующем разделе статьи «[[Индексация сжатого текста]]» см. ссылки на реализации сжатых суффиксных массивов, см. также в http://www.cs.helsinki.fi/group/suds/cst реализацию сжатых суффиксных деревьев Садаканэ. | |||
== См. также == | |||
* [[Индексация сжатого текста]] | |||
* [[Последовательное точное сравнение строк]] | |||
* [[Индексация текста]] | |||
== Литература == | |||
1. Foschini, L., Grossi, R., Gupta, A., Vitter, J.S.: When indexing equals compression: Experiments with compressing suffix arrays and applications. ACM Trans. Algorithms 2(4), 611-639 (2006) | |||
2. Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, 12-14 January, pp. 841-850 (2003) | |||
3. Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378^07 (2006) | |||
4. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, 30 October - 1 November, pp. 549-554(1989) | |||
5. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935-948 (1993) | |||
6. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407-430 (2001) | |||
7. Munro, I.: Tables. In: Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LNCS, vol. 1180, Hyderabad, 18-20 December, pp. 37^2(1996) | |||
8. Munro, I., Raman, V., Rao, S.: Space efficient suffix trees. J. Algorithms 39(2), 205-222 (2001) | |||
9. Navarro, G., Makinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39(1), Article 2 (2007) | |||
10. Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Algorithms 48(2), 294-313 (2003) | |||
11. Sadakane, K.: Compressed suffix trees with full functionality. Theor. Comput. Syst. 41,589-607 (2007) | |||
