Why use last column of Burrows-Wheeler-Transform

Question

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?

Answer 1

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.