It also turns out Mike Burrows, the first author of the paper ("the 'b' in 'bzip', I was told), sits about 20 feet from me. Tonight I introduced myself and we chatted about it for a bit. He added some amusing anecdotes. Such as:
The paper claims it has performance comparable to Lempel-Ziv while achieving better compression. This was true at the time, but Mike said that the final deshuffling step has poor cache performance so as computers have increased in speed and cache dependency, this algorithm has fallen behind gzip. At a recent compression conference (celebrating the 10th anniversary of the publishing of the paper, though he pointed it was actually discovered in 1978 -- the number they have in the paper is wrong) he proposed some methods to speed it up by a factor of two. But the compression folks were only interested in O() improvements, and since somebody had already proved it was O(n) (with a large constant) nobody was interested.
Mike seems like a generally hax0ry fellow, recently getting credit for writing some tight assembly for an upcoming Google project.
[Obligatory programming-language-related footnote: the author of the bzip2 library works on ghc, the Haskell compiler.]
