2 ms·
Unless I missed it, this page doesn't actually contain a description of how to invert the BWT. Fortunately, Wikipedia has a fairly decent description: The inve
by barrkel 17y ago
Unless I missed it, this page doesn't actually contain a description of how to invert the BWT. Fortunately, Wikipedia has a fairly decent description:
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 to get the first column. Then, the first and last columns 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.