Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\BWT{\mathit{BW}} \def\endmarker{\sharp} $

For the example of $x=\sa{banana}\endmarker$ we get $\BWT(x)=\sa{annb}\endmarker\sa{aa}$:

$\BWT(x)$

$\sa{a}$ $\endmarker$

$\sa{n}$ $\sa{a}$ $\endmarker$

$\sa{n}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\endmarker$

$\sa{b}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\endmarker$

$\endmarker$ $\sa{b}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\endmarker$

$\sa{a}$ $\sa{n}$ $\sa{a}$ $\endmarker$

$\sa{a}$ $\sa{n}$ $\sa{a}$ $\sa{n}$ $\sa{a}$ $\endmarker$

Problem 96: In-place BW Transform

The Burrows-Wheeler transform ($\BWT$) of a word can be computed in linear time, over a linear-sortable alphabet, using linear space. This is achieved via a method to sort the suffixes or conjugates of the word, which requires linear extra space in addition to the input.

The problem shows how the input word is changed to its transform with constant additional memory space but with a slower computation.

Let $x$ be a fixed word of length $n$ whose last letter is the end-marker $\endmarker$, smaller than all other letters. Sorting the conjugates of $x$ to get $\BWT(x)$ then amounts to sorting its suffixes. The transform is composed of letters preceding suffixes (circularly for the end-marker).

Design an in-place algorithm to compute the Burrows-Wheeler transform of an end-marked word of length $n$ in time $O(n^2)$ using only constant extra space.

References

D. Adjeroh, T. Bell, and A. Mukherjee. The Burrows-Wheeler Transform. Springer, 2008.

M. Crochemore, R. Grossi, J. Kärkkäinen, and G. M. Landau. Computing the Burrows-Wheeler transform in place and in small space. J. Discrete Algorithms, 32:44-52, 2015.

$\BWT(x)$
$\sa{a}$	$\endmarker$
$\sa{n}$	$\sa{a}$	$\endmarker$
$\sa{n}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\endmarker$
$\sa{b}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\endmarker$
$\endmarker$	$\sa{b}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\endmarker$
$\sa{a}$	$\sa{n}$	$\sa{a}$	$\endmarker$
$\sa{a}$	$\sa{n}$	$\sa{a}$	$\sa{n}$	$\sa{a}$	$\endmarker$

125 Problems in Text Algorithms

Example

Problem 96: In-place BW Transform

References