Loading…
Faster Fully Compressed Pattern Matching by Recompression
In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term fully means that both the pattern and the text are given in the compressed form. The problem...
Saved in:
| Published in: | ACM transactions on algorithms 2015-01, Vol.11 (3), p.1-43 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3 |
| container_end_page | 43 |
| container_issue | 3 |
| container_start_page | 1 |
| container_title | ACM transactions on algorithms |
| container_volume | 11 |
| creator | Jez, Artur |
| description | In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term
fully
means that both the pattern
and
the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.
This technique yields an
O
((
n
+
m
) log
M
) algorithm for compressed pattern matching, assuming that
M
fits in
O
(1) machine words, where
n
(
m
) is the size of the compressed representation of the text (pattern, respectively), and
M
is the size of the decompressed pattern. If only
m
+
n
fits in
O
(1) machine words, the running time increases to
O
((
n
+
m
) log
M
log (
n
+
m
)). The previous best algorithm due to Lifshits has
O
(
n
2
m
) running time. |
| doi_str_mv | 10.1145/2631920 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1669843838</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1669843838</sourcerecordid><originalsourceid>FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3</originalsourceid><addsrcrecordid>eNo9kE1LxDAYhIMouK7iX-hNL9V8NU2OUlwVVhTRc3ibvNVKv0zaQ_-9lS2eZhiemcMQcsnoDWMyu-VKMMPpEdmwTJpUCSGO_z3PTslZjN-UCiOE3hCzgzhiSHZT08xJ0bdDwBjRJ68wLnmXPMPovuruMynn5A3dCtR9d05OKmgiXqy6JR-7-_fiMd2_PDwVd_vUSZ6PaSm1AgAqJWKJJs-1Mw7R5Vqiq6jJpaESgKN0QgvvvaQMqswzb5jiBsSWXB92h9D_TBhH29bRYdNAh_0ULVPKaLl09YJeHVAX-hgDVnYIdQthtozav3Pseo74BYHbVhE</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1669843838</pqid></control><display><type>article</type><title>Faster Fully Compressed Pattern Matching by Recompression</title><source>Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)</source><creator>Jez, Artur</creator><creatorcontrib>Jez, Artur</creatorcontrib><description>In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term
fully
means that both the pattern
and
the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.
This technique yields an
O
((
n
+
m
) log
M
) algorithm for compressed pattern matching, assuming that
M
fits in
O
(1) machine words, where
n
(
m
) is the size of the compressed representation of the text (pattern, respectively), and
M
is the size of the decompressed pattern. If only
m
+
n
fits in
O
(1) machine words, the running time increases to
O
((
n
+
m
) log
M
log (
n
+
m
)). The previous best algorithm due to Lifshits has
O
(
n
2
m
) running time.</description><identifier>ISSN: 1549-6325</identifier><identifier>EISSN: 1549-6333</identifier><identifier>DOI: 10.1145/2631920</identifier><language>eng</language><subject>Algorithms ; Compressed ; Compressing ; Matching ; Recompression ; Representations ; Running ; Strings ; Texts</subject><ispartof>ACM transactions on algorithms, 2015-01, Vol.11 (3), p.1-43</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3</citedby><cites>FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Jez, Artur</creatorcontrib><title>Faster Fully Compressed Pattern Matching by Recompression</title><title>ACM transactions on algorithms</title><description>In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term
fully
means that both the pattern
and
the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.
This technique yields an
O
((
n
+
m
) log
M
) algorithm for compressed pattern matching, assuming that
M
fits in
O
(1) machine words, where
n
(
m
) is the size of the compressed representation of the text (pattern, respectively), and
M
is the size of the decompressed pattern. If only
m
+
n
fits in
O
(1) machine words, the running time increases to
O
((
n
+
m
) log
M
log (
n
+
m
)). The previous best algorithm due to Lifshits has
O
(
n
2
m
) running time.</description><subject>Algorithms</subject><subject>Compressed</subject><subject>Compressing</subject><subject>Matching</subject><subject>Recompression</subject><subject>Representations</subject><subject>Running</subject><subject>Strings</subject><subject>Texts</subject><issn>1549-6325</issn><issn>1549-6333</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNo9kE1LxDAYhIMouK7iX-hNL9V8NU2OUlwVVhTRc3ibvNVKv0zaQ_-9lS2eZhiemcMQcsnoDWMyu-VKMMPpEdmwTJpUCSGO_z3PTslZjN-UCiOE3hCzgzhiSHZT08xJ0bdDwBjRJ68wLnmXPMPovuruMynn5A3dCtR9d05OKmgiXqy6JR-7-_fiMd2_PDwVd_vUSZ6PaSm1AgAqJWKJJs-1Mw7R5Vqiq6jJpaESgKN0QgvvvaQMqswzb5jiBsSWXB92h9D_TBhH29bRYdNAh_0ULVPKaLl09YJeHVAX-hgDVnYIdQthtozav3Pseo74BYHbVhE</recordid><startdate>20150101</startdate><enddate>20150101</enddate><creator>Jez, Artur</creator><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20150101</creationdate><title>Faster Fully Compressed Pattern Matching by Recompression</title><author>Jez, Artur</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Algorithms</topic><topic>Compressed</topic><topic>Compressing</topic><topic>Matching</topic><topic>Recompression</topic><topic>Representations</topic><topic>Running</topic><topic>Strings</topic><topic>Texts</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Jez, Artur</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>ACM transactions on algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Jez, Artur</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Faster Fully Compressed Pattern Matching by Recompression</atitle><jtitle>ACM transactions on algorithms</jtitle><date>2015-01-01</date><risdate>2015</risdate><volume>11</volume><issue>3</issue><spage>1</spage><epage>43</epage><pages>1-43</pages><issn>1549-6325</issn><eissn>1549-6333</eissn><abstract>In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term
fully
means that both the pattern
and
the text are given in the compressed form. The problem is approached using a recently developed technique of local recompression: the SLPs are refactored so that substrings of the pattern and text are encoded in both SLPs in the same way. To this end, the SLPs are locally decompressed and then recompressed in a uniform way.
This technique yields an
O
((
n
+
m
) log
M
) algorithm for compressed pattern matching, assuming that
M
fits in
O
(1) machine words, where
n
(
m
) is the size of the compressed representation of the text (pattern, respectively), and
M
is the size of the decompressed pattern. If only
m
+
n
fits in
O
(1) machine words, the running time increases to
O
((
n
+
m
) log
M
log (
n
+
m
)). The previous best algorithm due to Lifshits has
O
(
n
2
m
) running time.</abstract><doi>10.1145/2631920</doi><tpages>43</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1549-6325 |
| ispartof | ACM transactions on algorithms, 2015-01, Vol.11 (3), p.1-43 |
| issn | 1549-6325 1549-6333 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_1669843838 |
| source | Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list) |
| subjects | Algorithms Compressed Compressing Matching Recompression Representations Running Strings Texts |
| title | Faster Fully Compressed Pattern Matching by Recompression |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T18%3A50%3A44IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Faster%20Fully%20Compressed%20Pattern%20Matching%20by%20Recompression&rft.jtitle=ACM%20transactions%20on%20algorithms&rft.au=Jez,%20Artur&rft.date=2015-01-01&rft.volume=11&rft.issue=3&rft.spage=1&rft.epage=43&rft.pages=1-43&rft.issn=1549-6325&rft.eissn=1549-6333&rft_id=info:doi/10.1145/2631920&rft_dat=%3Cproquest_cross%3E1669843838%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c427t-b486aaa044eebe9778c9ceec784ecf0974904aa2e4c383ddd401af5d1d91629a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1669843838&rft_id=info:pmid/&rfr_iscdi=true |