Search code examples
algorithmburrows-wheeler-transform

Burrows-Wheeler Transform (BWT) - Stored Data

After using BWT, which set of data do we need in the encoded data? Do we need to encode (or export) the Suffix Array?

Input:

stackoverflow

BWT Output:

wtavrcfkle$soo

Suffix Array:

13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12

Solution

  • suffix array is only needed to compute bwt transform, after transform done it can be dropped away.

    BWT("stackoverflow")="wtavrcfkle$soo"

UNBWT("wtavrcfkle$soo")="stackoverflow"

    You can also restore the suffix array from transformed output if you like:)