Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.11057 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914276428480512 |
|---|---|
| author | Kimura, Kotaro I, Tomohiro |
| author_facet | Kimura, Kotaro I, Tomohiro |
| contents | Nishimoto and Tabei [CPM, 2021] proposed r-enum, an algorithm to enumerate various characteristic substrings, including maximal repeats, in a string $T$ of length $n$ in $O(r)$ words of compressed working space, where $r \le n$ is the number of runs in the Burrows-Wheeler transform (BWT) of $T$. Given the run-length encoded BWT (RLBWT) of $T$, r-enum runs in $O(n \log \log_{w} (n/r))$ time in addition to the time linear to the number of output strings, where $w = Θ(\log n)$ is the word size. In this paper, we first improve the $O(n \log \log_{w} (n/r))$ term to $O(n)$. We next extend r-enum to compute other context-sensitive repeats such as near-supermaximal repeats (NSMRs) and supermaximal repeats, as well as the context diversity for every maximal repeat in the same complexities. Furthermore, we study net occurrences: An occurrence of a repeat is called a net occurrence if it is not covered by another repeat, and the net frequency of a repeat is the number of its net occurrences. With this terminology, an NSMR is a repeat with a positive net frequency. Given the RLBWT of $T$, we show how to compute the set $S^{nsmr}$ of all NSMRs in $T$ together with their net frequency/occurrences in $O(n)$ time and $O(r)$ space. We also show that an $O(r)$-space data structure can be built from the RLBWT to compute the net frequency/occurrences of any pattern in optimal time. The data structure is built in $O(r)$ space and in $O(n)$ time with high probability or deterministic $O(n + |S^{nsmr}| \log \log \min(σ, |S^{nsmr}|))$ time, where $σ\le r$ is the alphabet size of $T$. To achieve this, we prove that the total number of net occurrences is less than $2r$. With the duality between net occurrences and \emph{minimal unique substrings (MUSs)}, we get a new upper bound $2r$ of the number of MUSs in $T$, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11057 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies Kimura, Kotaro I, Tomohiro Data Structures and Algorithms Nishimoto and Tabei [CPM, 2021] proposed r-enum, an algorithm to enumerate various characteristic substrings, including maximal repeats, in a string $T$ of length $n$ in $O(r)$ words of compressed working space, where $r \le n$ is the number of runs in the Burrows-Wheeler transform (BWT) of $T$. Given the run-length encoded BWT (RLBWT) of $T$, r-enum runs in $O(n \log \log_{w} (n/r))$ time in addition to the time linear to the number of output strings, where $w = Θ(\log n)$ is the word size. In this paper, we first improve the $O(n \log \log_{w} (n/r))$ term to $O(n)$. We next extend r-enum to compute other context-sensitive repeats such as near-supermaximal repeats (NSMRs) and supermaximal repeats, as well as the context diversity for every maximal repeat in the same complexities. Furthermore, we study net occurrences: An occurrence of a repeat is called a net occurrence if it is not covered by another repeat, and the net frequency of a repeat is the number of its net occurrences. With this terminology, an NSMR is a repeat with a positive net frequency. Given the RLBWT of $T$, we show how to compute the set $S^{nsmr}$ of all NSMRs in $T$ together with their net frequency/occurrences in $O(n)$ time and $O(r)$ space. We also show that an $O(r)$-space data structure can be built from the RLBWT to compute the net frequency/occurrences of any pattern in optimal time. The data structure is built in $O(r)$ space and in $O(n)$ time with high probability or deterministic $O(n + |S^{nsmr}| \log \log \min(σ, |S^{nsmr}|))$ time, where $σ\le r$ is the alphabet size of $T$. To achieve this, we prove that the total number of net occurrences is less than $2r$. With the duality between net occurrences and \emph{minimal unique substrings (MUSs)}, we get a new upper bound $2r$ of the number of MUSs in $T$, which may be of independent interest. |
| title | R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.11057 |