Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.11873 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908363769511936 |
|---|---|
| author | Chen, Jingbang Dai, Jiangqi Mang, Qiuyang Shi, Qingyu Xu, Tingqiang |
| author_facet | Chen, Jingbang Dai, Jiangqi Mang, Qiuyang Shi, Qingyu Xu, Tingqiang |
| contents | We study the internal dictionary matching (IDM) problem where a dictionary $\mathcal{D}$ containing $d$ substrings of a text $T$ is given, and each query concerns the occurrences of patterns in $\mathcal{D}$ in another substring of $T$. We propose a novel $O(n)$-sized data structure named Basic Substring Structure (BASS) where $n$ is the length of the text $T.$ With BASS, we are able to handle all types of queries in the IDM problem in nearly optimal query and preprocessing time. Specifically, our results include:
$\bullet$ The first algorithm that answers the CountDistinct query in $\tilde{O}(1)$ time with $\tilde{O}(n+d)$ preprocessing, where we need to compute the number of distinct patterns that exist in $T[l,r]$. Previously, the best result was $\tilde{O}(m)$ time per query after $\tilde{O}(n^2/m+d)$ or $\tilde{O}(nd/m+d)$ preprocessing, where $m$ is a chosen parameter.
$\bullet$ Faster algorithms for two other types of internal queries. We improve the runtime for (1) Occurrence counting (Count) queries to $O(\log n/\log\log n)$ time per query with $O(n+d\sqrt{\log n})$ preprocessing from $O(\log^2 n/\log\log n)$ time per query with $O(n\log n/\log \log n+d\log^{3/2} n)$ preprocessing. (2) Distinct pattern reporting (ReportDistinct) queries to $O(1+|\text{output}|)$ time per query from $O(\log n+|\text{output}|)$ per query.
In addition, we match the optimal runtime in the remaining two types of queries, pattern existence (Exists), and occurrence reporting (Report). We also show that BASS is more generally applicable to other internal query problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_11873 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Internal Dictionary Matching Chen, Jingbang Dai, Jiangqi Mang, Qiuyang Shi, Qingyu Xu, Tingqiang Data Structures and Algorithms We study the internal dictionary matching (IDM) problem where a dictionary $\mathcal{D}$ containing $d$ substrings of a text $T$ is given, and each query concerns the occurrences of patterns in $\mathcal{D}$ in another substring of $T$. We propose a novel $O(n)$-sized data structure named Basic Substring Structure (BASS) where $n$ is the length of the text $T.$ With BASS, we are able to handle all types of queries in the IDM problem in nearly optimal query and preprocessing time. Specifically, our results include: $\bullet$ The first algorithm that answers the CountDistinct query in $\tilde{O}(1)$ time with $\tilde{O}(n+d)$ preprocessing, where we need to compute the number of distinct patterns that exist in $T[l,r]$. Previously, the best result was $\tilde{O}(m)$ time per query after $\tilde{O}(n^2/m+d)$ or $\tilde{O}(nd/m+d)$ preprocessing, where $m$ is a chosen parameter. $\bullet$ Faster algorithms for two other types of internal queries. We improve the runtime for (1) Occurrence counting (Count) queries to $O(\log n/\log\log n)$ time per query with $O(n+d\sqrt{\log n})$ preprocessing from $O(\log^2 n/\log\log n)$ time per query with $O(n\log n/\log \log n+d\log^{3/2} n)$ preprocessing. (2) Distinct pattern reporting (ReportDistinct) queries to $O(1+|\text{output}|)$ time per query from $O(\log n+|\text{output}|)$ per query. In addition, we match the optimal runtime in the remaining two types of queries, pattern existence (Exists), and occurrence reporting (Report). We also show that BASS is more generally applicable to other internal query problems. |
| title | Nearly Optimal Internal Dictionary Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.11873 |