[bugfix-66]

Explained here with Go code:

https://bugfix-66.com/7f0f425d3eee8def16e1102d054fd45394d027...

Wikipedia gives an impractical, inefficient account of the algorithm. It's almost comically bad.

But the BWT has an efficient inverse transform with very short, simple code, as seen above. This is the classic linked list algorithm.

The forward transform is also simple if done right. See the Go code here:

https://bugfix-66.com/72949624ebbb28b3d0ce5d700970a8857d354b...

Together, that's full code for industrial-strength forward and inverse BWT. All that's missing is some method of avoiding degeneracy in the forward transform string sort (e.g., noising long runs in the input or a suffix array).

[brilee]

It's frustrating that your link to an "explanation" is an intentionally buggy implementation of the algorithm :(

I understand the point of the debugging game, but in this context, a link to the solutions page would be more helpful....

[bugfix-66]

Replace

  at = root

with

  at = next[root]

and you're done. Once you understand the forward transform, you understand that root is the LAST byte and next[root] is the FIRST byte.

All the fixes in BUGFIX-66 are trivial if you understand what the code is doing, that's part of the game concept. Also, if you submit broken code, it gives you a useful hint to direct your attention to the bug.

Similarly, the fix for the forward transform is to add

  i1, i2 = x[i1], x[i2]

at the top of the less() function.

[ignoramous]

> Wikipedia gives an impractical, inefficient account of the algorithm. It's almost comically bad.

I encourage you to edit and fix it.

[metadat]

I love your site! Hope you don't mind that I sent you an email.

It's a fantastic example of minimal yet fully functional!

[bugfix-66]

Thanks. I just recently started building it.

Understanding small, elegant algorithms (enough to make tiny fixes) is something I consider fun. Hopefully it's fun for others.

Imagine the book Hacker's Delight, but turned into a simple debugging game. That's the concept.