News for hackers. Stuff that matters.
Re:The Burrows-Wheeler Transform by foobarian on Thursday October 09, 2025 @05:39PM (#45533391)
The unintuitive part of BWT to me was always the reverse operation, which was the only thing the post didn't give intuition for :-)
Re:The Burrows-Wheeler Transform by raboukhalil on Thursday October 09, 2025 @06:31PM (#45533735)
Good point, thanks! I'll add a subsection about the intuition for that.
Re:The Burrows-Wheeler Transform by raboukhalil on Thursday October 09, 2025 @10:57PM (#45535020)
I just added a section about the intuition behind the decoding: https://sandbox.bio/concepts/bwt#intuition-decoding , hope it helps!
Re:The Burrows-Wheeler Transform by foobarian on Friday October 10, 2025 @10:07AM (#45539263)
Thank you! I think the circular property of that matrix is the key.
Re:The Burrows-Wheeler Transform by hinkley on Thursday October 09, 2025 @08:28PM (#45534392)
Most 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.

Re:The Burrows-Wheeler Transform by raboukhalil on Thursday October 09, 2025 @10:59PM (#45535029)
I added more details about how the decoding works here: https://sandbox.bio/concepts/bwt#intuition-decoding , I'd love to hear if that is more clear now
Re:The Burrows-Wheeler Transform by SimplyUnknown on Friday October 10, 2025 @04:27AM (#45536528)
I'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.

Re:The Burrows-Wheeler Transform by foobarian on Friday October 10, 2025 @09:52AM (#45539067)
I 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.

Re:The Burrows-Wheeler Transform by kragen on Friday October 10, 2025 @04:06PM (#45543196)
The 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!
Re:The Burrows-Wheeler Transform by krackers on Monday October 13, 2025 @08:40PM (#45574941)
This 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 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.

Re:The Burrows-Wheeler Transform by foobarian on Tuesday October 14, 2025 @09:09AM (#45579592)
Yes, 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