{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T08:44:30Z","timestamp":1743669870666},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_14","type":"book-chapter","created":{"date-parts":[[2013,8,10]],"date-time":"2013-08-10T01:20:34Z","timestamp":1376097634000},"page":"199-215","source":"Crossref","is-referenced-by-count":2,"title":["Random Access to High-Order Entropy Compressed Text"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"14_CR1","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms\u00a07(4), 52 (2011)","journal-title":"ACM Transactions on Algorithms"},{"key":"14_CR2","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: SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-03784-9_12","volume-title":"String Processing and Information Retrieval","author":"N.R. Brisaboa","year":"2009","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: Directly addressable variable-length codes. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 122\u2013130. Springer, Heidelberg (2009)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-642-20662-7_12","volume-title":"Experimental Algorithms","author":"N.R. Brisaboa","year":"2011","unstructured":"Brisaboa, N.R., C\u00e1novas, R., Claude, F., Mart\u00ednez-Prieto, M.A., Navarro, G.: Compressed string dictionaries. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol.\u00a06630, pp. 136\u2013147. Springer, Heidelberg (2011)"},{"key":"14_CR5","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation (1994)"},{"issue":"7","key":"14_CR6","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":"1","key":"14_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0196-6774(03)00043-9","volume":"48","author":"E.D. Demaine","year":"2003","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A.: A linear lower bound on index size for text retrieval. J. Algorithms\u00a048(1), 2\u201315 (2003)","journal-title":"J. Algorithms"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Patrascu, M., Thorup, M.: Changing base without losing space. In: STOC, pp. 593\u2013602 (2010)","DOI":"10.1145\/1806689.1806771"},{"issue":"1","key":"14_CR9","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. Theor. Comput. Sci.\u00a0372(1), 115\u2013121 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"14_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0166-218X(93)00116-H","volume":"64","author":"A.S. Fraenkel","year":"1996","unstructured":"Fraenkel, A.S., Kleinb, S.T.: Robust universal complete codes for transmission and compression. Discrete Applied Mathematics\u00a064(1), 31\u201355 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Saks, M.E.: The cell probe complexity of dynamic data structures. In: STOC, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"issue":"1-2","key":"14_CR12","doi-asserted-by":"crossref","first-page":"63","DOI":"10.3233\/FI-2009-0066","volume":"92","author":"K. Fredriksson","year":"2009","unstructured":"Fredriksson, K., Nikitin, F.: Simple random access compression. Fundam. Inform.\u00a092(1-2), 63\u201381 (2009)","journal-title":"Fundam. Inform."},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.tcs.2007.02.047","volume":"379","author":"A. G\u00e1l","year":"2007","unstructured":"G\u00e1l, A., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci.\u00a0379, 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci.\u00a0387, 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/11780441_27","volume-title":"Combinatorial Pattern Matching","author":"R. Gonz\u00e1lez","year":"2006","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Statistical encoding of succinct data structures. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 294\u2013305. Springer, Heidelberg (2006)"},{"issue":"27","key":"14_CR16","doi-asserted-by":"publisher","first-page":"2964","DOI":"10.1016\/j.tcs.2010.12.036","volume":"412","author":"R. Grossi","year":"2011","unstructured":"Grossi, R.: A quick tour on suffix arrays and compressed suffix arrays. Theor. Comput. Sci.\u00a0412(27), 2964\u20132973 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1007\/978-3-642-39206-1_43","volume-title":"ICALP 2013","author":"R. Grossi","year":"2013","unstructured":"Grossi, R., Raman, R., Rao, S.S., Venturini, R.: Dynamic compressed strings with random access. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 504\u2013515. Springer, Heidelberg (2013)"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-13509-5_24","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2010","unstructured":"Hon, W.-K., Shah, R., Vitter, J.S.: Compression, indexing, and retrieval for massive string data. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 260\u2013274. Springer, Heidelberg (2010)"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-31594-7_43","volume-title":"Automata, Languages, and Programming","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.K.: Cram: Compressed random access memory. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 510\u2013521. Springer, Heidelberg (2012)"},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1137\/S0097539797331105","volume":"29","author":"R. Kosaraju","year":"1999","unstructured":"Kosaraju, R., Manzini, G.: Compression of low entropy strings with Lempel-Ziv algorithms. SIAM Journal of Computing\u00a029(3), 893\u2013911 (1999)","journal-title":"SIAM Journal of Computing"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference, pp. 296\u2013305 (1999)","DOI":"10.1109\/DCC.1999.755679"},{"issue":"2","key":"14_CR22","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M. Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on slp-compressed strings: A survey. Groups Complexity Cryptology\u00a04(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/248625.248639","volume":"15","author":"U. Manber","year":"1997","unstructured":"Manber, U.: A text compression scheme that allows fast searching directly in the compressed file. ACM Trans. Inf. Syst.\u00a015(2), 124\u2013136 (1997)","journal-title":"ACM Trans. Inf. Syst."},{"issue":"3","key":"14_CR24","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":"14_CR25","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":"14_CR26","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv.\u00a039(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Ottaviano, G., Grossi, R.: Fast compressed tries through path decompositions. In: ALENEX, pp. 65\u201374 (2012)","DOI":"10.1137\/1.9781611972924.7"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Viola, E.: Cell-probe lower bounds for succinct partial sums. In: Charikar, M. (ed.) SODA, pp. 117\u2013122. SIAM (2010)","DOI":"10.1137\/1.9781611973075.11"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Raman, R., Rao, S.S.: Succinct representations of ordinal trees. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Munro Festschrift 2013. LNCS, vol.\u00a08066, pp. 319\u2013332. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40273-9_20"},{"issue":"1-3","key":"14_CR31","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. Comput. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR32","unstructured":"Sadakane, K.: Personal communication (2012)"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proc. of the 17th ACM-SIAM SODA, pp. 1230\u20131239 (2006)","DOI":"10.1145\/1109557.1109693"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: SODA, pp. 1230\u20131239. ACM Press (2006)","DOI":"10.1145\/1109557.1109693"},{"key":"14_CR35","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)"},{"key":"14_CR36","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers (1999)"},{"issue":"6","key":"14_CR37","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1145\/214762.214771","volume":"30","author":"I.H. Witten","year":"1987","unstructured":"Witten, I.H., Neal, R.M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM\u00a030(6), 520\u2013540 (1987)","journal-title":"Commun. ACM"},{"issue":"5","key":"14_CR38","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T19:36:11Z","timestamp":1596310571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}