Bug 13: Bungled Burrows-Wheeler Inverse Transform
- The inverse BWT takes as input a sequence of bytes. One of these bytes is distinguished as the root.
- The sorted ordering of these input bytes is summarized through an exclusive prefix sum of byte counts.
- The n input bytes are linked together into a circular list represented by a slice of n integers.
- The i'th occurrence of byte b in the input is linked-to from the i'th occurrence of byte b in the sorted input.
- Why? If two strings have the same first byte, their sorted order is determined by the bytes that follow.
- Therefore, rotating (moving the first byte to the end) both strings does not change their relative order.
- Traversing the linked list yields the original byte sequence (i.e., the input to the BWT).
Fix The Tiny Bug In This Go Code: