Internal Pattern Matching in Small Space and Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916224815857664 |
|---|---|
| author | Bathie, Gabriel Charalampopoulos, Panagiotis Starikovskaya, Tatiana |
| author_facet | Bathie, Gabriel Charalampopoulos, Panagiotis Starikovskaya, Tatiana |
| contents | In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our main contribution is a space-time trade-off for the Internal Pattern Matching (IPM) problem, where the goal is to construct a data structure over a string $S$ of length $n$ that allows one to answer the following type of queries: Compute the occurrences of a fragment $P$ of $S$ inside another fragment $T$ of $S$, provided that $|T| < 2|P|$. For any $τ\in [1 .. n/\log^2 n]$, we present a nearly-optimal $Õ(n/τ)$-size data structure that can be built in $Õ(n)$ time using $Õ(n/τ)$ extra space, and answers IPM queries in $O(τ+\log n \log^3 \log n)$ time. IPM queries have been identified as a crucial primitive operation for the analysis of algorithms on strings. In particular, the complexities of several recent algorithms for approximate pattern matching are expressed with regards to the number of calls to a small set of primitive operations that include IPM queries; our data structure allows us to port these results to the small-space setting. We further showcase the applicability of our IPM data structure by using it to obtain space-time trade-offs for the longest common substring and circular pattern matching problems in the asymmetric streaming setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17502 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Internal Pattern Matching in Small Space and Applications Bathie, Gabriel Charalampopoulos, Panagiotis Starikovskaya, Tatiana Data Structures and Algorithms In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our main contribution is a space-time trade-off for the Internal Pattern Matching (IPM) problem, where the goal is to construct a data structure over a string $S$ of length $n$ that allows one to answer the following type of queries: Compute the occurrences of a fragment $P$ of $S$ inside another fragment $T$ of $S$, provided that $|T| < 2|P|$. For any $τ\in [1 .. n/\log^2 n]$, we present a nearly-optimal $Õ(n/τ)$-size data structure that can be built in $Õ(n)$ time using $Õ(n/τ)$ extra space, and answers IPM queries in $O(τ+\log n \log^3 \log n)$ time. IPM queries have been identified as a crucial primitive operation for the analysis of algorithms on strings. In particular, the complexities of several recent algorithms for approximate pattern matching are expressed with regards to the number of calls to a small set of primitive operations that include IPM queries; our data structure allows us to port these results to the small-space setting. We further showcase the applicability of our IPM data structure by using it to obtain space-time trade-offs for the longest common substring and circular pattern matching problems in the asymmetric streaming setting. |
| title | Internal Pattern Matching in Small Space and Applications |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17502 |