We can invert the Burrows-Wheeler with this method:

The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this information, you can easily reconstruct the first column. The last column tells you all the characters in the text, so just sort these characters alphabetically to get the first column. Then, the first and last columns (of each row) together give you all pairs of successive characters in the document, where pairs are taken cyclically so that the last and first character form a pair. Sorting the list of pairs gives the first and second columns. Continuing in this manner, you can reconstruct the entire list. Then, the row with the "end of file" character at the end is the original text.

From: https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

I don't understand why this method works.

  • $\begingroup$ Find a source which contains a proof. $\endgroup$ – Yuval Filmus Nov 29 '19 at 22:39
  • $\begingroup$ A source that I founded uses LF mapping which I understad. I don't understand the method in wikipedia. $\endgroup$ – asv Nov 30 '19 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.