Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929451896406016 |
|---|---|
| author | Inenaga, Shunsuke |
| author_facet | Inenaga, Shunsuke |
| contents | The linear-size suffix tries (LSTries) [Crochemore et al., TCS 2016] are a version of suffix trees in which the edge labels are single characters, yet are able to perform pattern matching queries in optimal time. Instead of explicitly storing the input text, LSTries have some extra non-branching internal nodes called type-2 nodes. The extended techniques are then used in the linear-size compact directed acyclic word graphs (LCDAWGs) [Takagi et al., SPIRE 2017], which can be stored with $O(el(T)+er(T))$ space (i.e. without the text), where $el(T)$ and $er(T)$ are the numbers of left- and right-extensions of the maximal repeats in the input text string $T$, respectively. In this paper, we present simpler alternatives to the aforementioned indexing structures, called the simplified LSTries (simLSTries) and the simplified LCDAWGs (simLCDAWGs), in which most of the type-2 nodes are removed. In particular, our simLCDAWGs require only $O(er(T))$ space and work on a weaker model of computation (i.e. the pointer machine model). This contrasts the $O(er(T))$-space CDAWG representation of [Belazzougui and Cunial, SPIRE 2017], which works on the word RAM model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_04509 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved Inenaga, Shunsuke Data Structures and Algorithms Formal Languages and Automata Theory The linear-size suffix tries (LSTries) [Crochemore et al., TCS 2016] are a version of suffix trees in which the edge labels are single characters, yet are able to perform pattern matching queries in optimal time. Instead of explicitly storing the input text, LSTries have some extra non-branching internal nodes called type-2 nodes. The extended techniques are then used in the linear-size compact directed acyclic word graphs (LCDAWGs) [Takagi et al., SPIRE 2017], which can be stored with $O(el(T)+er(T))$ space (i.e. without the text), where $el(T)$ and $er(T)$ are the numbers of left- and right-extensions of the maximal repeats in the input text string $T$, respectively. In this paper, we present simpler alternatives to the aforementioned indexing structures, called the simplified LSTries (simLSTries) and the simplified LCDAWGs (simLCDAWGs), in which most of the type-2 nodes are removed. In particular, our simLCDAWGs require only $O(er(T))$ space and work on a weaker model of computation (i.e. the pointer machine model). This contrasts the $O(er(T))$-space CDAWG representation of [Belazzougui and Cunial, SPIRE 2017], which works on the word RAM model. |
| title | Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved |
| topic | Data Structures and Algorithms Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2401.04509 |