Online Computation of String Net Frequency
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913455023325184 |
|---|---|
| author | Guo, Peaker Umboh, Seeun William Wirth, Anthony Zobel, Justin |
| author_facet | Guo, Peaker Umboh, Seeun William Wirth, Anthony Zobel, Justin |
| contents | The net frequency (NF) of a string, of length $m$, in a text, of length $n$, is the number of occurrences of the string in the text with unique left and right extensions. Recently, Guo et al. [CPM 2024] showed that NF is combinatorially interesting and how two key questions can be computed efficiently in the offline setting. First, SINGLE-NF: reporting the NF of a query string in an input text. Second, ALL-NF: reporting an occurrence and the NF of each string of positive NF in an input text. For many applications, however, facilitating these computations in an online manner is highly desirable. We are the first to solve the above two problems in the online setting, and we do so in optimal time, assuming, as is common, a constant-size alphabet: SINGLE-NF in $O(m)$ time and ALL-NF in $O(n)$ time. Our results are achieved by first designing new and simpler offline algorithms using suffix trees, proving additional properties of NF, and exploiting Ukkonen's online suffix tree construction algorithm and results on implicit node maintenance in an implicit suffix tree by Breslauer and Italiano. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00308 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Computation of String Net Frequency Guo, Peaker Umboh, Seeun William Wirth, Anthony Zobel, Justin Data Structures and Algorithms The net frequency (NF) of a string, of length $m$, in a text, of length $n$, is the number of occurrences of the string in the text with unique left and right extensions. Recently, Guo et al. [CPM 2024] showed that NF is combinatorially interesting and how two key questions can be computed efficiently in the offline setting. First, SINGLE-NF: reporting the NF of a query string in an input text. Second, ALL-NF: reporting an occurrence and the NF of each string of positive NF in an input text. For many applications, however, facilitating these computations in an online manner is highly desirable. We are the first to solve the above two problems in the online setting, and we do so in optimal time, assuming, as is common, a constant-size alphabet: SINGLE-NF in $O(m)$ time and ALL-NF in $O(n)$ time. Our results are achieved by first designing new and simpler offline algorithms using suffix trees, proving additional properties of NF, and exploiting Ukkonen's online suffix tree construction algorithm and results on implicit node maintenance in an implicit suffix tree by Breslauer and Italiano. |
| title | Online Computation of String Net Frequency |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.00308 |