Burrows-Wheeler Transform, or BWT, is a text indexing algorithm, which is used in data compression applications. 
How it works:
build an n by n matrix BWM containing all the cyclic rotations of your text t, which has length | t | = n, such that each row of BWM contains one rotation of t, and each cell of BWM contains a letter of t
sort the rows lexicographically
the rightmost column of BWM is BWT
For example , the following string T
would give the following matrix BWM(T)
and if we sort the rows lexicographically, we end up with
which gives us BWT(T) in the last column, which is
Once of the coolest things about BWT is that you can restore the original string from only its BWT!
You may also notice that BWT has a close link to the suffix array, but is much smaller in size. Algorithms are always being developed for searching indexes like BWT, for example, the FM-Index . Check out my next blog post to learn about the FM-Index!
1. Burrows, Michael, and David J. Wheeler. "A block-sorting lossless data compression algorithm." (1994).
3. Ferragina, Paolo, and Giovanni Manzini. "Opportunistic data structures with applications." Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on. IEEE, 2000.