Burrows-Wheeler
Transform (1994)
nA pre-processing step
for data compression
nInvolves sorting of all
rotations of the block of data
to be compressed
nRationale: Compressed string transforms better
nWorst case complexity of N2log(N), where N = size of block to be sorted
nCan be improved to
N(logN)2 (Sadakane ’98)