{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:36Z","timestamp":1750219776057,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Danish Research Council","award":["DFF-9131-00069B"],"award-info":[{"award-number":["DFF-9131-00069B"]}]},{"name":"Danish Research Council","award":["DFF-8021-002498, DFF\u20139131-00069B"],"award-info":[{"award-number":["DFF-8021-002498, DFF\u20139131-00069B"]}]},{"name":"VIL51463","award":["VILLUM FONDEN"],"award-info":[{"award-number":["VILLUM FONDEN"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            Given a string\n            <jats:italic>S<\/jats:italic>\n            of length\n            <jats:italic>n<\/jats:italic>\n            , the classic string indexing problem is to preprocess\n            <jats:italic>S<\/jats:italic>\n            into a compact data structure that supports efficient subsequent pattern queries. In this article, we consider the basic variant where the pattern is given in compressed form and the goal is to achieve query time that is fast in terms of the compressed size of the pattern. This captures the common client-server scenario, where a client submits a query and communicates it in compressed form to a server. Instead of the server decompressing the query before processing it, we consider how to efficiently process the compressed query directly. Our main result is a novel linear space data structure that achieves near-optimal query time for patterns compressed with the classic Lempel-Ziv 1977 (LZ77) compression scheme. Along the way, we develop several data structural techniques of independent interest, including a novel data structure that compactly encodes all LZ77 compressed suffixes of a string in linear space and a general decomposition of tries that reduces the search time from logarithmic in the size of the trie to logarithmic in the length of the pattern.\n          <\/jats:p>","DOI":"10.1145\/3607141","type":"journal-article","created":{"date-parts":[[2023,7,21]],"date-time":"2023-07-21T12:00:04Z","timestamp":1689940804000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["String Indexing with Compressed Patterns"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1120-5154","authenticated-orcid":false,"given":"Philip","family":"Bille","sequence":"first","affiliation":[{"name":"Technical University of Denmark, DTU Compute, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8322-4952","authenticated-orcid":false,"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[{"name":"Technical University of Denmark, DTU Compute, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1078-4075","authenticated-orcid":false,"given":"Teresa Anna","family":"Steiner","sequence":"additional","affiliation":[{"name":"Technical University of Denmark, DTU Compute, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"534","volume-title":"Proc. 39th FOCS","author":"Alstrup Stephen","year":"1998","unstructured":"Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. 1998. Marked ancestor problems. In Proc. 39th FOCS. 534\u2013543."},{"key":"e_1_3_1_3_2","first-page":"159","volume-title":"Proc. 17th SPIRE","author":"Belazzougui Djamal","year":"2010","unstructured":"Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna. 2010. Dynamic Z-fast tries. In Proc. 17th SPIRE. 159\u2013172."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635816"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.12.021"},{"key":"e_1_3_1_6_2","first-page":"65","volume-title":"Proc. 26th CPM","author":"Bille Philip","year":"2015","unstructured":"Philip Bille, Inge Li G\u00f8rtz, Mathias B\u00e6k Tejs Knudsen, Moshe Lewenstein, and Hjalte Wedel Vildh\u00f8j. 2015. Longest common extensions in sublinear space. In Proc. 26th CPM. 65\u201376."},{"key":"e_1_3_1_7_2","first-page":"10:1\u201310:13","volume-title":"Proc. 37th STACS","author":"Bille Philip","year":"2020","unstructured":"Philip Bille, Inge Li G\u00f8rtz, and Teresa Anna Steiner. 2020. String indexing with compressed patterns. In Proc. 37th STACS. 10:1\u201310:13."},{"key":"e_1_3_1_8_2","first-page":"106","volume-title":"Proc. 9th STOC","author":"Carter Larry","year":"1977","unstructured":"Larry Carter and Mark N. Wegman. 1977. Universal classes of hash functions (extended abstract). In Proc. 9th STOC. 106\u2013112."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_3_1_10_2","first-page":"180","volume-title":"Proc. 19th SPIRE","author":"Claude Francisco","year":"2012","unstructured":"Francisco Claude and Gonzalo Navarro. 2012. Improved grammar-based compressed indexes. In Proc. 19th SPIRE. 180\u2013192."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_3_1_12_2","first-page":"390","volume-title":"Proc. 41st FOCS","author":"Ferragina Paolo","year":"2000","unstructured":"Paolo Ferragina and Giovanni Manzini. 2000. Opportunistic data structures with applications. In Proc. 41st FOCS. 390\u2013398."},{"key":"e_1_3_1_13_2","first-page":"269","volume-title":"Proc. 12th SODA","author":"Ferragina Paolo","year":"2001","unstructured":"Paolo Ferragina and Giovanni Manzini. 2001. An experimental study of an opportunistic index. In Proc. 12th SODA. 269\u2013278."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_3_1_16_2","first-page":"26:1\u201326:11","volume-title":"Proc. 27th CPM","author":"Fischer Johannes","year":"2016","unstructured":"Johannes Fischer, Dominik K\u00f6ppl, and Florian Kurpicz. 2016. On the benefit of merging suffix array intervals for parallel pattern matching. In Proc. 27th CPM. 26:1\u201326:11."},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_1_18_2","first-page":"731","volume-title":"Proc. 11th LATIN","author":"Gagie Travis","year":"2014","unstructured":"Travis Gagie, Pawe\u0142 Gawrychowski, Juha K\u00e4rkk\u00e4inen, Yakov Nekrich, and Simon J Puglisi. 2014. LZ77-based self-indexing with faster pattern matching. In Proc. 11th LATIN. 731\u2013742."},{"key":"e_1_3_1_19_2","first-page":"399","volume-title":"Proc. 10th LATIN","author":"Gagie Travis","year":"2012","unstructured":"Travis Gagie, Kalle Karhu, Juha K\u00e4rkk\u00e4inen, Veli M\u00e4kinen, Leena Salmela, and Jorma Tarhio. 2012. Indexed multi-pattern matching. In Proc. 10th LATIN. 399\u2013407."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.3389\/fbioe.2015.00012"},{"key":"e_1_3_1_21_2","first-page":"54:1\u201354:18","volume-title":"Proc. 28th ESA","author":"Gao Younan","year":"2020","unstructured":"Younan Gao, Meng He, and Yakov Nekrich. 2020. Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing. In Proc. 28th ESA. 54:1\u201354:18."},{"key":"e_1_3_1_22_2","first-page":"316","volume-title":"Proc. 9th DCC","author":"Gasieniec Leszek","year":"1999","unstructured":"Leszek Gasieniec and Wojciech Rytter. 1999. Almost optimal fully LZW-compressed pattern matching. In Proc. 9th DCC. 316\u2013325."},{"key":"e_1_3_1_23_2","first-page":"624","volume-title":"Proc. 29th STACS","author":"Gawrychowski Pawel","year":"2012","unstructured":"Pawel Gawrychowski. 2012. Tying up the loose ends in fully LZW-compressed pattern matching. In Proc. 29th STACS. 624\u2013635."},{"key":"e_1_3_1_24_2","first-page":"841","volume-title":"Proc. 14th SODA","author":"Grossi Roberto","year":"2003","unstructured":"Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. In Proc. 14th SODA. 841\u2013850."},{"key":"e_1_3_1_25_2","first-page":"636","volume-title":"Proc. 15th SODA","author":"Grossi Roberto","year":"2004","unstructured":"Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2004. When indexing equals compression: Experiments with compressing suffix arrays and applications. In Proc. 15th SODA. 636\u2013645."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_3_1_28_2","first-page":"132","volume-title":"Proc. 7th SPIRE","author":"Hirao Masahiro","year":"2000","unstructured":"Masahiro Hirao, Ayumi Shinohara, Masayuki Takeda, and Setsuo Arikawa. 2000. Fully compressed pattern matching algorithm for balanced straight-line programs. In Proc. 7th SPIRE. 132\u2013138."},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003728"},{"issue":"3","key":"e_1_3_1_30_2","first-page":"20:1\u201320:43","article-title":"Faster fully compressed pattern matching by recompression","volume":"11","author":"Jez Artur","year":"2015","unstructured":"Artur Jez. 2015. Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms 11, 3 (2015), 20:1\u201320:43.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009205"},{"key":"e_1_3_1_33_2","first-page":"141","volume-title":"Proc. 3rd WSP","author":"K\u00e4rkk\u00e4inen Juha","year":"1996","unstructured":"Juha K\u00e4rkk\u00e4inen and Esko Ukkonen. 1996. Lempel-Ziv parsing and sublinear-size index structures for string matching. In Proc. 3rd WSP. 141\u2013155."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.10.010"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.006"},{"key":"e_1_3_1_37_2","first-page":"305","volume-title":"Proc. 11th CPM","author":"M\u00e4kinen Veli","year":"2000","unstructured":"Veli M\u00e4kinen. 2000. Compact suffix array. In Proc. 11th CPM. 305\u2013319."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0169"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.07.009"},{"key":"e_1_3_1_40_2","first-page":"274","volume-title":"Proc. 23rd IWOCA","author":"Navarro Gonzalo","year":"2012","unstructured":"Gonzalo Navarro. 2012. Indexing highly repetitive collections. In Proc. 23rd IWOCA. 274\u2013279."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/3092586"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"e_1_3_1_44_2","first-page":"1","volume-title":"Proc. 14th FOCS","author":"Weiner Peter","year":"1973","unstructured":"Peter Weiner. 1973. Linear pattern matching algorithms. In Proc. 14th FOCS. 1\u201311."},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3607141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:33Z","timestamp":1750178253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3607141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3607141"],"URL":"https:\/\/doi.org\/10.1145\/3607141","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"2020-03-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}