{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T22:53:34Z","timestamp":1790636014809,"version":"4.1.0"},"reference-count":67,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel--Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\\mathcal{S}$ of size $n$. We present two representations of $\\mathcal{S}$ achieving $O(\\log N)$ random access time, and either $O(n\\cdot\\alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\\alpha_k(n)$ is the inverse of the $k$th row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\\min\\{|P|k,k^4+|P|\\}+\\log N)+\\mathrm{occ})$, where $\\mathrm{occ}$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two \u201cbiased\u201d weighted ancestor data structures, and a compact representation of heavy paths in grammars.<\/jats:p>","DOI":"10.1137\/130936889","type":"journal-article","created":{"date-parts":[[2015,5,5]],"date-time":"2015-05-05T13:01:35Z","timestamp":1430830895000},"page":"513-539","source":"Crossref","is-referenced-by-count":82,"title":["Random Access to Grammar-Compressed Strings and Trees"],"prefix":"10.1137","volume":"44","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,5,5]]},"reference":[{"key":"atypb1","unstructured":"N. Alon and B. Schieber,\n                      Optimal Preprocessing for Answering On-Line Product Queries\n                      , Tech. Report TR-71\/87, Institute of Computer Science, Tel Aviv University, Tel Aviv, Israel, 1987."},{"key":"atypb2","first-page":"534","author":"Alstrup S.","year":"1998","journal-title":"NJ"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0023"},{"key":"atypb4","first-page":"853","author":"Amir A.","year":"2003","journal-title":"Philadelphia"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00097-X"},{"key":"atypb6","first-page":"119","author":"Apostolico A.","year":"1998","journal-title":"Proceedings of the IEEE Data Compression Conference"},{"key":"atypb7","first-page":"143","author":"Apostolico A.","year":"2000","journal-title":"Proceedings of the IEEE Data Compression Conference"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/5.892709"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00215-6"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1138-6"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"atypb12","first-page":"3","volume":"6","author":"Bille P.","year":"2010","journal-title":"ACM Trans. Algorithms"},{"key":"atypb13","first-page":"261","author":"Buneman P.","year":"2005","journal-title":"NJ"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00005-W"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.004"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"P. C\u00e9gielski, I. Guessarian, Y. Lifshits, and Y. Matiyasevich,\n                      Window subsequence problems for compressed texts\n                      , in Proceedings of the 1st Symposium on Computer Science in Russia (CSR), 2006, pp. 127-136.","DOI":"10.1007\/11753728_15"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"B. Chazelle and B. Rosenberg,\n                      Computing partial sums in multidimensional arrays\n                      , in Proceedings of the 5th Annual ACM Symposium on Computational Geometry (SCG), 1989, pp. 131-139.","DOI":"10.1145\/73833.73848"},{"key":"atypb19","first-page":"235","author":"Claude F.","year":"2009","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700370527"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402007"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"O. Delpratt, R. Raman, and N. Rahman,\n                      Engineering succinct dom\n                      , in Proceedings of the International Conference on Extending Database Technology (EDBT), ACM Internat. Conf. Proc. Ser. 261, A. Kemper, P. Valduriez, N. Mouaddib, J. Teubner, M. Bouzeghoub, V. Markl, L. Amsaleg, and I. Manolescu, eds., ACM, New York, 2008, pp. 49-60.","DOI":"10.1145\/1352431.1352442"},{"key":"atypb23","first-page":"341","author":"Demaine E. D.","year":"2009","journal-title":"New York"},{"key":"atypb24","first-page":"130","author":"Farach M.","year":"1996","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"atypb26","unstructured":"F. E. Fich,\n                      Constant-time Operations for Words of Length w\n                      , manuscript, 1999."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80064-9"},{"key":"atypb29","first-page":"23","volume":"12","author":"Gage P.","year":"1994","journal-title":"The C Users J."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.78"},{"key":"atypb31","first-page":"137","volume":"56","author":"Gasieniec L.","year":"2003","journal-title":"Fund. Inform."},{"key":"atypb32","first-page":"366","author":"Hagerup T.","year":"1998","journal-title":"New York"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"atypb34","first-page":"529","author":"Hermelin D.","year":"2009","journal-title":"New York"},{"key":"atypb35","unstructured":"J. Iacono,\n                      private communication\n                      , NYU, New York, 2010."},{"key":"atypb36","first-page":"549","author":"Jacobson G.","year":"1989","journal-title":"NJ"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.09.002"},{"key":"atypb38","first-page":"195","author":"Karkkainen J.","year":"2000","journal-title":"New York"},{"key":"atypb39","unstructured":"J. Karkkainen and E. Ukkonen,\n                      Lempel-Ziv parsing and sublinear-size index structures for string matching\n                      , in Proceedings of the 3rd South American Workshop on String Processing (WSP), 1996, pp. 141-155."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00426-7"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1109\/18.850665"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/5.892708"},{"key":"atypb46","first-page":"228","author":"Lifshits Y.","year":"2007","journal-title":"New York"},{"key":"atypb47","first-page":"1","author":"Makinen V.","year":"1999","journal-title":"New York"},{"key":"atypb48","first-page":"31","author":"Manber U.","year":"1994","journal-title":"New York"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264563"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"atypb51","first-page":"1006","author":"Munro J. I.","year":"2004","journal-title":"New York"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1145\/375360.375365"},{"key":"atypb53","first-page":"459","author":"Navarro G.","year":"2001","journal-title":"NJ"},{"key":"atypb54","first-page":"424","author":"Navarro G.","year":"2014","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1613\/jair.374"},{"key":"atypb56","unstructured":"M. P\u01cetra\u015fcu,\n                      private communication\n                      , 2009."},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"atypb58","first-page":"134","author":"Sadakane K.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"atypb60","unstructured":"Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara, T. Shinohara, and S. Arikawa,\n                      Byte Pair Encoding: A Text Compression Scheme That Accelerates Pattern Matching\n                      , Technical Report DOI-TR-161, Department of Informatics, Kyushu University, Fukuoka, Japan, 1999."},{"key":"atypb61","first-page":"306","author":"Shibata Y.","year":"2000","journal-title":"New York"},{"key":"atypb62","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan,\n                      Data Structures and Network Algorithms\n                      , CBMS-NSF Regional Conf. Ser. in Appl. Math. 44, SIAM, Philadelphia, 1983.","DOI":"10.1137\/1.9781611970265"},{"key":"atypb63","first-page":"247","author":"Verbin E.","year":"2013","journal-title":"New York"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1109\/18.841161"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055501"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130936889","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:03:55Z","timestamp":1787339035000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130936889"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130936889"],"URL":"https:\/\/doi.org\/10.1137\/130936889","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}