Suffix Arrays and the BWT

The Burrows-Wheeler Transform

The BWT is the last column of sorted cyclic rotations.

highlighted = computed this step

Sort all cyclic rotations

Write every cyclic rotation of the sentinel-terminated string, then sort those rotations. The first sorted rotation is $GATTACA.

first rotation=$GATTACA\text{first rotation}=\text{\$GATTACA}
Sorted rotationsThe BWT is the last column of the sorted rotations table.Sorted rotationLast$GATTACAAA$GATTACCACA$GATTTATTACA$GGCA$GATTAAGATTACA$$TACA$GATTTTACA$GAA

Take the last column

The Burrows-Wheeler Transform is the last column of that sorted rotation table. For the worked string, the computed BWT is ACTGA$TA.

BWT=ACTGA$TA\text{BWT}=\text{ACTGA\$TA}
Sorted rotationsThe BWT is the last column of the sorted rotations table.Sorted rotationLast$GATTACAAA$GATTACCACA$GATTTATTACA$GGCA$GATTAAGATTACA$$TACA$GATTTTACA$GAA

The BWT groups similar contexts

The transform moves characters with similar right-contexts near one another. That grouping helps compression and also supports fast exact search.

sorted contexts⟶searchable last column\text{sorted contexts} \longrightarrow \text{searchable last column}
Sorted rotationsThe BWT is the last column of the sorted rotations table.Sorted rotationLast$GATTACAAA$GATTACCACA$GATTTATTACA$GGCA$GATTAAGATTACA$$TACA$GATTTTACA$GAA