{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:20:59Z","timestamp":1725603659717},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_63","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"748-759","source":"Crossref","is-referenced-by-count":19,"title":["Alphabet-Independent Compressed Text Indexing"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"63_CR1","series-title":"NATO ISI Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"Apostolico, A.: The myriad virtues of subword trees. In: Combinatorial Algorithms on Words. NATO ISI Series, pp. 85\u201396. Springer, Heidelberg (1985)"},{"key":"63_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-17514-5_27","volume-title":"Algorithms and Computation","author":"J. Barbay","year":"2010","unstructured":"Barbay, J., Gagie, T., Navarro, G., Nekrich, Y.: Alphabet partitioning for compressed rank\/Select and applications. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part II. LNCS, vol.\u00a06507, pp. 315\u2013326. Springer, Heidelberg (2010)"},{"key":"63_CR3","unstructured":"Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: SODA, pp. 680\u2013689 (2007)"},{"key":"63_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with o(1) accesses. In: SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"63_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Theory and practise of monotone minimal perfect hashing. In: ALENEX (2009)","DOI":"10.1137\/1.9781611972894.13"},{"key":"63_CR6","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"issue":"4","key":"63_CR7","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1145\/1082036.1082043","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM\u00a052(4), 688\u2013713 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"63_CR8","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string b-tree: A new data structure for string search in external memory and its applications. J. ACM\u00a046(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"key":"63_CR9","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"4","key":"63_CR10","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"63_CR11","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg. 3(2), article 20 (2007)","DOI":"10.1145\/1240233.1240243"},{"issue":"6","key":"63_CR12","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.ipl.2006.04.008","volume":"99","author":"T. Gagie","year":"2006","unstructured":"Gagie, T.: Large alphabets and incompressibility. Inf. Proc. Lett.\u00a099(6), 246\u2013251 (2006)","journal-title":"Inf. Proc. Lett."},{"key":"63_CR13","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: SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"63_CR14","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: SODA, pp. 841\u2013850 (2003)"},{"key":"63_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-642-14165-2_57","volume-title":"Automata, Languages and Programming","author":"R. Grossi","year":"2010","unstructured":"Grossi, R., Orlandi, A., Raman, R.: Optimal trade-offs for succinct string indexes. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 678\u2013689. Springer, Heidelberg (2010)"},{"key":"63_CR16","doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: STOC, pp. 397\u2013406 (2000)","DOI":"10.1145\/335305.335351"},{"key":"63_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-540-73437-6_12","volume-title":"Combinatorial Pattern Matching","author":"S. Lee","year":"2007","unstructured":"Lee, S., Park, K.: Dynamic rank-select structures with applications to run-length encoded texts. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 95\u2013106. Springer, Heidelberg (2007)"},{"issue":"5","key":"63_CR18","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comp.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"63_CR19","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. J. ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"63_CR20","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":"I. Munro","year":"1996","unstructured":"Munro, I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"63_CR21","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv. 39(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"63_CR22","unstructured":"Raman, R., Raman, V., Rao, S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA, pp. 233\u2013242 (2002)"},{"key":"63_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/3-540-40996-3_35","volume-title":"Algorithms and Computation","author":"K. Sadakane","year":"2000","unstructured":"Sadakane, K.: Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 295\u2013321. Springer, Heidelberg (2000)"},{"issue":"2","key":"63_CR24","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Alg.\u00a048(2), 294\u2013313 (2003)","journal-title":"J. Alg."},{"issue":"4","key":"63_CR25","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theo. Comp. Sys.\u00a041(4), 589\u2013607 (2007)","journal-title":"Theo. Comp. Sys."},{"key":"63_CR26","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"key":"63_CR27","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. Ann. IEEE Symp. on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:08:23Z","timestamp":1560528503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}