{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T12:32:52Z","timestamp":1780489972691,"version":"3.54.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T00:00:00Z","timestamp":1609372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC"},{"name":"Chile, and Basal Funds","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}]},{"name":"ISF","award":["1278\/16 and 1926\/19"],"award-info":[{"award-number":["1278\/16 and 1926\/19"]}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"name":"BSF","award":["2018364"],"award-info":[{"award-number":["2018364"]}]},{"name":"Fondecyt","award":["1-200038"],"award-info":[{"award-number":["1-200038"]}]},{"name":"MIUR-SIR CMACBioSeq","award":["RBSI146R5L"],"award-info":[{"award-number":["RBSI146R5L"]}]},{"name":"MPM under the EU\u2019s Horizon 2020 Research and Innovation Programme","award":["683064"],"award-info":[{"award-number":["683064"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>\n            We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To achieve this result, we combine several recent findings, including\n            <jats:italic>string attractors<\/jats:italic>\n            \u2014new combinatorial objects encompassing most known compressibility measures for highly repetitive texts\u2014and grammars based on\n            <jats:italic>locally consistent parsing<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            More in detail, let\u03b3 be the size of the smallest attractor for a text\n            <jats:italic>T<\/jats:italic>\n            of length\n            <jats:italic>n<\/jats:italic>\n            . The measure\u03b3 is an (asymptotic) lower bound to the size of dictionary compressors based on Lempel\u2013Ziv, context-free grammars, and many others. The smallest known text representations in terms of attractors use space\n            <jats:italic>O<\/jats:italic>\n            (\u03b3 log (\n            <jats:italic>n<\/jats:italic>\n            \/\u03b3)), and our lightest indexes work within the same asymptotic space. Let \u03b5 &gt; 0 be a suitably small constant fixed at construction time,\n            <jats:italic>m<\/jats:italic>\n            be the pattern length, and\n            <jats:italic>occ<\/jats:italic>\n            be the number of its text occurrences. Our index counts pattern occurrences in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +log\n            <jats:sup>2+\u03b5<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time and locates them in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +(\n            <jats:italic>occ<\/jats:italic>\n            +1)log\n            <jats:sup>\u03b5<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time. These times already outperform those of most dictionary-compressed indexes, while obtaining the least asymptotic space for any index searching within\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>occ<\/jats:italic>\n            ),polylog,\n            <jats:italic>n<\/jats:italic>\n            ) time. Further, by increasing the space to\n            <jats:italic>O<\/jats:italic>\n            (\u03b3 log (\n            <jats:italic>n<\/jats:italic>\n            \/\u03b3)log\n            <jats:sup>\u03b5<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), we reduce the locating time to the optimal\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>occ<\/jats:italic>\n            ), and within\n            <jats:italic>O<\/jats:italic>\n            (\u03b3 log (\n            <jats:italic>n<\/jats:italic>\n            \/\u03b3)log\n            <jats:italic>n<\/jats:italic>\n            ) space we can also count in optimal\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) time. No dictionary-compressed index had obtained this time before. All our indexes can be constructed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) space and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) expected time.\n          <\/jats:p>\n          <jats:p>\n            As a by-product of independent interest, we show how to build, in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) expected time and without knowing the size\u03b3 of the smallest attractor (which is NP-hard to find), a run-length context-free grammar of size\n            <jats:italic>O<\/jats:italic>\n            (\u03b3 log (\n            <jats:italic>n<\/jats:italic>\n            \/\u03b3)) generating (only)\n            <jats:italic>T<\/jats:italic>\n            . As a result, our indexes can be built without knowing\u03b3.\n          <\/jats:p>","DOI":"10.1145\/3426473","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T18:48:01Z","timestamp":1609440481000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Optimal-Time Dictionary-Compressed Indexes"],"prefix":"10.1145","volume":"17","author":[{"given":"Anders Roy","family":"Christiansen","sequence":"first","affiliation":[{"name":"The Technical University of Denmark, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikko Berggren","family":"Ettienne","sequence":"additional","affiliation":[{"name":"The Technical University of Denmark, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel, and University of California, Berkeley, US"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"CeBiB and University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3553-4953","authenticated-orcid":false,"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[{"name":"Ca\u2019 Foscari University of Venice, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796605"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917)","volume":"78","author":"Belazzougui Djamal","year":"2017","unstructured":"Djamal Belazzougui and Fabio Cunial . 2017 . Representing the suffix tree with the CDAWG . In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917) , LIPIcs, Vol. 78 . 7:1--7:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.7 10.4230\/LIPIcs.CPM.2017.7 Djamal Belazzougui and Fabio Cunial. 2017. Representing the suffix tree with the CDAWG. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917), LIPIcs, Vol. 78. 7:1--7:13. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_3"},{"key":"e_1_2_1_6_1","article-title":"Alphabet-independent compressed text indexing","volume":"10","author":"Belazzougui Djamal","year":"2014","unstructured":"Djamal Belazzougui and Gonzalo Navarro . 2014 . Alphabet-independent compressed text indexing . ACM Trans. Algor. 10 , 4 (2014), 23:1--23:19. DOI:https:\/\/doi.org\/10.1145\/2635816 10.1145\/2635816 Djamal Belazzougui and Gonzalo Navarro. 2014. Alphabet-independent compressed text indexing. ACM Trans. Algor. 10, 4 (2014), 23:1--23:19. DOI:https:\/\/doi.org\/10.1145\/2635816","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 2053--2071","author":"Belazzougui Djamal","year":"1974","unstructured":"Djamal Belazzougui and Simon J. Puglisi . 2016. Range predecessor and Lempel--Ziv parsing . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 2053--2071 . DOI:https:\/\/doi.org\/10.1137\/1.978161 1974 331.ch143 10.1137\/1.9781611974331.ch143 Djamal Belazzougui and Simon J. Puglisi. 2016. Range predecessor and Lempel--Ziv parsing. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 2053--2071. DOI:https:\/\/doi.org\/10.1137\/1.9781611974331.ch143"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.05.002"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.12.021"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.01.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.06.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998198"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_25"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_19"},{"key":"#cr-split#-e_1_2_1_20_1.1","doi-asserted-by":"crossref","unstructured":"Maxime Crochemore and Wojciech Rytter. 2003. Jewels of Stringology. World Scientific. DOI:https:\/\/doi.org\/10.1142\/4838 10.1142\/4838","DOI":"10.1142\/4838"},{"key":"#cr-split#-e_1_2_1_20_1.2","doi-asserted-by":"crossref","unstructured":"Maxime Crochemore and Wojciech Rytter. 2003. Jewels of Stringology. World Scientific. DOI:https:\/\/doi.org\/10.1142\/4838","DOI":"10.1142\/4838"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN\u201914)","volume":"8392","author":"Gagie Travis","unstructured":"Travis Gagie , Pawel Gawrychowski , Juha K\u00e4rkk\u00e4inen , Yakov Nekrich , and Simon J. Puglisi . 2014. LZ77-based self-indexing with faster pattern matching . In Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN\u201914) LNCS, Vol. 8392 . 731--742. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63 10.1007\/978-3-642-54423-1_63 Travis Gagie, Pawel Gawrychowski, Juha K\u00e4rkk\u00e4inen, Yakov Nekrich, and Simon J. Puglisi. 2014. LZ77-based self-indexing with faster pattern matching. In Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN\u201914) LNCS, Vol. 8392. 731--742. DOI:https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.96"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.78"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_36"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.99"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.27"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 3rd South American Workshop on String Processing (WSP\u201996)","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 Proceedings of the 3rd South American Workshop on String Processing (WSP\u201996) . 141--155. http:\/\/www.cs.helsinki.fi\/juha.karkkainen\/publications\/wsp96-final.ps.gz. Juha K\u00e4rkk\u00e4inen and Esko Ukkonen. 1996. Lempel-Ziv parsing and sublinear-size index structures for string matching. In Proceedings of the 3rd South American Workshop on String Processing (WSP\u201996). 141--155. http:\/\/www.cs.helsinki.fi\/juha.karkkainen\/publications\/wsp96-final.ps.gz."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188814"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00426-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920)","author":"Kociumaka T.","unstructured":"T. Kociumaka , G. Navarro , and N. Prezza . 2020. Towards a definitive measure of repetitiveness . In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920) . T. Kociumaka, G. Navarro, and N. Prezza. 2020. Towards a definitive measure of repetitiveness. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.006"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055501"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.11.022"},{"key":"e_1_2_1_39_1","volume-title":"Compressed full-text indexes. Comput. Surv. 39, 1","author":"Navarro Gonzalo","year":"2007","unstructured":"Gonzalo Navarro and Veli M\u00e4kinen . 2007. Compressed full-text indexes. Comput. Surv. 39, 1 ( 2007 ). DOI:https:\/\/doi.org\/10.1145\/1216370.1216372 10.1145\/1216370.1216372 Gonzalo Navarro and Veli M\u00e4kinen. 2007. Compressed full-text indexes. Comput. Surv. 39, 1 (2007). DOI:https:\/\/doi.org\/10.1145\/1216370.1216372"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.007"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916)","volume":"58","author":"Nishimoto Takaaki","year":"2016","unstructured":"Takaaki Nishimoto , Tomohiro I, Shunsuke Inenaga , Hideo Bannai , and Masayuki Takeda . 2016 . Fully dynamic data structure for LCE queries in compressed space . In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916) , LIPIcs, Vol. 58 . 72:1--72:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.72 10.4230\/LIPIcs.MFCS.2016.72 Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. 2016. Fully dynamic data structure for LCE queries in compressed space. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS\u201916), LIPIcs, Vol. 58. 72:1--72:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.72"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.014"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM\u201919)","volume":"128","author":"Prezza Nicola","year":"2019","unstructured":"Nicola Prezza . 2019 . Optimal rank and select queries on dictionary-compressed text . In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM\u201919) , LIPIcs, Vol. 128 . 4:1--4:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.4 10.4230\/LIPIcs.CPM.2019.4 Nicola Prezza. 2019. Optimal rank and select queries on dictionary-compressed text. In Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM\u201919), LIPIcs, Vol. 128. 4:1--4:12. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2019.4"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9618-6"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.1002195"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214019"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426473","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3426473","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:45Z","timestamp":1750197705000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3426473"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,31]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3426473"],"URL":"https:\/\/doi.org\/10.1145\/3426473","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,31]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}