Compressed pattern matching

In computer science, compressed pattern matching (abbreviated as CPM) is the process of searching for patterns in compressed data with little or no decompression. Searching in a compressed string is faster than searching an uncompressed string and requires less space.

Compressed matching problem

If the compressed file uses a variable width encoding it could be present a problem: for example, let “100” be the codeword for a and let “110100” be the codeword for b. If we are looking for an occurrence of a in the text we could obtain as result also an occurrence that is within the codeword of b: we call this event false match. So we have to verify if the occurrence detected is effectively aligned on a codeword boundary. However we could always decode the entire text and then apply a classic string matching algorithm, but this usually requires more space and time and often is not possible, for example if the compressed file is hosted online. This problem of verifying the match returned by the compressed pattern matching algorithm is a true or a false match together with the impossibility of decoding an entire text is called the compressed matching problem.[1]

Strategies

Many strategies exist for finding the boundaries of codewords and avoiding full decompression of the text, for example:

  • List of the indices of first bit of each codeword, where we can apply a binary search;
  • List of the indices of first bit of each codeword with differential coding, so we can take less space within the file;
  • Mask of bit, where bit 1 marks the starting bit of each codeword;
  • Subdivision in blocks, for a partial and aimed decompression.

There were introduced algorithms that provide running time that grows logarithmically with the increase of string and pattern length.[2]

References

  1. ^ Joel Grus (2019). Data Science from Scratch. First Principles with Python. O'Reilly Media. ISBN 9781491901427. Archived from the original on 2021-08-17. Retrieved 2021-08-26.
  2. ^ Artur Jeż (2013-06-25). "Faster fully compressed pattern matching by recompression". arXiv:1111.3244 [cs.DS].

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.