{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T20:54:50Z","timestamp":1776113690375,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662483497","type":"print"},{"value":"9783662483503","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_13","type":"book-chapter","created":{"date-parts":[[2015,8,31]],"date-time":"2015-08-31T21:40:34Z","timestamp":1441057234000},"page":"142-154","source":"Crossref","is-referenced-by-count":22,"title":["Access, Rank, and Select in Grammar-compressed Strings"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuo","family":"Tabei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"issue":"19","key":"13_CR1","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.ipl.2012.06.017","volume":"112","author":"H. Bannai","year":"2012","unstructured":"Bannai, H., Gagie, T.I., Inenaga, S., Landau, G.M., Lewenstein, M.: An efficient algorithm to test square-freeness of strings compressed by straight-line programs. Information Processing Letters\u00a0112(19), 711\u2013714 (2012)","journal-title":"Information Processing Letters"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-319-07566-2_5","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2014","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L.: Compressed subsequence matching and packed\u00a0tree\u00a0coloring. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol.\u00a08486, pp. 40\u201349. Springer, Heidelberg (2014)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: Proc. 22nd SODA, pp. 373\u2013389. SIAM (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-642-40104-6_13","volume-title":"Algorithms and Data Structures","author":"P. Bille","year":"2013","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L., Sach, B., Vildh\u00f8j, H.W., Vind, S.: Fingerprints in compressed strings. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 146\u2013157. Springer, Heidelberg (2013)"},{"issue":"7","key":"13_CR5","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Transactions on Information Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"13_CR6","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E. Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM Journal on Computing\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"13_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2006.12.012","volume":"372","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theoretical Computer Science\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theoretical Computer Science"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: Blasting through the information theoretic barrier with fusion trees. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 1\u20137. ACM (1990)","DOI":"10.1145\/100216.100217"},{"issue":"3","key":"13_CR9","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences\u00a047(3), 424\u2013436 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proc. 17th SODA, pp. 368\u2013373. SIAM (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"13_CR11","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. 14th SODA, pp. 841\u2013850. SIAM (2003)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-40273-9_22","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"W.K. Hon","year":"2013","unstructured":"Hon, W.K., Patil, M., Shah, R., Thankachan, S.V., Vitter, J.S.: Indexes for document retrieval with relevance. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol.\u00a08066, pp. 351\u2013362. Springer, Heidelberg (2013)"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/978-3-642-40313-2_51","volume-title":"Mathematical Foundations of Computer Science 2013","author":"T. I","year":"2013","unstructured":"I, T., Matsubara, W., Shimohira, K., Inenaga, S., Bannai, H., Takeda, M., Narisawa, K., Shinohara, A.: Detecting regularities on grammar-compressed strings. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 571\u2013582. Springer, Heidelberg (2013)"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-319-02432-5_21","volume-title":"String Processing and Information Retrieval","author":"T. I","year":"2013","unstructured":"I, T., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M.: Faster lyndon factorization algorithms for SLP and LZ78 compressed text. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol.\u00a08214, pp. 174\u2013185. Springer, Heidelberg (2013)"},{"issue":"2","key":"13_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1142\/S0129054112400126","volume":"23","author":"S. Inenaga","year":"2012","unstructured":"Inenaga, S., Bannai, H.: Finding characteristic substrings from compressed texts. International Journal of Foundations of Computer Science\u00a023(2), 261\u2013280 (2012)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"2","key":"13_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM Journal of Research and Development"},{"key":"13_CR17","first-page":"172","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic Journal of Computing\u00a04, 172\u2013186 (1997)","journal-title":"Nordic Journal of Computing"},{"issue":"3","key":"13_CR18","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. Journal of the ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"Journal of the ACM"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/978-3-642-35926-2_29","volume-title":"IWOCA 2012","author":"G. Navarro","year":"2012","unstructured":"Navarro, G.: Indexing highly repetitive collections. In: Smyth, B. (ed.) IWOCA 2012. LNCS, vol.\u00a07643, pp. 274\u2013279. Springer, Heidelberg (2012)"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. ACM Computing Surveys\u00a046(4), article 52, 47 pages (2014)","DOI":"10.1145\/2535933"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys 39(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-319-11918-2_4","volume-title":"String Processing and Information Retrieval","author":"G. Navarro","year":"2014","unstructured":"Navarro, G., Ord\u00f3\u00f1ez, A.: Grammar compressed sequences with rank\/Select support. In: Moura, E., Crochemore, M. (eds.) SPIRE 2014. LNCS, vol.\u00a08799, pp. 31\u201344. Springer, Heidelberg (2014)"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proc. 9th ALENEX, pp. 60\u201370. SIAM (2007)","DOI":"10.1137\/1.9781611972870.6"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"issue":"1\u20133","key":"13_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comp. Sci.\u00a0302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comp. Sci."},{"key":"13_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-38905-4_24","volume-title":"Combinatorial Pattern Matching","author":"E. Verbin","year":"2013","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 247\u2013258. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T16:24:45Z","timestamp":1559233485000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}