{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:58Z","timestamp":1759639018757,"version":"3.40.5"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_46","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"587-598","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Policriti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Gigante","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Linear time construction of compressed text indices in compact space. arXiv preprint arXiv:1401.0936 (2014)","DOI":"10.1145\/2591796.2591885"},{"key":"46_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-319-02432-5_5","volume-title":"String Processing and Information Retrieval","author":"T Beller","year":"2013","unstructured":"Beller, T., Zwerger, M., Gog, S., Ohlebusch, E.: Space-efficient construction of the burrows-wheeler transform. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 5\u201316. Springer, Heidelberg (2013)"},{"issue":"49","key":"46_CR3","first-page":"758","volume":"49","author":"NG de Bruijn","year":"1946","unstructured":"de Bruijn, N.G., Erdos, P.: A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen 49(49), 758\u2013764 (1946)","journal-title":"Koninklijke Nederlandse Akademie v. Wetenschappen"},{"key":"46_CR4","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm (1994)"},{"issue":"3","key":"46_CR5","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00453-011-9535-0","volume":"63","author":"P Ferragina","year":"2012","unstructured":"Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. Algorithmica 63(3), 707\u2013730 (2012)","journal-title":"Algorithmica"},{"issue":"4","key":"46_CR6","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. Journal of the ACM (JACM) 52(4), 688\u2013713 (2005)","journal-title":"Journal of the ACM (JACM)"},{"key":"46_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 390\u2013398. IEEE (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"46_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 345\u2013354. ACM (1989)","DOI":"10.1145\/73007.73040"},{"key":"46_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-07959-2_28","volume-title":"Experimental Algorithms","author":"S Gog","year":"2014","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 326\u2013337. Springer, Heidelberg (2014)"},{"issue":"43","key":"46_CR10","doi-asserted-by":"publisher","first-page":"4414","DOI":"10.1016\/j.tcs.2009.07.022","volume":"410","author":"R Gonz\u00e1lez","year":"2009","unstructured":"Gonz\u00e1lez, R., Navarro, G.: Rank\/select on dynamic compressed sequences and applications. Theoretical Computer Science 410(43), 4414\u20134422 (2009)","journal-title":"Theoretical Computer Science"},{"key":"46_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-16321-0_35","volume-title":"String Processing and Information Retrieval","author":"M He","year":"2010","unstructured":"He, M., Munro, J.I.: Succinct representations of dynamic strings. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 334\u2013346. Springer, Heidelberg (2010)"},{"issue":"9","key":"46_CR12","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"DA Huffman","year":"1952","unstructured":"Huffman, D.A., et al.: A method for the construction of minimum redundancy codes. Proc. IRE 40(9), 1098\u20131101 (1952)","journal-title":"Proc. IRE"},{"issue":"7","key":"46_CR13","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1089\/cmb.2005.12.943","volume":"12","author":"RA Lippert","year":"2005","unstructured":"Lippert, R.A., Mobarry, C.M., Walenz, B.P.: A space-efficient construction of the burrows-wheeler transform for genomic data. Journal of Computational Biology 12(7), 943\u2013951 (2005)","journal-title":"Journal of Computational Biology"},{"issue":"3","key":"46_CR14","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 (JACM) 48(3), 407\u2013430 (2001)","journal-title":"Journal of the ACM (JACM)"},{"key":"46_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2013.07.004","volume":"25","author":"G Navarro","year":"2014","unstructured":"Navarro, G.: Wavelet trees for all. Journal of Discrete Algorithms 25, 2\u201320 (2014)","journal-title":"Journal of Discrete Algorithms"},{"issue":"1","key":"46_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys (CSUR) 39(1), 2 (2007)","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"5","key":"46_CR17","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1137\/130908245","volume":"43","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. SIAM Journal on Computing 43(5), 1781\u20131806 (2014)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"46_CR18","first-page":"16","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms (TALG) 10(3), 16 (2014)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"46_CR19","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: Data Compression Conference, DCC 2009, pp. 193\u2013202. IEEE (2009)","DOI":"10.1109\/DCC.2009.42"},{"key":"46_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-44634-6_39","volume-title":"Algorithms and Data Structures","author":"R Raman","year":"2001","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct dynamic data structures. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 426\u2013437. Springer, Heidelberg (2001)"},{"key":"46_CR21","unstructured":"Tischler, G.: Faster average case low memory semi-external construction of the burrows-wheeler transform. In: CEUR Workshop Proceedings, vol. 1146, pp. 61\u201368 (2014)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:57:26Z","timestamp":1747691846000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}