Export Citations
2 Results for: Keyword: locally consistent parsing
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
Searched The ACM Guide to Computing Literature (3,842,498 records)|Limit your search to The ACM Full-Text Collection (774,561 records)
Select All
- research-articleJune 2023
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of ComputingPages 219–232https://doi.org/10.1145/3564246.3585239In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at ...
- research-articleDecember 2020
Optimal-Time Dictionary-Compressed Indexes
ACM Transactions on Algorithms (TALG), Volume 17, Issue 1Article No.: 8, Pages 1–39https://doi.org/10.1145/3426473We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To achieve this result, we combine several recent findings, including string ...