http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Compressed_pattern_matchingCompressed pattern matching - Revision history2026-10-25T22:21:57ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Compressed_pattern_matching&diff=8084623&oldid=previmported>InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.52023-12-19T23:18:40Z<p>Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5</p>
<p><b>New page</b></p><div>{{Short description|Searching for patterns in compressed data}}<br />
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.<br />
<br />
==Compressed matching problem==<br />
If the [[Data compression|compressed]] file uses a [[variable width encoding]] it could be present a problem: for example, let “100” be the [[Code word (communication)|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 searching algorithm|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'''.<ref>{{cite book|title=Data Science from Scratch. First Principles with Python|url=https://python.engineering/data-science-from-scratch-first-principles-with-python/|isbn=9781491901427|author=Joel Grus|date=2019|publisher=O'Reilly Media|access-date=2021-08-26|archive-date=2021-08-17|archive-url=https://web.archive.org/web/20210817121416/https://python.engineering/data-science-from-scratch-first-principles-with-python/|url-status=dead}}</ref><br />
<br />
==Strategies==<br />
Many strategies exist for finding the boundaries of codewords and avoiding full decompression of the text, for example:<br />
*List of the indices of first bit of each codeword, where we can apply a binary search;<br />
*List of the indices of first bit of each codeword with differential coding, so we can take less space within the file;<br />
*[[Mask (computing)|Mask of bit]], where bit 1 marks the starting bit of each codeword;<br />
*Subdivision in blocks, for a partial and aimed decompression.<br />
<br />
There were introduced algorithms that provide running time that grows logarithmically with the increase of string and pattern length.<ref>{{cite arXiv|title=Faster fully compressed pattern matching by recompression|date=2013-06-25|author=Artur Jeż|class=cs.DS |eprint=1111.3244}}</ref><br />
<br />
== References ==<br />
{{reflist}}<br />
*Shmuel T. Klein and Dana Shapira [https://scholar.archive.org/work/42bnluwv6jfb7p4wra3diihz7m/access/wayback/http://www.dmi.unict.it/~faro/algocom/prova02/paper24.pdf PATTERN MATCHING IN HUFFMAN ENCODED TEXTS] (2003)<br />
* [http://www.cs.helsinki.fi/njc/References/karpinskirs1997:172.html Marek Karpinski, Wojciech Rytter and Ayumi Shinohara. AN EFFICIENT PATTERN-MATCHING ALGORITHM FOR STRINGS WITH SHORT DESCRIPTIONS. Nordic Journal of Computing 4(2): pp.172-168 (1997).]<br />
<br />
== External links ==<br />
* {{cite journal | citeseerx = 10.1.1.44.5521 | title = Almost optimal fully LZW-compressed pattern matching | year = 1999 | pages = 316–325 }}<br />
* {{citation|url=http://cc.ee.ntu.edu.tw/~yen/papers/compsac2002.pdf |title=A Dictionary-based Compressed Pattern Matching Algorithm |url-status=dead |archive-url=https://web.archive.org/web/20030313175423/http://cc.ee.ntu.edu.tw/~yen/papers/compsac2002.pdf |archive-date=March 13, 2003 }}<br />
* {{cite journal | citeseerx = 10.1.1.50.1745 | title = A unifying framework for compressed pattern matching | year = 1999 | pages = 89–96 }}<br />
* {{cite journal | url = http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJ40.pdf | title = Speeding Up String Pattern Matching by Text Compression: The Dawn of a New Era | access-date = 2009-03-22 | archive-url = https://web.archive.org/web/20070808170750/http://www.i.kyushu-u.ac.jp/~takeda/papers/IPSJ40.pdf | archive-date = 2007-08-08 | url-status = dead }}<br />
* {{cite journal | citeseerx = 10.1.1.15.4609 | title = Shift-and approach to pattern matching in LZW compressed text | year = 1999 | pages = 1–13 }}<br />
* {{cite journal | url = http://vlsi.cs.ucf.edu/nsf/files/lzw_cpm.pdf | title = LZW Algorithm }}<br />
<br />
{{Strings |state=collapsed}}<br />
<br />
{{DEFAULTSORT:Compressed Pattern Matching}}<br />
[[Category:Data compression]]<br />
[[Category:Pattern matching]]<br />
[[Category:Computer data]]</div>imported>InternetArchiveBot