Publications
- Yu-Feng Chien, Wing-Kai Hon, Rahul Shah and Jeffrey Vitter, Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 252-261, 2008.
[http://www.cs.purdue.edu/~jsv/Papers/CHS08.geometricbw.pdf]
[http://www.cs.nthu.edu.tw/~wkhon/papers/CHSV08.pdf]
- Ge Nong, Sen Zhang and Wai Hong Chan, Computing Inverse ST in Linear Complexity, 19th Annual Symposium on Combinatorial Pattern Matching (Accepted, To Appear), 2008.
[http://www.cs.sysu.edu.cn/nong/index.files/Computing%20Inverse%20ST%20in%20Linear%20Complexity.pdf]
- Mikaël Salson, Thierry Lecroq, Martine Léonard and Laurent Mouchard, Dynamic Burrows-Wheeler Transform, Proceedings of the Prague Stringology Conference, pp. 13-25, 2008.
[http://www.stringology.org/event/2008/p02.html]
[http://www-igm.univ-mlv.fr/~lecroq/articles/psc2008-sllm.pdf]
- Peter Fenwick, Burrows-Wheeler Compression : Principles and Reflections, Theoretical Computer Science, 387, pp. 200-219, 2007.
[http://www.cs.auckland.ac.nz/~peter-f/FTPfiles/BWreflections.pdf]
- Travis Gagie and Giovanni Manzini, Move-to-Front, Distance Coding, and Inversion Frequencies Revisited, Proceedings of the 18th Symposium on Combinatorial Pattern Matching, LNCS 4580, Springer-Verlag, pp. 71-82, 2007.
[http://www.mfn.unipmn.it/~manzini/cpm07/cpm07extended.pdf]
[http://www.csd.uwo.ca/CPM2007/CPM_2007_Presentaions/CPM%20Session%203/Gagie_Manzini_slides_new.pdf]
- Haim Kaplan and Elad Verbin, Most Burrows-Wheeler Based Compressors are Not Optimal, Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, LNCS 4580, Springer-Verlag, pp. 107-118, 2007.
[http://www.math.tau.ac.il/~haimk/papers/bwt_lb.ps]
[http://www.cs.tau.ac.il/~eladv/papers/bwt_lb.ps]
- Ge Nong and Sen Zhang, Efficient Algorithms for the Inverse Sort Transform, IEEE Transactions on Computers, 56(11), pp. 1564-1574, 2007.
[http://www.cs.sysu.edu.cn/nong/index.files/Efficient%20Algorithms%20for%20the%20Inverse%20Sort.pdf]
- Paolo Ferragina, Raffaele Giancarlo and Giovanni Manzini, The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression, Proceedings of the 14th European Symposium on Algorithms, LNCS 4168, Springer-Verlag, pp. 756-767, 2006.
[http://www.mfn.unipmn.it/~manzini/boosting/booster-tr.pdf]
- Paolo Ferragina, Raffaele Giancarlo and Giovanni Manzini, The Myriad Virtues of Wavelet Trees, Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, LNCS 4051, Springer-Verlag, pp. 561-572, 2006.
[http://www.mfn.unipmn.it/~manzini/papers/icalp06.pdf]
- Juha Karkkainen, Fast BWT in Small Space by Blockwise Suffix Sorting, Theoretical Computer Science, 2006.
[http://www.cs.helsinki.fi/juha.karkkainen/publications/tcs06-revised.ps.gz]
- Haim Kaplan, Shir Landau and Elad Verbin, A Simpler Analysis of Burrows-Wheeler Based Compression, Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, LNCS 4009, Springer-Verlag, pp. 282-293, 2006.
[http://www.math.tau.ac.il/~haimk/papers/bwt.ps]
[http://www.cs.tau.ac.il/~eladv/papers/bwt.ps]
[http://www.cs.tau.ac.il/~eladv/ppt/bwt.ppt]
[http://www.cs.tau.ac.il/~eladv/ppt/bwt2.ppt]
- Dror Baron and Yoram Bresler, Anti-Sequential Suffix Sorting for BWT-Based Data Compression, IEEE Transactions on Computers, 54(4), pp. 385-397, 2005.
[http://www2.ece.rice.edu/~drorb/pdf/116140-2-nobios.pdf]
- Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini and Marinella Sciortino, Boosting Textual Compression in Optimal Linear Time, Journal of the ACM, 52(4), pp. 688-713, 2005.
[http://www.mfn.unipmn.it/~manzini/papers/jacm05b.pdf]
- Ulrich Lauther and Tamas Lukovszki, Space Efficient Algorithms for the Burrows-Wheeler Backtransformation, Proceedings of the 13th Annual European Symposium on Algorithms, LNCS 3669, Springer-Verlag, pp. 293-304, 2005.
[http://people.inf.elte.hu/lukovszki/Publ/esa05.ps.gz]
[http://people.inf.elte.hu/lukovszki/Publ/esa05.pdf]
- Ross Lippert, Clark Mobarry and Brian Walenz, A space-efficient construction of the Burrows Wheeler transform for genomic data, Journal of Computational Biology, 2005.
[http://www-math.mit.edu/~lippert/research/JCB-LMW-04-submission-5.pdf]
- Ross Lippert, Space-efficient whole genome comparisons with Burrows-Wheeler transforms, Journal of Computational Biology, 12(4), pp. 407-415, 2005.
[http://www-math.mit.edu/~lippert/research/JCB-L-05-submission-2.pdf]
- Dror Baron and Yoram Bresler, An O(N) Semi-Predictive Universal Encoder via the BWT, IEEE Transactions on Information Theory, 50(5), pp. 928-937, 2004.
[http://www2.ece.rice.edu/~drorb/pdf/mdl_final.pdf]
- Michael Dipperstein, Burrows-Wheeler Transform Discussion and Implementation, 2004.
[http://michael.dipperstein.com/bwt/]
- Peter Fenwick, Reflections on the Burrows Wheeler transform, The University of Auckland, Department of Computer Science, Technical Report 172, 2004.
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/TechRep172.pdf]
- Paolo Ferragina and Giovanni Manzini, Compression Boosting in Optimal Linear Time Using the Burrows-Wheeler Transform, Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 655-663, 2004.
[http://citeseer.ist.psu.edu/ferragina04compression.html]
[http://www.mfn.unipmn.it/~manzini/papers/soda04.pdf]
- Luca Foschini, Roberto Grossi, Ankur Gupta and Jeffrey Vitter, Fast Compression with a Static Model in High-Order Entropy, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 62-71, 2004.
[http://sssupa.sssup.it/~foschini/files/wzip-final.pdf]
[http://www.di.unipi.it/~grossi/PAPERS/dcc04.pdf]
[http://www.cs.duke.edu/~jsv/Papers/FGGV04.fast.pdf]
- Juha Karkkainen, Fast BWT in small space by blockwise suffix sorting, Proceedings DIMACS Working Group on The Burrows-Wheeler Transform: Ten Years Later, pp. 12-13, 2004.
[http://www.cs.helsinki.fi/juha.karkkainen/publications/bwt04.pdf]
[http://dimacs.rutgers.edu/Workshops/BWT/karkkainen.pdf]
- Jurgen Abel, Improvements to the Burrows-Wheeler Compression Algorithm: After BWT Stages, 2003.
[http://citeseer.ist.psu.edu/abel03improvements.html]
[http://www.data-compression.info/JuergenAbel/Preprints/Preprint_After_BWT_Stages.pdf]
- Richard Bird and Shin-cheng Mu, Inverting the Burrows-Wheeler Transform, Journal of Functional Programming Special Issue on Functional Pearls, 2003.
[http://citeseer.ist.psu.edu/bird01inverting.html]
[http://www.ipl.t.u-tokyo.ac.jp/~scm/pub/bwtJFP.ps.gz]
- Sebastian Deorowicz, Universal lossless data compression algorithms, PhD thesis, Silesian University of Technology, 2003.
[http://sun.iinf.polsl.gliwice.pl/~sdeor/pub/deo03.ps.gz]
[http://sun.iinf.polsl.gliwice.pl/~sdeor/pub/deo03.pdf]
- Peter Fenwick, Mark Titchener and Michelle Lorenz, Burrows Wheeler Alternatives to Move to Front, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 428-, 2003.
[http://citeseer.ist.psu.edu/563772.html]
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/DCC2003.ps]
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/DCC2003.pdf]
- Sebastian Deorowicz, Second step algorithms in the Burrows-Wheeler compression algorithm, Software-Practice and Experience, 32(2), pp. 99-111, 2002.
[http://citeseer.ist.psu.edu/deorowicz01second.html]
[http://sun.iinf.polsl.gliwice.pl/~sdeor/pub/deo01.ps.gz]
[http://sun.iinf.polsl.gliwice.pl/~sdeor/pub/deo01.pdf]
- Michelle Effros, Karthik Visweswariah, Sanjeev Kulkarni and Sergio Verdu, Universal Lossless Source Coding With the Burrows Wheeler Transform, IEEE Transactions on Information Theory, 48(5), pp. 1061-1081, 2002.
[http://citeseer.ist.psu.edu/effros02universal.html]
[http://www.princeton.edu/~kulkarni/Papers/Journals/j2002_evkv_transit.pdf]
- R. Yugo Kartono Isal, Alistair Moffat and Alwin C. H. Ngai, Enhanced Word-Based Block-Sorting Text Compression, Proceedings of the 25th Australasian Computer Science Conference, Melbourne, pp. 129-138, 2002.
[http://citeseer.ist.psu.edu/535800.html]
[http://crpit.com/confpapers/CRPITV4Isal.pdf]
- Giovanni Manzini, An Analysis of the Burrows-Wheeler Transform, Journal of the ACM, 48(3), pp. 407-430, 2001.
[http://citeseer.ist.psu.edu/manzini01analysis.html]
[http://www.mfn.unipmn.it/~manzini/papers/bwjacm2.pdf]
- Julian Seward, Space-time tradeoffs in the Inverse B-W Transform, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 439-448, 2001.
[http://citeseer.ist.psu.edu/381988.html]
- Anthony Wirth, Symbol-driven compression of Burrows Wheeler transformed text, Masters thesis, The University of Melbourne, 2001.
[http://www.cs.mu.oz.au/~awirth/pubs/awirthMSC.pdf]
- Bernhard Balkenhol and Stefan Kurtz, Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice, IEEE Transactions on Computers, 49(10), pp. 1043-1053, 2000.
[http://citeseer.ist.psu.edu/balkenhol00universal.html]
[http://www.mathematik.uni-bielefeld.de/ahlswede/pub/balkenhol/107476-1.ps.gz]
[http://www.techfak.uni-bielefeld.de/~kurtz/PS/balkenholkurtz.ps.gz]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/BalKur2000.pdf]
- Dror Baron and Yoram Bresler, Tree Source Identification with the Burrows Wheeler Transform, Proceedings of the 34th Annual Conference on Information Sciences and Systems, Princeton New Jersey, FA1-10-FA1-15, 2000.
[http://citeseer.ist.psu.edu/baron00tree.html]
[http://www2.ece.rice.edu/~drorb/ps/ciss_sub2.ps]
[http://www2.ece.rice.edu/~drorb/pdf/ciss_sub2.pdf]
- Sebastian Deorowicz, Improvements to Burrows-Wheeler Compression Algorithm, Software-Practice and Experience, 30(13), pp. 1465-1483, 2000.
[http://citeseer.ist.psu.edu/deorowicz00improvement.html]
[http://sun.iinf.polsl.gliwice.pl/~sdeor/pub/deo00.ps.gz]
- Stefan Kurtz and Bernhard Balkenhol, Space Efficient Linear Time Computation of the Burrows and Wheeler-Transformation, Numbers, Information and complexity, pp. 375-383, 2000.
[http://citeseer.ist.psu.edu/kurtz99space.html]
[http://www.mathematik.uni-bielefeld.de/ahlswede/pub/balkenhol/ahlssymp.ps.gz]
[http://www.techfak.uni-bielefeld.de/~kurtz/PS/kurtzbalkenhol.ps.gz]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/KurBal2000.pdf]
- Kunihiko Sadakane, Unifying Text Search And Compression Suffix Sorting, Block Sorting and Suffix Arrays, PhD thesis, University of Tokyo, 2000.
[http://citeseer.ist.psu.edu/sadakane00unifying.html]
- Bernhard Balkenhol, Stefan Kurtz and Yuri Shtarkov, Modifications of the Burrows and Wheeler Data Compression Algorithm, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 188-197, 1999.
[http://citeseer.ist.psu.edu/balkenhol99modifications.html]
[http://www.mathematik.uni-bielefeld.de/ahlswede/pub/balkenhol/dcc99.ps.gz]
[http://www.techfak.uni-bielefeld.de/~kurtz/PS/balkenhol_BurrowsWheelerDcc99.ps.gz]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/BalKurSht1999.pdf]
- Bernhard Balkenhol and Yuri Shtarkov, One attempt of a compression algorithm using the BWT, Preprint 99-133, SFB343: Discrete Structures in Mathematics, Falculty of Mathematics, University of Bielefeld, 1999.
[http://citeseer.ist.psu.edu/balkenhol99one.html]
[http://www.mathematik.uni-bielefeld.de/sfb343/preprints/pr99133.ps.gz]
- Arturo Campos, Burrows and Wheeler Transformation, 1999.
[http://www.arturocampos.com/ac_bwt.html]
[http://www.arturocampos.com/ac_bwt_html.zip]
- Giovanni Manzini, The Burrows-Wheeler Transform: Theory and Practice, Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, Szklarska Poreba, Poland, LNCS 1672, Springer-Verlag, pp. 34-47, 1999.
[http://citeseer.ist.psu.edu/manzini99burrowswheeler.html]
[http://www.mfn.unipmn.it/~manzini/papers/mfcs99x.ps.gz]
[http://www.mfn.unipmn.it/~manzini/papers/mfcs99x.pdf]
- Bernhard Balkenhol and Stefan Kurtz, Universal Data Compression Based on the Burrows and Wheeler-Transformation: Theory and Practice, Preprint 98-069, SFB343: Discrete Structures in Mathematics, Falculty of Mathematics, University of Bielefeld, 1998.
[http://citeseer.ist.psu.edu/balkenhol98universal.html]
[http://www.mathematik.uni-bielefeld.de/sfb343/preprints/pr98069.ps.gz]
- Brenton Chapin and Stephen Tate, Higher Compression from the Burrows-Wheeler Transform by Modified Sorting, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 532-, 1998.
[http://citeseer.ist.psu.edu/chapin98higher.html]
[http://www.cs.unt.edu/~srt/papers/bwtsort.ps]
[http://www.cs.unt.edu/~srt/papers/bwtsort.pdf]
- Ziya Arnavut and Spyros Magliveras, Block Sorting and Compression, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 181-190, 1997.
[http://citeseer.ist.psu.edu/arnavut97block.html]
- Ziya Arnavut and Spyros Magliveras, Lexical Permutation Sorting Algorithm, The Computer Journal, 40(5), pp. 292-295, 1997.
[http://citeseer.ist.psu.edu/arnavut97lexical.html]
- Michael Schindler, A Fast Block-sorting Algorithm for lossless Data Compression, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 469-, 1997.
[http://citeseer.ist.psu.edu/schindler96fast.html]
[http://www.compressconsult.com/st/dcc97eab.ps.gz]
- Peter Fenwick, Block Sorting Text Compression Final Report, The University of Auckland, Department of Computer Science, Technical Report 130, 1996.
[http://citeseer.ist.psu.edu/fenwick96block.html]
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/TechRep130.ps]
- Peter Fenwick, Block Sorting Text Compression, Proceedings of the 19th Australasian Computer Science Conference, Melbourne, Australia, 1996.
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/ACSC96paper.ps]
- Mark Nelson, Data Compression with the Burrows-Wheeler Transform, Dr. Dobb's Journal, 1996.
[http://www.dogma.net/markn/articles/bwt/bwt.htm]
- Peter Fenwick, Improvements to the Block Sorting Text Compression Algorithm, The University of Auckland, Department of Computer Science, Technical Report 120, 1995.
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/TechRep120.ps]
- Peter Fenwick, Experiments with a Block Sorting Text Compression Algorithm, The University of Auckland, Department of Computer Science, Technical Report 111, 1995.
[http://citeseer.ist.psu.edu/fenwick95experiments.html]
[ftp://ftp.cs.auckland.ac.nz/pub/staff/peter-f/TechRep111.ps]
- Michael Burrows and David Wheeler, A Block-Sorting Lossless Data Compression Algorithm, Digital Systems Research Center, SRC Research Report 124, Palo Alto, California, 1994.
[http://citeseer.ist.psu.edu/76182.html]
[ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-124.ps.gz]
[ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-124.pdf]
- Michael Maniscalco, The M03 algorithm.
[http://www.michael-maniscalco.com/m03.pdf]
- Wikipedia, Burrows-Wheeler transform.
[http://en.wikipedia.org/wiki/Burrows-Wheeler_transform]
Source Code
日本語の資料