Functional Pearl: Inverting the Burrows-Wheeler Transform
Functional Pearl: Inverting the Burrows-Wheeler Transform
Richard Bird and Shin-Cheng Mu.
Abstract:
The objective of this pearl is to derive the inverse of the
Burrows-Wheeler transform from its specification, using simple
equational reasoning. In fact, we derive the inverse of a more general
version of the transform, proposed by Schindler.