Deriving the Burrows-Wheeler Transform from the Positional BWT
A teaching route that reaches the BWT and the FM-index by starting from the Positional BWT rather than the other way round. Positional search on a set of strings is built from a right-to-left radix sort, backward search replaces binary search once rank structures are added, prefix search is positional search at position zero, substring search is prefix search on the suffixes, and switching from suffixes to cyclic shifts makes every column of the PBWT identical - that single column being the BWT. Sampling diagonals rather than columns yields the standard suffix-array sample.
Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform
Travis Gagie (Dalhousie University), Giovanni Manzini (University of Pisa) and Marinella Sciortino (University of Palermo), arXiv 2208.09840v1, cs.DS, 21 August 2022, eight pages, no journal referenc…