A Suffix Tree Or Not A Suffix Tree?
| Autor: | Hjalte Wedel Vildhøj, Tatiana Starikovskaya |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Compressed suffix array Suffix tree Generalized suffix tree String searching algorithm Data_CODINGANDINFORMATIONTHEORY Theoretical Computer Science Longest common substring problem law.invention Combinatorics law Computer Science - Data Structures and Algorithms Suffix tour graphs Data_FILES Discrete Mathematics and Combinatorics Data Structures and Algorithms (cs.DS) Reverse engineering Computer Science::Data Structures and Algorithms Suffix trees Mathematics Suffix array Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Suffix links Computational Theory and Mathematics Suffix FM-index Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Starikovskaya, T A & Vildhøj, H W 2015, ' A suffix tree or not a suffix tree? ', Journal of Discrete Algorithms, vol. 32, pp. 14-23 . https://doi.org/10.1016/j.jda.2015.01.005 |
| DOI: | 10.1016/j.jda.2015.01.005 |
| Popis: | In this paper we study the structure of suffix trees. Given an unlabeled tree $\tau$ on $n$ nodes and suffix links of its internal nodes, we ask the question "Is $\tau$ a suffix tree?", i.e., is there a string $S$ whose suffix tree has the same topological structure as $\tau$? We place no restrictions on $S$, in particular we do not require that $S$ ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. We prove that $\tau$ is a suffix tree if and only if it is realized by a string $S$ of length $n-1$, and we give a linear-time algorithm for inferring $S$ when the first letter on each edge is known. This generalizes the work of I et al. [Discrete Appl. Math. 163, 2014]. Comment: Full version. An extended abstract has been accepted to IWOCA 2014 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|