FM-index

Invented by Paolo Ferragina, Giovanni Manzini (2000); the transform: Michael Burrows, David Wheeler (1994)
Idea:
  • a full-text index that counts and locates the occurrences of a pattern in a text, and takes about as much space as the compressed text — the text itself need not be kept
Advantages:
  • the whole index, the text included, usually takes less space than the text alone — close to the text's compressed length

References

  • P. Ferragina, G. Manzini. Opportunistic data structures with applications. Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), 390-398, 2000.
  • M. Burrows, D.J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
  • P. Ferragina, G. Manzini. Indexing compressed text. Journal of the ACM, 52(4):552-581, 2005.
  • G. Navarro, V. Mäkinen. Compressed full-text indexes. ACM Computing Surveys, 39(1):2, 2007.