FM-index
FM-index (wikipedia) は全文検索を効率よく行うためのデータ構造．Ferragina と Manzini によって2000年に提案された． あらかじめテキストから索引を構築することで，操作
$ \mathrm{count}: 与えられたパターンがテキスト中に現れる回数を計算する
をパターンの長さ$ m，テキストのアルファベット数$ \sigmaとして$ O(m\log\sigma)時間で実行できる．
準備
実装の利便性から，添字は 0-based であるとする（リスト$ A の先頭要素は $ A[0] ）．
テキスト$ T を，要素数$ \sigma のアルファベット集合 $ \Sigma からなる文字列とし（$ T \in \Sigma^* ），その長さを $ n = |T| とする．各文字の間には順序が定まり，最小の文字を$ \$ とする．$ T の終端 $ T[n-1] は常に$ \$ であるとする．
code:mississippi.txt
0 1
index 012345678901
T = mississippi$
n = 12
Suffix Array
$ T の$ n 個の接尾辞 (suffix) の開始位置を，接尾辞の辞書順でソートした数列を接尾辞配列 (suffix array) という (wikipedia)． T = mississippi$ の接尾辞はmississippi$, ississippi$, ..., $ であり，接尾辞配列$ SA は[11, 10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] である．
最小の接尾辞は常に$なので，$ SA[0]= n - 1 が成り立つ．
L配列 と F配列
テキスト $ Tとその接尾辞配列 $ SAについて，長さ$ nの配列$ Lと$ Fを以下のように定める：
$ L[p] = \mathrm{if}\;SA[p]>0\;\mathrm{then}\;T[SA[p]-1]\;\mathrm{else}\; T[n-1]
$ F[p] = T[SA[p]]
$ Tの接尾辞の代わりに$ Tのすべての巡回を辞書順でソートし，それらの先頭文字および最後の文字をとって $ Fおよび$ L とすると考えるとわかりやすい（F = first, L = last）．
https://gyazo.com/2a158e1b34e49a2f5d202a6eaade8abc
ここで，$ L はテキスト$ Tの Burrows-Wheeler Transform そのものである．また各行における$ Lは同じ行の suffix の1つ前の文字であるから，以下の関係が成り立つ：
$ T[i] = F[SA^{-1}[i]] = L[SA^{-1}[i+1]].
（例）$ T = \mathrm{mississippi}\$ について，$ j = 8番目の文字は$ \mathrm p．
$ SA^{-1}[8] = 7,\quad SA^{-1}[8 + 1] = 6,\quad T[9] = F[7] = L[6] = \mathrm p
LF Mapping
L配列中の$ p 番目の文字$ L[p] がF配列のどこに現れるかを計算する関数，すなわち $ SA^{-1}[i+1] を $ SA^{-1}[i] に変換する関数を LF mapping と呼ぶ．
$ LF(p) = SA^{-1}[SA[p]-1]
（例）$ LF(6) = SA^{-1}[SA[6] - 1] = SA^{-1}[9 - 1] = 7
ここで，$ c = L[p] がわかっているとき，$ SA と$ SA^{-1} の代わりに$ L[0..p) に現れる文字$ cの個数を数える関数$ \mathrm{rank}_c(L, p)を使って LF mapping を以下のように計算できる．
$ LF(p) = \mathrm{rank}_c(L, p) + C[c], \quad c = L[p]
ここで$ C は， 各文字$ cについてテキスト$ T中の$ c未満の文字の出現回数を格納する配列である．
（例）$ LF(6) = \mathrm{rank}_{\mathrm p}(L, 6) + C[\mathrm p] = 1 + 6 = 7
inverse LF Mapping
F配列の$ p 番目の文字$ F[p] がL配列のどこに現れるかを計算する関数，すなわち $ SA^{-1}[i] を $ SA^{-1}[i+1] に変換する関数を inverse LF mapping または $ \psi関数 と呼ぶ．
$ \psi(p) = SA^{-1}[SA[p] + 1]
TODO: 例
ここで，$ c = F[p] がわかっているとき，$ SA と$ SA^{-1} の代わりに $ L[0..p] に現れる $ p + 1番目の$ cの位置を与える関数 $ \mathrm{select}_c(L, p)を使って inverse LF mapping を以下のように計算できる．
$ \psi(p) = \mathrm{select}_c(L, p - C[c]), \quad c = F[p]
TODO: 例
Counting patterns
code:count.rs
let mut s = 0;
let mut e = n;
for k in (0..n).rev() {
if s >= e {
break;
}
}
return e - s
TODO: なぜうまくいくか解説．
Locating patterns
count クエリによって，あるパターン$ P を接頭辞に持つテキストの接尾辞の開始位置が，$ SA 上に（連続して）保存されている区間$ [s, e) を計算できた．しかし，実用上はパターンのテキスト$ T における位置 ，すなわちそのパターンを接頭辞に持つテキストの接尾辞の開始位置$ SA[p]\ (s \leq p < e) が計算できるとよい．
ここで LF mapping の定義より$ SA[LF(p)] = SA[p] - 1 であるから，
$ SA[p] = SA[LF(p)] + 1 = SA[LF(LF(p))] + 2 = \cdots = SA[LF^k(p)] + k.
Extracting text
$ T[i] = L[SA^{-1}[i+1]]
$ SA^{-1}[i + 1] = \psi(SA^{-1}[i]) = \cdots = \psi^k(SA^{-1}[i - k + 1])
なので，$ SA^{-1}も$ SAと同様にサンプリングできる．さらに，
$ T[i - 1] = L[SA^{-1}[i]] = L[LF(SA^{-1}[i + 1])] = L[LF(p)],
$ T[i - l] = L[LF^l(SA^{-1}[i + 1])] = L[LF^l(p)].
よりテキスト$ T上の位置 $ iから逆順にテキストを効率よく復元できる．
一方で，
$ T[i] = F[SA^{-1}[i]]
でもあった．$ F の任意の位置の要素は$ C 上の2分探索によって復元できるから， $ q = SA^{-1}[i] が計算できれば $ T[i] を復元できる．さらに，
$ T[i + 1] = F[SA^{-1}[i + 1]] = F[\psi(SA^{-1}[i])] = F[\psi(q)],
$ T[i + r] = F[\psi^r(SA^{-1}[i])] = F[\psi^r(q)].
よりテキスト$ T上の位置 $ jから正順にテキストを効率よく復元できる．
P. Ferragina and G. Manzini. 2000. Opportunistic data structures with applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS '00), 390-. pdf (draft) 最初の論文
Paolo Ferragina and Giovanni Manzini. 2005. Indexing compressed text. J. ACM 52, 4 (July 2005), 552-581. (pdf)