{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T03:10:15Z","timestamp":1738897815523,"version":"3.37.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,1,21]],"date-time":"2009-01-21T00:00:00Z","timestamp":1232496000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s00453-008-9269-9","type":"journal-article","created":{"date-parts":[[2009,1,20]],"date-time":"2009-01-20T19:55:52Z","timestamp":1232481352000},"page":"339-351","source":"Crossref","is-referenced-by-count":0,"title":["Space Efficient Algorithms for the Burrows-Wheeler Backtransformation"],"prefix":"10.1007","volume":"58","author":[{"given":"Ulrich","family":"Lauther","sequence":"first","affiliation":[]},{"given":"Tam\u00e1s","family":"Lukovszki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,21]]},"reference":[{"key":"9269_CR1","unstructured":"Abel, J.: Grundlagen des Burrows-Wheeler-Kompressionsalgorithmus (in German). Informatik\u2014Forschung und Entwicklung (2003). http:\/\/www.data-compression.info\/JuergenAbel\/Preprints\/Preprint_Grundlagen_BWCA.pdf"},{"key":"9269_CR2","doi-asserted-by":"crossref","unstructured":"Arnavut, Z.: Generalization of the BWT transformation and inversion ranks. In: Proc. IEEE Data Compression Conference (DCC\u201902), p. 447 (2002)","DOI":"10.1109\/DCC.2002.999990"},{"volume-title":"Algorithms and Theory of Computation Handbook","year":"1999","key":"9269_CR3","unstructured":"Atallah, M.J. (ed.): Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton (1999)"},{"issue":"10","key":"9269_CR4","first-page":"1043","volume":"23","author":"B. Balkenhol","year":"2000","unstructured":"Balkenhol, B., Kurtz, S.: Universal data compression based on the Burrows-Wheeler transformation: Theory and practice. IEEE Trans. Comput. 23(10), 1043\u20131053 (2000)","journal-title":"IEEE Trans. Comput."},{"key":"9269_CR5","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proc. 8th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997), p. 360\u2013369 (1997)"},{"key":"9269_CR6","doi-asserted-by":"crossref","unstructured":"Burkhardt, S., K\u00e4rkk\u00e4inen, J.: Fast lightweight suffix array construction and checking. In: Proc. 14th Symposium on Combinatorial Pattern Matching (CPM\u201903), pp. 55\u201369 (2003)","DOI":"10.1007\/3-540-44888-8_5"},{"key":"9269_CR7","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report 124, Digital Equipment Corporation (1994). http:\/\/gatekeeper.research.compaq.com\/pub\/DEC\/SRC\/research-reports\/abstracts\/src-rr-124.html"},{"key":"9269_CR8","unstructured":"The Canterbury Corpus: http:\/\/corpus.canterbury.ac.nz\/"},{"key":"9269_CR9","unstructured":"Fenwick, P.: Block sorting text compression\u2014final report. Technical report, Department of Computer Science, The University of Auckland (1996). ftp:\/\/ftp.cs.auckland.ac.nz\/pub\/staff\/peter-f\/TechRep130.ps"},{"key":"9269_CR10","unstructured":"Ferragina, P., Manzini, G.: An experimental study of an opportunistic index. In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901), pp. 269\u2013278 (2001)"},{"key":"9269_CR11","unstructured":"Ferragina, P., Manzini, G.: Compression boosting in optimal linear time using the Burrows-Wheeler transform. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904), pp. 655\u2013663 (2004)"},{"key":"9269_CR12","unstructured":"Toms hardware guide: http:\/\/www.tomshardware.com\/cpu\/20001120\/p4-01.html"},{"key":"9269_CR13","doi-asserted-by":"crossref","unstructured":"Itoh, H., Tanaka, H.: An efficient method for in-memory construction of suffix arrays. In: Proc. 6th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 81\u201388 (1999)","DOI":"10.1109\/SPIRE.1999.796581"},{"issue":"3","key":"9269_CR14","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.tcs.2007.07.017","volume":"387","author":"N.J. Larsson","year":"2007","unstructured":"Larsson, N.J., Sadakane, K.: Faster suffix sorting. Theor. Comput. Sci. 387(3), 258\u2013272 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9269_CR15","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Meyers, E.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22, 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9269_CR16","doi-asserted-by":"crossref","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 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"9269_CR17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00453-004-1094-1","volume":"40","author":"G. Manzini","year":"2004","unstructured":"Manzini, G., Ferragina, P.: Engineering a lightweight suffix array construction algorithm. Algorithmica 40(1), 33\u201350 (2004)","journal-title":"Algorithmica"},{"key":"9269_CR18","doi-asserted-by":"crossref","unstructured":"Na, J.C.: Linear-time construction of compressed suffix arrays using o(nlog\u2009n)-bit working space for large alphabets. In: Proc. 16th Symposium on Combinatorial Pattern Matching (CPM\u201905), pp. 56\u201367 (2005)","DOI":"10.1007\/11496656_6"},{"key":"9269_CR19","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full text indexes. ACM Comput. Surv. 39(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"key":"9269_CR20","unstructured":"Nelson, M.: Data compression with the Burrows-Wheeler transform. Dr. Dobb\u2019s J. 9 (1996)"},{"key":"9269_CR21","doi-asserted-by":"crossref","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.H.: A taxonomy of suffix array construction algorithms. ACM Comput. Surv. 39(2) (2007)","DOI":"10.1145\/1242471.1242472"},{"key":"9269_CR22","unstructured":"Seward, J.: Bzip2 manual. http:\/\/www.bzip.org\/1.0.3\/bzip2-manual-1.0.3.html"},{"key":"9269_CR23","doi-asserted-by":"crossref","unstructured":"Seward, J.: On the performance of BWT sorting algorithms. In: Proc. IEEE Data Compression Conference (DCC\u201900), pp. 173\u2013182 (2000)","DOI":"10.1109\/DCC.2000.838157"},{"key":"9269_CR24","doi-asserted-by":"crossref","unstructured":"Seward, J.: Space-time tradeoffs in the inverse B-W transform. In: Proc. IEEE Data Compression Conference (DCC\u201901), pp. 439\u2013448 (2001)","DOI":"10.1109\/DCC.2001.917175"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9269-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9269-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9269-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T02:41:34Z","timestamp":1738896094000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9269-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,21]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9269"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9269-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,1,21]]}}}