Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-24T19:33:40.499Z Has data issue: false hasContentIssue false

FUNCTIONAL PEARL Inverting the Burrows–Wheeler transform

Published online by Cambridge University Press:  27 October 2004

RICHARD S. BIRD
Affiliation:
Programming Research Group, Oxford University, Wolfson Building, Parks Road, Oxford OX1 3QD, UK (email: richard.bird@comlab.ox.ac.uk)
SHIN-CHENG MU
Affiliation:
Programming Research Group, Oxford University, Wolfson Building, Parks Road, Oxford OX1 3QD, UK (email: richard.bird@comlab.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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
Copyright
© 2004 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.