Constant-time edge label and leaf pointer maintenance on sliding suffix trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910348003508224 |
|---|---|
| author | Leonard, Laurentius Inenaga, Shunsuke Bannai, Hideo Mieno, Takuya |
| author_facet | Leonard, Laurentius Inenaga, Shunsuke Bannai, Hideo Mieno, Takuya |
| contents | Sliding suffix trees (Fiala & Greene, 1989) for an input text $T$ over an alphabet of size $σ$ and a sliding window $W$ of $T$ can be maintained in $O(|T| \log σ)$ time and $O(|W|)$ space. The two previous approaches that achieve this can be categorized into the credit-based approach of Fiala and Greene (1989) and Larsson (1996, 1999), or the batch-based approach proposed by Senft (2005). Brodnik and Jekovec (2018) showed that the sliding suffix tree can be supplemented with leaf pointers in order to find all occurrences of an online query pattern in the current window, and that leaf pointers can be maintained by credit-based arguments as well. The main difficulty in the credit-based approach is in the maintenance of index-pairs that represent each edge. In this paper, we show that valid edge index-pairs can be derived in constant time from leaf pointers, thus reducing the maintenance of edge index-pairs to the maintenance of leaf pointers. We further propose a new simple method that maintains leaf pointers without using credit-based arguments. The lack of credit-based arguments allow a simpler proof of correctness compared to the credit-based approach, whose analyses were initially flawed (Senft 2005). In addition, our method reduces the worst-case time of leaf pointer and edge label maintenance per leaf insertion and deletion from $Θ(|W|)$ time to $O(1)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_01412 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Constant-time edge label and leaf pointer maintenance on sliding suffix trees Leonard, Laurentius Inenaga, Shunsuke Bannai, Hideo Mieno, Takuya Data Structures and Algorithms Sliding suffix trees (Fiala & Greene, 1989) for an input text $T$ over an alphabet of size $σ$ and a sliding window $W$ of $T$ can be maintained in $O(|T| \log σ)$ time and $O(|W|)$ space. The two previous approaches that achieve this can be categorized into the credit-based approach of Fiala and Greene (1989) and Larsson (1996, 1999), or the batch-based approach proposed by Senft (2005). Brodnik and Jekovec (2018) showed that the sliding suffix tree can be supplemented with leaf pointers in order to find all occurrences of an online query pattern in the current window, and that leaf pointers can be maintained by credit-based arguments as well. The main difficulty in the credit-based approach is in the maintenance of index-pairs that represent each edge. In this paper, we show that valid edge index-pairs can be derived in constant time from leaf pointers, thus reducing the maintenance of edge index-pairs to the maintenance of leaf pointers. We further propose a new simple method that maintains leaf pointers without using credit-based arguments. The lack of credit-based arguments allow a simpler proof of correctness compared to the credit-based approach, whose analyses were initially flawed (Senft 2005). In addition, our method reduces the worst-case time of leaf pointer and edge label maintenance per leaf insertion and deletion from $Θ(|W|)$ time to $O(1)$ time. |
| title | Constant-time edge label and leaf pointer maintenance on sliding suffix trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2307.01412 |