Faster and Simpler Online Computation of String Net Frequency
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912795705999360 |
|---|---|
| author | Inenaga, Shunsuke |
| author_facet | Inenaga, Shunsuke |
| contents | An occurrence of a repeated substring $u$ in a string $S$ is called a net occurrence if extending the occurrence to the left or to the right decreases the number of occurrences to 1. The net frequency (NF) of a repeated substring $u$ in a string $S$ is the number of net occurrences of $u$ in $S$. Very recently, Guo et al. [SPIRE 2024] proposed an online $O(n \log σ)$-time algorithm that maintains a data structure of $O(n)$ space which answers Single-NF queries in $O(m\log σ+ σ^2)$ time and reports all answers of the All-NF problem in $O(nσ^2)$ time. Here, $n$ is the length of the input string $S$, $m$ is the query pattern length, and $σ$ is the alphabet size. The $σ^2$ term is a major drawback of their method since computing string net frequencies is originally motivated for Chinese language processing where $σ$ can be thousands large. This paper presents an improved online $O(n \log σ)$-time algorithm, which answers Single-NF queries in $O(m \log σ)$ time and reports all answers to the All-NF problem in output-optimal $O(|\mathsf{NF}^+(S)|)$ time, where $\mathsf{NF}^+(S)$ is the set of substrings of $S$ paired with their positive NF values. We note that $|\mathsf{NF}^+(S)| = O(n)$ always holds. In contract to Guo et al.'s algorithm that is based on Ukkonen's suffix tree construction, our algorithm is based on Weiner's suffix tree construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06837 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster and Simpler Online Computation of String Net Frequency Inenaga, Shunsuke Data Structures and Algorithms An occurrence of a repeated substring $u$ in a string $S$ is called a net occurrence if extending the occurrence to the left or to the right decreases the number of occurrences to 1. The net frequency (NF) of a repeated substring $u$ in a string $S$ is the number of net occurrences of $u$ in $S$. Very recently, Guo et al. [SPIRE 2024] proposed an online $O(n \log σ)$-time algorithm that maintains a data structure of $O(n)$ space which answers Single-NF queries in $O(m\log σ+ σ^2)$ time and reports all answers of the All-NF problem in $O(nσ^2)$ time. Here, $n$ is the length of the input string $S$, $m$ is the query pattern length, and $σ$ is the alphabet size. The $σ^2$ term is a major drawback of their method since computing string net frequencies is originally motivated for Chinese language processing where $σ$ can be thousands large. This paper presents an improved online $O(n \log σ)$-time algorithm, which answers Single-NF queries in $O(m \log σ)$ time and reports all answers to the All-NF problem in output-optimal $O(|\mathsf{NF}^+(S)|)$ time, where $\mathsf{NF}^+(S)$ is the set of substrings of $S$ paired with their positive NF values. We note that $|\mathsf{NF}^+(S)| = O(n)$ always holds. In contract to Guo et al.'s algorithm that is based on Ukkonen's suffix tree construction, our algorithm is based on Weiner's suffix tree construction. |
| title | Faster and Simpler Online Computation of String Net Frequency |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.06837 |