Run-Length FM-Index - koki

FM-index は検索対象のテキストから予め索引を構築しておくことで，テキストに含まれる任意のパターン文字列の個数を数えるクエリ$ \mathrm{count} を，テキストのサイズに依らず高速に実行できるデータ構造です．加えて，suffix array や inverse suffix array の一部を追加で保持しておくことで，パターンの位置の列挙 $ \mathrm{locate}やテキストの復元 $ \mathrm{extract}といったクエリを高速に実行することができます（自己索引）． 主要な応用としてゲノム解析（例：HISAT2）などが挙げられます．身近なところでは，arXiv をコーパスとした高速な英文コロケーション検索を提供する Hyper Collocation でも用いられています（解説）． FM-Index に関しては，高速文字列解析の世界 や 簡潔データ構造