{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T20:54:47Z","timestamp":1776113687182,"version":"3.50.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030592110","type":"print"},{"value":"9783030592127","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-59212-7_16","type":"book-chapter","created":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:05:34Z","timestamp":1600250734000},"page":"221-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Practical Random Access to\u00a0SLP-Compressed Texts"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9106-6192","authenticated-orcid":false,"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-0196","authenticated-orcid":false,"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3470-9187","authenticated-orcid":false,"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3204-3801","authenticated-orcid":false,"given":"Louisa","family":"Seelbach Benkner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4566-8974","authenticated-orcid":false,"given":"Yoshimasa","family":"Takabatake","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,17]]},"reference":[{"key":"16_CR1","unstructured":"Bannai, H., et al.: The smallest grammar problem revisited. CoRR, abs\/1908.06428 (2019)"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-662-48350-3_13","volume-title":"Algorithms \u2013 ESA 2015","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Cording, P.H., Puglisi, S.J., Tabei, Y.: Access, rank, and select in grammar-compressed strings. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 142\u2013154. Springer, Heidelberg (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-662-48350-3_13"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., et al.: Queries on LZ-bounded encodings. In: 2015 Data Compression Conference, pp. 83\u201392. IEEE (2015)","DOI":"10.1109\/DCC.2015.69"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Bille, P., Li G\u00f8rtz, I., Prezza, N.: Space-efficient re-pair compression. In: 2017 Data Compression Conference (DCC), pp. 171\u2013180. IEEE (2017)","DOI":"10.1109\/DCC.2017.24"},{"issue":"3","key":"16_CR5","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/s13015-019-0148-5","volume":"14","author":"C Boucher","year":"2019","unstructured":"Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix-free parsing for building big BWTs. Algorithms Mol. Biol. 14(1), 13 (2019). \nhttps:\/\/doi.org\/10.1186\/s13015-019-0148-5","journal-title":"Algorithms Mol. Biol."},{"issue":"7","key":"16_CR7","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"15","key":"16_CR8","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1093\/bioinformatics\/btr330","volume":"27","author":"P Danecek","year":"2011","unstructured":"Danecek, P., et al.: The variant call format and VCFtools. Bioinformatics 27(15), 2156\u20132158 (2011)","journal-title":"Bioinformatics"},{"key":"16_CR9","unstructured":"Dinklage, P., Fischer, J., Herlez, A., Kociumaka, T., Kurpicz, F.: Practical performance of space efficient data structures for longest common extensions. In: Proceedings of the Twenty-Eighth European Symposium on Algorithms (ESA) (2020, to appear)"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Esposito, E., Graf, T.M., Vigna, S.: RecSplit: minimal perfect hashing via recursive splitting. In: 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 175\u2013185. SIAM (2020)","DOI":"10.1137\/1.9781611976007.14"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Furuya, I., Takagi, T., Nakashima, Y., Inenaga, S., Bannai, H., Kida, T.: MR-RePair: grammar compression based on maximal repeats. In: Data Compression Conference. DCC 2019, Snowbird, UT, USA, 26\u201329 March 2019, pp. 508\u2013517 (2019)","DOI":"10.1109\/DCC.2019.00059"},{"issue":"2","key":"16_CR12","first-page":"23","volume":"12","author":"P Gage","year":"1994","unstructured":"Gage, P.: A new algorithm for data compression. C Users J. 12(2), 23\u201338 (1994)","journal-title":"C Users J."},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-030-32686-9_3","volume-title":"String Processing and Information Retrieval","author":"T Gagie","year":"2019","unstructured":"Gagie, T., I, T., Manzini, G., Navarro, G., Sakamoto, H., Takabatake, Y.: Rpair: rescaling RePair with Rsync. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 35\u201344. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-32686-9_3"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Gall\u00e9, M.: Investigating the effectiveness of BPE: the power of shorter sequences. In: Inui, K., Jiang, J., Ng, V., Wan, X. (eds.) Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, 3\u20137 November 2019, pp. 1375\u20131381. Association for Computational Linguistics (2019)","DOI":"10.18653\/v1\/D19-1141"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Je\u017c, A., Lohrey, M.: Balancing straight-line programs. In: 60th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2019, Baltimore, Maryland, USA, 9\u201312 November 2019, pp. 1169\u20131183 (2019)","DOI":"10.1109\/FOCS.2019.00073"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Ga\u0144czorz, M., Je\u017c, A.: Improvements on re-pair grammar compressor. In: 2017 Data Compression Conference (DCC), pp. 181\u2013190. IEEE (2017)","DOI":"10.1109\/DCC.2017.52"},{"key":"16_CR17","doi-asserted-by":"publisher","unstructured":"Hucke, D.: Approximation ratios of RePair, LongestMatch and Greedy on unary strings. In: Brisaboa, N.R., Puglisi, S.J. (eds.) SPIRE 2019. LNCS, vol. 11811, pp. 3\u201315. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-32686-9_1","DOI":"10.1007\/978-3-030-32686-9_1"},{"key":"16_CR18","unstructured":"Hucke, D., Je\u017c, A., Lohrey, M.: Approximation ratio of RePair. CoRR, abs\/1703.06061 (2017)"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Kempa, D., Kociumaka, T.: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 756\u2013767 (2019)","DOI":"10.1145\/3313276.3316368"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-030-17083-7_10","volume-title":"Research in Computational Molecular Biology","author":"A Kuhnle","year":"2019","unstructured":"Kuhnle, A., Mun, T., Boucher, C., Gagie, T., Langmead, B., Manzini, G.: Efficient construction of a complete index for pan-genomics read alignment. In: Cowen, L.J. (ed.) RECOMB 2019. LNCS, vol. 11467, pp. 158\u2013173. Springer, Cham (2019). \nhttps:\/\/doi.org\/10.1007\/978-3-030-17083-7_10"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-16321-0_20","volume-title":"String Processing and Information Retrieval","author":"S Kuruppu","year":"2010","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 201\u2013206. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-16321-0_20"},{"key":"16_CR22","unstructured":"Jesper Larsson, N., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference. DCC 1999, Snowbird, Utah, USA, 29\u201331 March 1999, pp. 296\u2013305 (1999)"},{"issue":"2","key":"16_CR23","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 Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-319-02432-5_25","volume-title":"String Processing and Information Retrieval","author":"S Maruyama","year":"2013","unstructured":"Maruyama, S., Tabei, Y., Sakamoto, H., Sadakane, K.: Fully-online grammar compression. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 218\u2013229. Springer, Cham (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-319-02432-5_25"},{"key":"16_CR25","unstructured":"Navarro, G.: Indexing highly repetitive string collections. CoRR, abs\/2004.02781 (2020)"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-319-94667-2_27","volume-title":"Combinatorial Algorithms","author":"T Ohno","year":"2018","unstructured":"Ohno, T., Goto, K., Takabatake, Y., I, T., Sakamoto, H.: LZ-ABT: a practical algorithm for $$\\alpha $$-balanced grammar compression. In: Iliopoulos, C., Leong, H.W., Sung, W.-K. (eds.) IWOCA 2018. LNCS, vol. 10979, pp. 323\u2013335. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-94667-2_27"},{"key":"16_CR27","unstructured":"Prezza, N.: Optimal rank and select queries on dictionary-compressed text. In: Pisanti, N., Pissis, S.P. (eds.) 30th Annual Symposium on Combinatorial Pattern Matching. CPM 2019, volume 128 of LIPIcs, Pisa, Italy, 18\u201320 June 2019, pp. 4:1\u20134:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"1\u20133","key":"16_CR28","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. Theoret. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-540-27836-8_5","volume-title":"Automata, Languages and Programming","author":"W Rytter","year":"2004","unstructured":"Rytter, W.: Grammar compression, LZ-encodings, and string algorithms with implicit input. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 15\u201327. Springer, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-27836-8_5"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Sakai, K., Ohno, T., Goto, K., Takabatake, Y., I, T., Sakamoto, H.: RePair in compressed space and time. In: 2019 Data Compression Conference (DCC), pp. 518\u2013527. IEEE (2019)","DOI":"10.1109\/DCC.2019.00060"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"Sennrich, R., Haddow, B., Birch, A.: Neural machine translation of rare words with subword units. In: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics. ACL 2016. Volume 1: Long Papers, Berlin, Germany, 7\u201312 August 2016. The Association for Computer Linguistics (2016)","DOI":"10.18653\/v1\/P16-1162"},{"key":"16_CR32","doi-asserted-by":"publisher","first-page":"808","DOI":"10.3389\/fmicb.2017.00808","volume":"8","author":"EL Stevens","year":"2017","unstructured":"Stevens, E.L., et al.: The public health impact of a publically available, environmental database of microbial genomes. Front. Microbiol. 8, 808 (2017)","journal-title":"Front. Microbiol."},{"key":"16_CR33","unstructured":"Takabatake, Y., I, T., Sakamoto, H.: A space-optimal grammar compression. In: 25th Annual European Symposium on Algorithms. ESA 2017, Vienna, Austria, 4\u20136 September 2017, pp. 67:1\u201367:15 (2017)"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"The 1000 Genomes Project Consortium: A global reference for human genetic variation. Nature 526, 68\u201374 (2015)","DOI":"10.1038\/nature15393"},{"key":"16_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. 7922, pp. 247\u2013258. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-38905-4_24"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-59212-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:08:42Z","timestamp":1600250922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-59212-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030592110","9783030592127"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-59212-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Orlando, FL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.ucf.edu\/spire2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"53% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}