Suffix Arrays and the BWT

The BWT is Reversible

The first and last columns carry enough information to reconstruct the original string.

highlighted = computed this step

First and last columns define the links

Sort the BWT characters to get the first column. Matching repeated letters by rank gives the LF links that walk back through the original string.

first column=sort⁡(last column)\text{first column}=\operatorname{sort}(\text{last column})
First and last columnsThe first column is the sorted BWT characters; the last column is the BWT.FirstLast$AACATAGCAG$TTTA

The transform is lossless

Following those links reconstructs GATTACA. Reversibility is why the BWT is a lossless transform, not a hash.

inverseBWT⁡(ACTGA$TA)=GATTACA\operatorname{inverseBWT}(\text{ACTGA\$TA})=\text{GATTACA}
First and last columnsThe first column is the sorted BWT characters; the last column is the BWT.FirstLast$AACATAGCAG$TTTA