4

The Burrows-Wheeler-Transform takes a string with length n, creates a matrix with n rows by shifting this string one position to the left for each row. Then the rows are sorted by the first column in lexicographical order. Then the last column will be submitted.

Why taking the last column? On Wikipedia there is an example with the string "^BANANA|". After sorting the first column is "AAABNN^|" and the last column is "BNN^AA|A". Using run length encoding it would be better to use the first column because of "AAA". So where are the advantages in taking the last column?

Improve this question

2 Answers 2

Reset to default
4

The key property of the Burrows-Wheeler-Transform that makes it useful is that it's reversible, without storing any metadata about what the transform did.

If you simply pick "AAABNN^|" because it compresses better than the other columns, instead of using a consistent rule like "always pick the last column", then when it came time to reverse the process, you'd have no way of knowing whether the original string was "^BANANA|" or "^AAABNN|" or "^BAANAN|" or something entirely different. In fact, if all you want to do is rearrange the letters for maximum compressability, simply sorting the letters is much more effective solution. But then you're effectively creating an irreversible compression algorithm, and compression is generally considered quite useless if there's no way to uncompress the data later.

Improve this answer
1
  • 1
    What is preventing you from picking a consistent rule of "always pick the first column"? What is special about the last column? Commented Oct 25, 2023 at 15:24
2

Here’s a naïve reconstruction method (without LF-mapping):

0 - The last column L contains all the characters of the string.

1 - Sorting it gives the first column 1.

2 - Pairing the last and first columns as [L, 1] gives all adjacent character pairs of the original string.

3 - Sorting [L, 1] produces the matrix [1, 2], giving the second column.

4 - Constructing [L, 1, 2] gives triples; sorting recovers [1, 2, 3], giving the third column.

5 - Repeating this process eventually reconstructs the full matrix.

When the full matrix is reconstructed, the row with the start/end marker in the correct position is the original string. If you only had the first column, you wouldn’t have any information about adjacency of characters to begin the reconstruction.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.