6 ms·
The unintuitive part of BWT to me was always the reverse operation, which was the only thing the post didn't give intuition for :-)
by foobarian 1y ago
The unintuitive part of BWT to me was always the reverse operation, which was the only thing the post didn't give intuition for :-)
- raboukhalil 1y agoGood point, thanks! I'll add a subsection about the intuition for that.
- raboukhalil 1y agoI just added a section about the intuition behind the decoding: https://sandbox.bio/concepts/bwt#intuition-decoding https://sandbox.bio/concepts/bwt#intuition-decoding , hope it helps!
- foobarian 1y agoThank you! I think the circular property of that matrix is the key.
- hinkley 1y agoMost BWT descriptions: now draw the rest of the owl. Once upon a time I found one that did the entire round trip, I neglected to bookmark it. So when I eventually forgot how it worked, or wanted to show others, I was stuck. Never did find it.
- raboukhalil 1y agoI added more details about how the decoding works here: https://sandbox.bio/concepts/bwt#intuition-decoding https://sandbox.bio/concepts/bwt#intuition-decoding , I'd love to hear if that is more clear now
- deleted 1y ago[deleted]
- SimplyUnknown 1y agoI'm still not sure I get it. I think it is 1. Put the BWT string in the right-most empty column 2. Sort the rows of the matrix such that the strings read along the columns of the matrix are in lexicographical order starting from the top-row???? 3. Repeat step 1 and 2 until matrix is full 4. Extract the row of the matrix that has the end-delimiter in the final column It's the "sort matrix" step that seems under-explained to me.
- foobarian 1y agoI think what did it for me is to recognize that the last column has characters that, for each row, come before the characters in the first column (since they are rotations). So we can view the last column as coming "before" the first one. 1. We sorted the first column to get the BWT column. Thereby we created the structure where the BWT column comes before the sorted column. 2. Therefore if we insert the BWT column before a sorted column, the order of row elements is preserved 3. If we now sort again, the order of characters across individual rows is again preserved 4. Going to step 2 again preserves row order 5. Once all columns are populated, therefore all rows are in the correct original order. And thanks to the end marker we can get the original string from any row.
- kragen 1y agoThe algorithm given in this page for the reverse transform is not usably efficient; the algorithm given in the original paper is, and I illustrated it in my explorable explanation of it linked in my top-level comment here. It was a pretty surprising insight!
- krackers 1y agoThis always seemed magical to me too, but Gemini recently gave me an explanation that clicked. The seemingly magical part is that it seems like you "lose" information during the transformation. After all if I give you the sorted string, it's not recoverable. But the key is that the the first and last columns of the BWT matrix end up being the lookup table, from any character to the preceding character. And of course given the BWT encoded string, you can get back the sorted string which is the first column. And with this info of which character precedes which character, it shouldn't be too magical that you can work backwards to reconstruct the original string. Still, the really clever part is that the BWT encoded string embeds the decoding key directly into the character and positional information. And it just so happens that the way it does this captures character pair dependencies in a way that makes it a good preprocessor for "symbol at a time" encoders. https://news.ycombinator.com/item?id=35738839 https://news.ycombinator.com/item?id=35738839 has a nice pithy way of phrasing it >It sorts letters in a text by their [surrounding] context, so that letters with similar context appear close to each other. In a strange vaguely DFT-like way, it switches long-distance and short-distance patterns around. The result is, in a typical text, long runs of the same letter, which can be easily compressed.
- foobarian 1y agoYes, agreed. Presumably if you just compressed the sorted string it would compress even better, though not reversibly. So compressing the preceding column (preceding since rows are rotations) seems the next best thing