The BWT based FM-index is one of my favorite data structures. It's used frequently for DNA mapping, where the 4 letter alphabet can be encoded in two bits and the occurrence function can use clever caching, bit bashing and the pop count function to get nice performance.
BWT is one of those computer things that just seem like pure magic