{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T10:39:25Z","timestamp":1761561565154},"reference-count":46,"publisher":"Wiley","issue":"8","license":[{"start":{"date-parts":[[2011,8,24]],"date-time":"2011-08-24T00:00:00Z","timestamp":1314144000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>The Burrows\u2013Wheeler Transform (<jats:sc>BWT<\/jats:sc>) produces a permutation of a string <jats:italic>X<\/jats:italic>, denoted <jats:italic>X<\/jats:italic><jats:sup>\u2217<\/jats:sup>, by sorting the <jats:italic>n<\/jats:italic> cyclic rotations of <jats:italic>X<\/jats:italic> into full lexicographical order and taking the last column of the resulting <jats:italic>n<\/jats:italic>\u00d7<jats:italic>n<\/jats:italic> matrix to be <jats:italic>X<\/jats:italic><jats:sup>\u2217<\/jats:sup>. The transformation is reversible in<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0001.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0001\" \/> time. In this paper, we consider an alteration to the process, called <jats:italic>k<\/jats:italic>\u2010<jats:sc>BWT<\/jats:sc>, where rotations are only sorted to a depth <jats:italic>k<\/jats:italic>. We propose new approaches to the forward and reverse transform, and show that the methods are efficient in practice. More than a decade ago, two algorithms were independently discovered for reversing <jats:italic>k<\/jats:italic>\u2010<jats:sc>BWT<\/jats:sc>, both of which run in<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0002.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0002\" \/> time. Two recent algorithms have lowered the bounds for the reverse transformation to<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0003.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0003\" \/> and<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0004.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0004\" \/>, respectively. We examine the practical performance for these reversal algorithms. We find that the original<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0005.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0005\" \/> approach is most efficient in practice, and investigates new approaches, aimed at further speeding reversal, which store precomputed context boundaries in the compressed file. By explicitly encoding the context boundaries, we present an<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/spe1112-math-0006.gif\" xlink:title=\"urn:x-wiley:380644:media:spe1112:spe1112-math-0006\" \/> reversal technique that is both efficient and effective. Finally, our study elucidates an inherently cache\u2010friendly \u2013 and hitherto unobserved \u2013 behavior in the reverse <jats:italic>k<\/jats:italic>\u2010<jats:sc>BWT<\/jats:sc>, which could lead to new applications of the <jats:italic>k<\/jats:italic>\u2010<jats:sc>BWT<\/jats:sc> transform. In contrast to previous empirical studies, we show that the partial transform can be reversed significantly faster than the full transform, without significantly affecting compression effectiveness. Copyright \u00a9 2011 John Wiley &amp; Sons, Ltd.<\/jats:p>","DOI":"10.1002\/spe.1112","type":"journal-article","created":{"date-parts":[[2011,8,31]],"date-time":"2011-08-31T22:38:44Z","timestamp":1314830324000},"page":"1037-1054","source":"Crossref","is-referenced-by-count":8,"title":["Revisiting bounded context block\u2010sorting transformations"],"prefix":"10.1002","volume":"42","author":[{"given":"J. Shane","family":"Culpepper","sequence":"first","affiliation":[{"name":"School of Computer Science &amp; Information Technology RMIT University  Melbourne VIC 3001 Australia"}]},{"given":"Matthias","family":"Petri","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Information Technology RMIT University  Melbourne VIC 3001 Australia"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"School of Computer Science &amp; Information Technology RMIT University  Melbourne VIC 3001 Australia"}]}],"member":"311","published-online":{"date-parts":[[2011,8,24]]},"reference":[{"key":"e_1_2_12_2_1","unstructured":"BurrowsM WheelerDJ.A block\u2010sorting lossless data compression algorithm.Technical Report 124 Digital Equipment Corporation Palo Alto California 1994."},{"key":"e_1_2_12_3_1","unstructured":"FenwickP.Block sorting text compression\u2013final report.Technical Report 130 University of Auckland 1996."},{"key":"e_1_2_12_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.888040"},{"key":"e_1_2_12_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2000.838160"},{"key":"e_1_2_12_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_12_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.995542"},{"key":"e_1_2_12_8_1","first-page":"756","volume-title":"Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006)","author":"Ferragina P","year":"2006"},{"key":"e_1_2_12_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2000.838157"},{"key":"e_1_2_12_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2001.917175"},{"key":"e_1_2_12_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_12_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1455268"},{"key":"e_1_2_12_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-78909-5"},{"key":"e_1_2_12_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1997.582137"},{"key":"e_1_2_12_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6440(199906)82:6<18::AID-ECJC3>3.0.CO;2-7"},{"key":"e_1_2_12_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242471.1242472"},{"key":"e_1_2_12_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_12_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1278374"},{"key":"e_1_2_12_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_9"},{"key":"e_1_2_12_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.018"},{"key":"e_1_2_12_21_1","first-page":"451","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), Part I","author":"K\u00e4rkk\u00e4inen J","year":"2010"},{"key":"e_1_2_12_22_1","first-page":"293","volume-title":"Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005)","author":"Lauther U","year":"2005"},{"key":"e_1_2_12_23_1","volume-title":"Text Compression","author":"Bell TC","year":"1990"},{"key":"e_1_2_12_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0935-6"},{"key":"e_1_2_12_25_1","volume-title":"Data Compression: The Complete Reference","author":"Salomon D","year":"2007"},{"key":"e_1_2_12_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_12_27_1","first-page":"1162","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases. (VLDB 2007)","author":"Vo BD","year":"2007"},{"key":"e_1_2_12_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_10"},{"key":"e_1_2_12_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69068-9_18"},{"key":"e_1_2_12_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13509-5_30"},{"key":"e_1_2_12_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.70762"},{"key":"e_1_2_12_32_1","unstructured":"FerraginaP NavarroG.Pizza & Chili corpus \u2013 Compressed indexes and their testbeds 2005."},{"key":"e_1_2_12_33_1","first-page":"81","volume-title":"Proceedings of the 6th International Symposium on String Processing and Information Retrieval (SPIRE 1999)","author":"Itoh H","year":"1999"},{"key":"e_1_2_12_34_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-540-89097-3_3","volume-title":"Proceedings of the 15th International Conference on String Processing and Information Retrieval (SPIRE 2008)","author":"K\u00e4rkk\u00e4inen J","year":"2008"},{"key":"e_1_2_12_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_12_36_1","first-page":"572","volume-title":"Proceedings of the 8th IEEE Data Compression Conference (DCC 1998)","author":"Schindler M","year":"1998"},{"key":"e_1_2_12_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_2_12_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_2_12_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_1"},{"key":"e_1_2_12_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_12_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1992.227475"},{"key":"e_1_2_12_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.426"},{"key":"e_1_2_12_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1996.488385"},{"key":"e_1_2_12_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2000.838154"},{"key":"e_1_2_12_45_1","first-page":"107","volume-title":"Proceedings of the 4th International Conference on Research in Computational Molecular Biology (RECOMB 2000)","author":"Chen X","year":"2000"},{"key":"e_1_2_12_46_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp319"},{"key":"e_1_2_12_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082043"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.1112","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.1112","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T22:32:48Z","timestamp":1698705168000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.1112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,24]]},"references-count":46,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1002\/spe.1112"],"URL":"https:\/\/doi.org\/10.1002\/spe.1112","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,24]]}}}