The article's method is nice, it allows you to decompress portions of the file. I thought this would be about the FM index. The FM index allows you to search wh

The article's method is nice, it allows you to decompress portions of the file. I thought this would be about the FM index. The FM index allows you to search what is essentially a bzip'd archive for a substring far more efficiently than you would be able to search an uncompressed string for a substring. Pretty mind blowing if you think about it. It works because the Burrows-Wheeler transform which is used in compression is closely related to the suffix array, which is a data structure used as a substring index. By adding a small amount of additional metadata to the compressed Burrows-Wheeler transformed string you can search for any substring. Its practical performance is slower than a suffix array, but the memory usage can be 100x lower.