[gww]

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.