تقرير
Internal Dictionary Matching
| العنوان: | Internal Dictionary Matching |
|---|---|
| المؤلفون: | Charalampopoulos, Panagiotis, Kociumaka, Tomasz, Mohamed, Manal, Radoszewski, Jakub, Rytter, Wojciech, Waleń, Tomasz |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $\mathcal{D}$ in fragments of a given string $T$ of length $n$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, $\mathcal{D}$ takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $\Theta(n\cdot d)$. In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $\mathcal{D}$ in a fragment $T[i..j]$ and reporting distinct patterns from $\mathcal{D}$ that occur in $T[i..j]$. We show how to construct, in $\mathcal{O}((n+d) \log^{\mathcal{O}(1)} n)$ time, a data structure that answers each of these queries in time $\mathcal{O}(\log^{\mathcal{O}(1)} n+|output|)$. The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight---up to subpolynomial factors---upper and lower bounds for the case of a dynamic dictionary. Comment: A short version of this paper was accepted for presentation at ISAAC 2019 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1909.11577 |
| رقم الأكسشن: | edsarx.1909.11577 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |