FM-index
The name stands for Full-text index in Minute space (by
https://en.wikipedia.org/wiki/FM-index
)
FM-indexは現在もっとも高速で現実的な圧縮全文索引である (
#高速文字列解析の世界
p.110)
BWTはSuffixArrayとほぼ同じなのでBWTで全文検索できちゃうよね。BWTはウェーブレット木があるから超効率よくね。ウェーブレット木は完備辞書があるから超効率よくね。ってことでできたのが超効率のいいSuffixArrayだ、よしこれをFM-Indexと名付けよう！っていうような話が書いてあるのが 第7章（
#高速文字列解析の世界
）。
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
BWT
の
LP-mapping
の性質を利用し
全文検索
を行う