What is it about?
We show how to store a large text efficiently, such that we can quickly find occurrences of any given word (pattern) in the text. The novelty in our work is that we allow these patterns to be given in compressed form, and we can report all occurrences without having to decompress the patterns first.
Featured Image
Photo by Patrick Tomasso on Unsplash
Why is it important?
In the common client-server scenario, a client submits a query and sends it to a server which processes the query. To minimize communication time and bandwidth, the query is sent in compressed form. Our work captures classic pattern matching queries in this scenario, where a large text is stored on a server, and several users may submit pattern queries over channels with limited bandwidth. Our data structure allows processing these queries more efficiently if their compressed size is small, i.e. if they are very repetitive.
Read the Original
This page is a summary of: String Indexing with Compressed Patterns, ACM Transactions on Algorithms, July 2023, ACM (Association for Computing Machinery),
DOI: 10.1145/3607141.
You can read the full text:
Contributors
The following have contributed to this page
