### Burrows-Wheeler Transform (BWT): Provenance

Given string S[1..n], its Burrows-Wheeler transform T[1..n] is defined as follows. Consider the set of cyclic suffixes of S, ie., S[i, i+1, ..., n, 1, 2,...,i-1] for all i. Sort these strings lexicographically and output the last character in the ith string in this sorted order as T[i], for each i. Both S and T are of same size, but T has great properties:

Btw, BWT has an intriguing provenance. Wheeler was an eccentric creator who intuited many algorithms, results and ideas. Burrows, who narrates this story (see page 199 here) in a TCS journal issue is much too modest and undersells his own considerable contribution in developing the original ideas into concrete, efficient algorithms and applications. Together they have produced a creative piece of work.

ps: I have been a voyeur. I liked BWT since the first time I saw it in 1994, have used it, maybe even extended it, but I still approach it as an outsider, curious, willing it hold it like a crystal between my fingers, rotate it, examine it, but eventually put it back on the table.

- T can be compressed very nicely by standard compressors, say run-length compressor,
- S can be recovered from T (and the index j where S[1..n] ended up in the sort order) in nearly linear time.

Btw, BWT has an intriguing provenance. Wheeler was an eccentric creator who intuited many algorithms, results and ideas. Burrows, who narrates this story (see page 199 here) in a TCS journal issue is much too modest and undersells his own considerable contribution in developing the original ideas into concrete, efficient algorithms and applications. Together they have produced a creative piece of work.

ps: I have been a voyeur. I liked BWT since the first time I saw it in 1994, have used it, maybe even extended it, but I still approach it as an outsider, curious, willing it hold it like a crystal between my fingers, rotate it, examine it, but eventually put it back on the table.

## 0 Comments:

Post a Comment

<< Home