Indexing Tries within Entropy-Bounded Space
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915370612293632 |
|---|---|
| author | Carfagna, Lorenzo Tosoni, Carlo |
| author_facet | Carfagna, Lorenzo Tosoni, Carlo |
| contents | We study the problem of indexing and compressing tries using a BWT-based approach. Specifically, we consider a succinct and compressed representation of the XBWT of Ferragina et al.\ [FOCS '05, JACM '09] corresponding to the analogous of the FM-index [FOCS '00, JACM '05] for tries. This representation allows to efficiently count the number of nodes reached by a given string pattern. To analyze the space complexity of the above trie index, we propose a proof for the combinatorial problem of counting the number of tries with a given symbol distribution. We use this formula to define a worst-case entropy measure for tries, as well as a notion of k-th order empirical entropy. In particular, we show that the relationships between these two entropy measures are similar to those between the corresponding well-known measures for strings. We use these measures to prove that the XBWT of a trie can be encoded within a space bounded by our k-th order empirical entropy plus a o(n) term, with n being the number of nodes in the trie. Notably, as happens for strings, this space bound can be reached for every sufficiently small k simultaneously. Finally, we compare the space complexity of the above index with that of the r-index for tries proposed by Prezza [SODA '21] and we prove that in some cases the FM-index for tries is asymptotically smaller. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02728 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Indexing Tries within Entropy-Bounded Space Carfagna, Lorenzo Tosoni, Carlo Data Structures and Algorithms We study the problem of indexing and compressing tries using a BWT-based approach. Specifically, we consider a succinct and compressed representation of the XBWT of Ferragina et al.\ [FOCS '05, JACM '09] corresponding to the analogous of the FM-index [FOCS '00, JACM '05] for tries. This representation allows to efficiently count the number of nodes reached by a given string pattern. To analyze the space complexity of the above trie index, we propose a proof for the combinatorial problem of counting the number of tries with a given symbol distribution. We use this formula to define a worst-case entropy measure for tries, as well as a notion of k-th order empirical entropy. In particular, we show that the relationships between these two entropy measures are similar to those between the corresponding well-known measures for strings. We use these measures to prove that the XBWT of a trie can be encoded within a space bounded by our k-th order empirical entropy plus a o(n) term, with n being the number of nodes in the trie. Notably, as happens for strings, this space bound can be reached for every sufficiently small k simultaneously. Finally, we compare the space complexity of the above index with that of the r-index for tries proposed by Prezza [SODA '21] and we prove that in some cases the FM-index for tries is asymptotically smaller. |
| title | Indexing Tries within Entropy-Bounded Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.02728 |