Sparse Suffix Tree Construction in Small Space
| Autor: | Johannes Fischer, Tsvi Kopelowitz, Inge Li Gørtz, Hjalte Wedel Vildhøj, Philip Bille, Benjamin Sach |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Compressed suffix array
Suffix tree String (computer science) Generalized suffix tree Suffix array LCP array Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Hash table law.invention Combinatorics Tree (descriptive set theory) law Data_FILES Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Automata, Languages, and Programming ISBN: 9783642392054 ICALP (1) |
| DOI: | 10.1007/978-3-642-39206-1_13 |
| Popis: | We consider the problem of constructing a sparse suffix tree (or suffix array) for b suffixes of a given text T of length n, using only O(b) words of space during construction. Attempts at breaking the naive bound of Ω(nb) time for this problem can be traced back to the origins of string indexing in 1968. First results were only obtained in 1996, but only for the case where the suffixes were evenly spaced in T. In this paper there is no constraint on the locations of the suffixes. We show that the sparse suffix tree can be constructed in O(nlog2b) time. To achieve this we develop a technique, which may be of independent interest, that allows to efficiently answer b longest common prefix queries on suffixes of T, using only O(b) space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Our first solution is Monte-Carlo and outputs the correct tree with high probability. We then give a Las-Vegas algorithm which also uses O(b) space and runs in the same time bounds with high probability when $b = O(\sqrt{n})$. Furthermore, additional tradeoffs between the space usage and the construction time for the Monte-Carlo algorithm are given. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|