-
an algorithm used to prepare data for use with data compression techniques such as bzip2. It permutes the order of characters in a string (S), sorting all the circular shifts of the text in lexicographic order, then extracting the last column and the index of the original string in the set of sorted permutations of S.
Some day when I have lots of free time to spare, I’ll spend a while getting my head around this deep magic, because it’s just amazing that this works.
(via John Regehr)
Tags: compression algorithms burrows-wheeler-transform bzip2 via:john-regehr magic text