Note: These tutorials are incomplete. More complete versions are being made available for our members. Sign up for free.
Thinking Conceptually about BWT
In this section, we will discuss various observations that will help you better understand the basic concepts behind BWT.
Observation 1. Connection between BWT and Suffix Array. BWT connects search and compression.
To properly understand the role of BWT in mapping, one always needs to remember that BWT is the last column of suffix array, or the column before the first column after sorting the rotated strings to build suffix array. BWT and suffix arrays are intimately connected, and the role of suffix arrays in search is easily established.
Observation 2. Next letters are sorted.
Observation 3. Single representation of each letter.
Let us say the word we like to build BWT from has each letter only one time. Is it possible to form the BWT by merely looking at the text? Yes, it is, because the BWT contains the letters prior to the actual letters in order.
Observation 4. LF Property Conceptually.
Observation 5. Computation of BWT - conceptually.
