Article contents
FUNCTIONAL PEARL Inverting the Burrows–Wheeler transform
Published online by Cambridge University Press: 27 October 2004
Abstract
The Burrows–Wheeler Transform is a string-to-string transform which, when used as a preprocessing phase in compression, significantly enhances the compression rate. However, it often puzzles people how the inverse transform is carried out. In this pearl we to exploit simple equational reasoning to derive the inverse of the Burrows–Wheeler transform from its specification. We also outline how to derive the inverse of two more general versions of the transform, one proposed by Schindler and the other by Chapin and Tate.
- Type
- Functional pearls
- Information
- Copyright
- © 2004 Cambridge University Press
- 5
- Cited by
Discussions
No Discussions have been published for this article.