🔍
FM-indexを用いた複数テキストの全文検索

2025/05/05に公開
FM-index は、文字列の全文検索を効率的に行うためのデータ構造（索引）です。あらかじめテキストのFM-indexを構築しておくことで、指定された検索パターンに関するクエリを高速に処理することができます。


クエリ
説明


\mathrm{count}
テキスト中のパターンの出現回数を数える

\mathrm{locate}
テキスト中のパターンの出現位置を計算する

特に、\mathrm{count}の計算はテキストの長さに依存せず、パターンの長さに応じて行うことができます。
FM-index は簡潔データ構造や Burrows-Wheeler 変換といった要素で構成されており、索引を圧縮した形で扱うことができます（圧縮全文索引）。また、索引自体が元のテキストの情報を保持しているので（自己索引）、検索結果のパターンに隣接するテキストを復元することもできます。
FM-index は単一テキストにおける検索機能を提供しますが、その自然な応用として複数テキストの集合に対する検索が挙げられます。 例えば、複数のファイルの中から特定のキーワードを含むファイルを列挙したい、といったことが往々にしてあります。本記事では、FM-indexを用いてこのような複数テキストの検索を実現する方法を紹介します。

 FM-index複数テキストにおける検索の話に入る前に、まずは単一テキストに対するFM-indexについておさらいします。
テキストTを、要素数\sigmaのアルファベット集合上の文字列とし、その長さをn = |T|とします。また、アルファベット集合のうち最小の文字を\text{\textdollar}とし、テキストの終端には常にこの終端記号が付加されているとします（T[n - 1]=\text\textdollar）。
!本記事では、文字列に対する添字アクセスを0-baseで表現します。

 FM-index の構築FM-index は以下の要素で構成されます。

T_\mathrm{BWT}：テキストTをBurrows-Wheeler変換した文字列。テキストの接尾辞配列から構築できます。

C：各アルファベットcについて、テキストTに含まれるcより小さい文字の出現回数を格納した配列。

SA：テキストTの接尾辞配列（suffix array）。\mathrm{locate}クエリの回答に必要です。サイズ削減のため、完全な接尾辞配列ではなく、等間隔にサンプルしたものを用いることができます。

 接尾辞配列（SA）テキストTの接尾辞配列（suffix array）は、Tのすべての接尾辞を辞書順に並べた際の、各接尾辞の開始位置を記録した配列です。例えば、T = \text{banana\textdollar}の場合、以下の表に示すように接尾辞配列は[6, 5, 3, 1, 0, 4, 2]となります。


接尾辞（辞書順）
開始位置


\text{\textdollar}
6

\text{a\textdollar}
5

\text{ana\textdollar}
3

\text{anana\textdollar}
1

\text{banana\textdollar}
0

\text{na\textdollar}
4

\text{nana\textdollar}
2

接尾辞配列は、SA-IS[1]などのアルゴリズムを用いることでO(n)時間で構築できます。

 Burrows-Wheeler 変換（T_\mathrm{BWT}）Burrows-Wheeler 変換は、テキストのすべての回転を辞書順に並べ、各回転の末尾の文字を順に抽出した文字列を得る変換です。例えば、T = \text{banana\textdollar}の回転は\text{banana\textdollar}, \text{anana\textdollar b}, \text{nana\textdollar ba}, \ldots, \text{\textdollar banana} ですが、これらを辞書順に並べた結果を以下に示します。
k  SA[k]  F     L
-----------------
0      6  $banana
1      5  a$banan
2      3  ana$ban
3      1  anana$b
4      0  banana$
5      4  na$bana
6      2  nana$ba
テキストTのBurrows-Wheeler変換T_\mathrm{BWT}は、回転の末尾の文字をとってT_\mathrm{BWT} = \text{annb\textdollar aa}です。
ここで、回転の順序は接尾辞配列の順序と同一です。表の行kは、接尾辞配列の値SA[k]に対応する接尾辞（およびその回転）を示しています。
表の先頭の列をF列、末尾の列をL列と呼びます。例ではF = \text{\textdollar aaabnn}、L = \text{annb\textdollar aa}となります。テキストTのBurrows-Wheeler変換T_\mathrm{BWT}は、このL列そのものです。これらの呼び方は以降も使用します。
Burrows-Wheeler変換されたテキストT_\mathrm{BWT}は、ウェーブレット木（wavelet tree）やウェーブレット行列（wavelet matrix）などのデータ構造を用いて、以下のクエリを高速に処理できるような形式で保存します。

\mathrm{rank}_c(T_\mathrm{BWT}, i)：T_\mathrm{BWT}[0, i)中の文字 c の出現回数を数える

\mathrm{select}_c(T_\mathrm{BWT}, i)：T_\mathrm{BWT}の中のi + 1 番目の c の出現位置を計算する

\mathrm{access}(T_\mathrm{BWT}, i)：T_\mathrm{BWT}[i]を求める
データのサイズや構築・クエリ効率は使用するウェーブレット木の実装によりますが、ウェーブレット行列を用いた場合の計算量は以下のようになります。
サイズ：O(n \log\sigma)
構築時間：O(n \log\sigma)

\mathrm{rank}, \mathrm{select}の計算時間：O(\log\sigma)

 文字の出現回数（C）配列Cには、各アルファベットcについて、テキストT中のcより小さい文字の総出現回数を格納します。例えば T = \text{banana\textdollar}の場合、C[\text\textdollar] = 0, C[\text a] = 1, C[\text b] = 4, C[\text n] = 5です。
実用上、Cは文字の数値表現を添字にした配列として保存するのが一般的です。このとき、CのサイズはO(\sigma\log n)になります。

 FM-index のクエリ例として、テキストT = \text{mississippi\textdollar}の回転表を以下に示します。
 k  SA[k]  F          L
-----------------------
 0     11  $mississippi
 1     10  i$mississipp
 2      7  ippi$mississ
 3      4  issippi$miss
 4      1  ississippi$m
 5      0  mississippi$
 6      9  pi$mississip
 7      8  ppi$mississi
 8      6  sippi$missis
 9      3  sissippi$mis
10      2  ssippi$missi
11      5  ssissippi$mi
FM-indexは、Burrows-Wheeler変換された文字列T_\mathrm{BWT} = \text{ipssm\textdollar pissii}（L列に等しい）、および配列C = \lbrace \text{\textdollar} \mapsto 0, \text{i} \mapsto 1, \text{m} \mapsto 5, \text{p} \mapsto 6, \text{s} \mapsto 8 \rbraceを保持しています。
重要な性質として、テキストに出現するパターンに対応する接尾辞、すなわちパターンで開始する接尾辞は、この表の中の連続する行に現れます。例えば、パターンP=\text{s}で始まる接頭辞は表の8行目から11行目、パターンP=\text{is}で始まる接尾辞は表の3行目から4行目、パターンP=\text{sis}で始まる接尾辞は表の9行目に現れます。したがって、テキスト中のパターンを検索するには、そのパターンに対応する接尾辞が現れる表中の行の範囲、すなわちSA上の範囲を特定すれば良いことが分かります。
パターンP'に対応するSA上の範囲が[s', e')であるとき、そのパターンに文字\text{c}を加えた新しいパターンP = cP'に対応するSA上の範囲を、T_\mathrm{BWT}とCを用いて計算できます。
例として、P' = \text{s}のSA上の範囲は[s', e') = [8, 12)です。このとき、P = \text{is}のSA上の範囲は、PのL列上の範囲L[8, 12)内に存在する文字c = \text{i}（L[10]とL[11]）が、F列に現れる範囲に相当します。
F列において、文字\text{i}はC[\text{i}] = 1行目から連続して出現します。また、F列とL列における文字\text{i}の出現順序は一致します。これらの性質を利用して、Pに対応するSA上の範囲[s, e)を次のように求めることができます。

\begin{align*}
s &= C[c] + \mathrm{rank}_c(T_\mathrm{BWT}, s') \\
e &= C[c] + \mathrm{rank}_c(T_\mathrm{BWT}, e').
\end{align*}
      k  SA[k]  F          L
     -----------------------
      0     11  $mississippi
C[i]  1     10  i$mississipp
      2      7  ippi$mississ
  s   3      4 *issippi$miss <-+
  |   4      1 *ississippi$m <-|--+
  e   5      0  mississippi$   |  |
      6      9  pi$mississip   |  |
      7      8  ppi$mississi   |  |
  s'  8      6  sippi$missis   |  |
  |   9      3  sissippi$mis   |  |
  |  10      2  ssippi$missi*--+  |
  |  11      5  ssissippi$mi*-----+
  e'
したがって、範囲の初期値を[s_0, e_0) = [0, n)とし、与えられたパターンPをその最後尾から一文字ずつ上記の方法で処理することで、P全体に対応するSA上の範囲[s, e)を特定できます。時間計算量は、パターンの長さをmとするとO(m\log \sigma)時間です。

 パターンの出現回数（count）パターンの出現回数（\mathrm{count}）を計算するには、パターンに対応するSA上の範囲[s, e)を上記のアルゴリズムで求めた後、e - sを返します。

 パターンの出現位置（locate）パターンの出現位置（\mathrm{locate}）を特定するには、接尾辞配列 SA 自体の情報が必要になります。パターンに対応するSA上の範囲[s, e)を求めた後、その範囲に含まれるすべての接尾辞配列の値SA[s], SA[s+1], \ldots, SA[e-1]がパターンの出現位置となります。
ここで、SA[0, n) のすべての要素を保持する代わりに、SAの要素をl個おきにサンプリングして保存することでデータサイズを軽減できます。T_\mathrm{BWT}とCを用いて、サンプリングされていないSAの値を必要に応じて復元できます。
この復元に用いられるのがLF-mappingです。LF-mapping（LF）は、L列中の位置kに存在する文字L[k]が、F列においてどの位置に対応するかを示します。FM-indexのクエリの節で説明したアルゴリズムと同じ要領で、以下のように計算できます。

LF(k) = C[L[k]] + \mathrm{rank}_{L[k]}(L, k).
また、LF-mapping はSAとその逆関数SA^{-1}を用いて、以下のように定義される位置間の対応関係と解釈することもできます。

LF(k) = SA^{-1}[SA[k] -_n 1].
ここで、a -_n bはnを法とした減算です。すなわち0-_n1 = n - 1です。
SA[LF(k)] = SA[SA^{-1}[SA[k] -_n 1]] = SA[k] -_n 1であることから、

SA[k] = SA[LF(k)] +_n 1 = \cdots = SA[LF^i(k)] + i.
すなわち、kから初めてLF(k), LF(LF(k)), \ldotsとLF-mappingを繰り返していくと、最終的にサンプルされたSAの要素に到達します。LF-mappingを繰り返した回数とサンプルされたSAの値から、任意のSA[k]を求めることができます。

 複数テキストのための FM-indexFM-indexを用いて、d個のテキスト片T_0, \ldots, T_{d-1}について、以下のクエリを効率的に処理することを目指します。
検索パターンを含むテキスト片の識別子の一覧を取得する
検索パターンの各テキスト片内での出現位置を取得する
検索パターンを接頭辞または接尾辞として含むテキスト片の識別子の一覧を取得する
複数のテキストに対する全文検索を実現するためには、いくつかのアプローチが考えられます。これらのアプローチは、テキストをどのように結合して単一の大きなテキストTとするかによって分類できます。



テキストの結合方法
T


1
異なる終端文字で結合
T = T_0\text\textdollar_0T_1\text\textdollar_1 \cdots T_{d-1}\text\textdollar_{d-1}

2
同一の終端文字で結合
T = T_0\text\textdollar T_1\text\textdollar \cdots T_{d-1}\text\textdollar

3
終端文字なしで結合
T = T_0T_1 \cdots T_{d-1}\text\textdollar


 異なる終端文字で結合この方法は、XML文書上の高速なXPathクエリ処理を実現するSXSI[2]で採用されています。各テキスト片T_xに固有の終端文字\text\textdollar_xを付加し、それらを結合したテキストT = T_0\text\textdollar_0T_1\text\textdollar_1 \cdots T_{d-1}\text\textdollar_{d-1}の FM-indexを構築します。このとき、これらの終端文字\text\textdollar_0, \ldots, \text\textdollar_{d-1}にはテキストの出現順と同一の順序\text\textdollar_0<\text\textdollar_1<\cdots<\text\textdollar_{d-1}を与えます。
Since there are several $’s in T, we fix a special ordering such that the end-marker of the i-th text appears at F[i] in M

 構築検索した位置をテキスト片の識別子と紐づけるために、\mathrm{Doc}と呼ばれるデータ構造を追加します。
T[SA[k]]がテキスト片T_xの先頭文字であるとします。このとき、L[k]は必ず終端文字\text\textdollarです。このとき\mathrm{Doc}[\mathrm{rank}_\text\textdollar(L, k)] = xとします。
例として、テキストT=\text{foo}\text\textdollar_0\text{bar}\text\textdollar_1\text{baz}\text\textdollar_2の回転表を以下に示します。表示の都合上、終端記号の添字は省略していますが、実際には区別されます。
 k  SA[k]  F          L
-----------------------
 0      3  $bar$baz$foo
 1      7  $baz$foo$bar
 2     11  $foo$bar$baz
 3      5  ar$baz$foo$b
 4      9  az$foo$bar$b
 5      4  bar$baz$foo$ L[5] = $_0
 6      8  baz$foo$bar$ L[6] = $_1
 7      0  foo$bar$baz$ L[7] = $_2
 8      1  oo$bar$baz$f
 9      2  o$bar$baz$fo
10      6  r$baz$foo$ba
11     10  z$foo$bar$ba
テキストの\mathrm{Doc}は以下のようになります。


k
T[SA[k]]
i = \mathrm{rank}_\text\textdollar(L, k)
\mathrm{Doc[i]}


5
T_1[0]
0
1

6
T_2[0]
1
2

7
T_0[0]
2
0

\mathrm{Doc}を構築するには、L列（T_\mathrm{BWT}）における終端文字の位置iを\mathrm{select}クエリを用いて順に特定し、SA[i]がテキストT_{x-_l1}の先頭文字の位置であることから対応する \mathrm{Doc}[i]の値を求めます。
またクエリの効率化のために、サンプリングしたSAの位置kについて、対応するテキスト片の識別子xおよびテキスト片における相対位置を\mathrm{Pos}として記録しておきます。

 クエリ与えられたパターンPを含むテキスト片を特定するには、まずPに対応するSA上の範囲[s, e)を求めます。次に、範囲内の各位置k（s \leq k \lt e)について、以下の計算を繰り返します。

L[k] = \text\textdollarまたはkが\mathrm{Pos}でサンプルされた位置の場合、停止する。

k \gets LF(k)とする。
計算を停止した位置kから、パターンPを含むテキスト片T_xの識別子xを以下のように特定します。

L[k] = \text\textdollarの場合、x =  \mathrm{Doc}[\mathrm{rank}_\text\textdollar(L,k)]

kが\mathrm{Pos}でサンプルされた位置である場合、\mathrm{Pos}を参照してテキストの識別子xを取得する
また、繰り返しの回数および\mathrm{Pos}に記録された相対位置を用いて、Pのテキスト片T_x内での相対位置も計算できます。
パターンPがテキスト片の接頭辞として出現する位置を列挙するには、まずパターンPに対応するSA上の範囲[s, e)を求めます。この範囲内の各k（s \leq k \lt e）について、L[k]が終端文字である場合、その出現位置はテキスト片の先頭であると分かります。
パターンPがテキスト片の接尾辞として出現する位置を列挙するには、範囲検索の初期値をF列の終端文字に対応する範囲[0,d)として、SA上の対応する範囲を同様の手順で特定します。

 計算量この方法では、単一テキストのためのFM-indexと比較して、追加で以下のデータが必要になります。
テキストTに保存する各テキスト片の終端文字
\mathrm{Doc}
\mathrm{Pos}
追加される終端文字の数は O(d) 個です。
\mathrm{Doc}を配列として表現する場合、サイズはO(d\log d)ビットです。また、\mathrm{Pos}をサンプリング間隔lで配列として保存する場合、そのサイズはO(\frac n l\log n)ビットです。
パターンのある出現位置について、対応するテキスト片の識別子および相対位置を計算する際の時間はO(l\log \sigma)になります。

 同一の終端文字で結合この方法では、各テキスト片T_xの末尾に同一の終端文字\text\textdollarを付加し、それらを結合したテキストT = T_0\text\textdollar T_1\text\textdollar \cdots T_{d-1}\text\textdollarのFM-indexを構築します。
テキストT=\text{foo}\text\textdollar_0\text{bar}\text\textdollar_1\text{baz}\text\textdollar_2について、 終端文字をすべて同じ文字（アルファベット中の最小値）とみなして接尾辞配列を構築した際の回転表は以下のようになります。
 k  SA[k]  F          L
-----------------------
 0     11  $foo$bar$baz
 1      3  $bar$baz$foo
 2      7  $baz$foo$bar
 3      5  ar$baz$foo$b
 4      9  az$foo$bar$b
 5      4  bar$baz$foo$
 6      8  baz$foo$bar$
 7      0  foo$bar$baz$
 8      2  o$bar$baz$fo
 9      1  oo$bar$baz$f
10      6  r$baz$foo$ba
11     10  z$foo$bar$ba
この方式で構築したFM-indexに対し、そのまま通常のLF-mapping LF(k) = C[L[k]] + \mathrm{rank}_{L[k]}(L, k)を適用すると、L[k]=\text\textdollarの場合に問題が生じます。

例えば、L[6]=\text\textdollarはテキスト片T_1=\text{bar}の終端に対応します。しかし、通常のLF-mappingの計算式を適用すると、

\begin{align*}
LF(6) &= C[\text\textdollar] + \mathrm{rank}_{\text\textdollar}(L, 6) \\
&= 0 + 1 \\
&= 1 \\
\end{align*}
となります。F列のk=1行目F[1]はテキスト片T_0=\text{foo}の終端に対応しており、本来対応するべきテキスト片T_1の終端とは異なります。

LF-mappingは\mathrm{locate}クエリなどで利用されるため、この問題は正確な検索結果を得る上で支障となります。
一方で、終端文字\text\textdollarに順序を定めて接尾辞配列を構築することは容易ではありません。アルファベットを文字と位置（終端文字の場合はテキストにおける位置、そうではない場合は0）の組として拡張したり、接尾辞配列の構築アルゴリズム自体に手を加えたりする方法も考えられますが、実装のオーバーヘッドや複雑性が増加します。
そこで、終端文字に順序を導入する代わりに、テキスト全体Tの先頭に対応するSA上の位置k_0（SA[k_0] = 0）を記憶しておくことで、LF-mapping を正しく計算できるようにします。

 構築\mathrm{Doc}や\mathrm{Pos}といった追加のデータ構造については、異なる終端文字で結合する方法と同様です。
k_0を求めるには、\mathrm{Doc}の構築時にT_\mathrm{BWT}中の終端文字の位置kを列挙する際、終端文字がテキストの末尾、すなわちT_\mathrm{BWT}[k] = \text\textdollar_{d-1}であったときにk_0 = kとすれば良いです。

 クエリk_0を用いてどのようにLF-mappingを計算するかを考えます。以下に示すのは、テキストT=\text{foo}\text\textdollar_0\text{bar}\text\textdollar_1\text{baz}\text\textdollar_2の接尾辞を辞書順に並べた表です。
 k  SA[k]  F          L
-----------------------
 0     11  $          z F[0] = $_2
 1      3  $bar$baz$  o F[1] = $_0
 2      7  $baz$      r F[2] = $_1
 3      5  ar$baz$    b
 4      9  az$        b
 5      4  bar$baz$   $ L[5] = $_0
 6      8  baz$       $ L[6] = $_1
 7      0  foo$bar$baz$ L[7] = $_2
 8      2  o$bar$baz$ o
 9      1  oo$bar$baz$f
10      6  r$baz$     a
11     10  z$         a
この例ではk_0 = 7です。
L列中で文字が\text\textdollarである行（例ではk = 5, 6, 7）、およびF列中で文字が\text\textdollarである行（例ではk = 0, 1, 2）を比較し、LF-mapping によってこれらの終端文字がどのように対応づけられるのかを観察します。

k = k_0 の場合、LF-mappingはL[k_0] = \text\textdollar_{d-1}に対して必ずF[0]を対応づけます。これは\text\textdollar_{d-1}が最小の接尾辞であるためです。例では、L[7] = \text\textdollar_2がF[0]に対応します。
それ以外の終端文字については、その出現順がL列とF列で一致します。これは、L[k] = \text\textdollar_xの行に対応する接尾辞T[SA[k], n-1]に対し、LF(k)の行に対応する接尾辞がT[SA[LF(k)], n-1] = \text\textdollar_x T[SA[k], n-1]となり、接尾辞の順序が保存されるためです。例では、L[5]=\text\textdollar_0、L[6]=\text\textdollar_1がF列においてF[1]、F[2]に同じ順序で出現しています。
よって、L[k]が終端文字であるときのLF-mapping LF(k)は以下のように計算できます。

LF(k) = \begin{cases}
\mathrm{rank}_\text\textdollar(T_\mathrm{BWT}, k) + 1 & \text{if } k < k_0 \\
0 & \text{if } k = k_0 \\
\mathrm{rank}_\text\textdollar(T_\mathrm{BWT}, k) & \text{if } k > k_0 \\
\end{cases}.

 終端文字なしで結合この方法では、終端文字を用いずにすべてのテキスト片を単純に結合したテキストT = T_0T_1 \cdots T_{d-1}\text\textdollarのFM-indexを構築します。この場合、テキスト中の各文字がどのテキスト片に由来するかを別途記録する必要があります。
このために、結合したテキストTと同じ長さのビット列Bを以下のように構成します。
結合されたテキストの文字T[i]があるテキスト片の最後の文字である場合、B[i] = 1とする。
それ以外の場合、B[i] = 0とする。
ビット列Bには、ウェーブレット木と同様に\mathrm{rank}_1(B, i)といったクエリを高速に処理できるデータ構造を用います。

 構築ビット列Bは、簡潔ビットベクトル[3]を用いて表現することで、サイズのオーバーヘッドを小さく抑えつつ、\mathrm{rank_1}クエリを定数時間で計算できます。また、Bに含まれる1の数はテキスト長に比べて少ない（疎である）ので、Elias-Fano符号などを用いてよりコンパクトに保存することもできます。

 クエリ\mathrm{locate}クエリによってパターンPの出現位置iを得た後、x = \mathrm{rank}_1(B, i)を計算することでPの属するテキスト片T_xを求めることができます。ただし、パターンが複数のテキスト片にまたがって出現している可能性があるので、パターンの終端位置i + |P| - 1が開始位置iと同じテキスト片に属するかを別途確認する必要があります。
また、パターンPのテキスト片T_xにおける相対位置は以下のように計算できます。
テキスト片T_0内に出現している場合（x = 0）は、結合テキスト全体における出現位置iがそのまま相対位置となります。
テキスト片T_x内に出現している場合（x > 0）は、テキスト片T_xの開始位置が\mathrm{select_1}(B, x - 1) + 1であることから、相対位置はi - (\mathrm{select_1}(B, x - 1) + 1)です。
例えば、テキストT=\text{foobarbaz\textdollar}について、そのテキスト片の終端位置を記録するビット列はB = 0010010010になります。
x   0  1  2
i   0123456789
--------------
T = foobarbaz$
B = 0010010010
--------------
       012
パターンP = \text{ar}の結合テキストにおける出現位置はi = 4です。このとき、\mathrm{rank}_1(B, 4) = 1であることから、パターンPがテキスト片T_1に出現していることがわかります。その相対位置は4 - (\mathrm{select_1}(B, 1 - 1) + 1) = 4 - (2 + 1) = 1です。
また、Bを用いて、パターンPがテキスト片の接頭辞または接尾辞として出現しているかどうか判定することができます。

 計算量単一テキストのFM-indexに加えて、ビット列Bが追加で必要です。 Bを簡潔ビットベクトルとして実装した場合、サイズはO(n)ビットになります。また、出現位置に対応するテキスト片の識別子や相対位置はO(1)時間で計算できます。

 まとめ複数のテキストに対する高速な文字列検索が、FM-indexを用いてどのように実現できるかを紹介しました。
紹介した内容は出典した文献を元にしていますが、筆者がFM-indexを実装中に考えたアイディアも一部あります。筆者が発見できなかった、より標準的で効率的な手法があるかもしれません[4]。

脚注
Ge Nong, Sen Zhang, & Wai Hong Chan. (2011). Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE Transactions on Computers, 60(10), 1471–1484. https://doi.org/10.1109/TC.2010.188 ↩︎
Arroyuelo, A., Claude, F., Maneth, S., Mäkinen, V., Navarro, G., Nguyen, K., Siren, J., & Välimäki, N. (2011). Fast In-Memory XPath Search over Compressed Text and Tree Indexes (No. arXiv:0907.2089). arXiv. https://doi.org/10.48550/arXiv.0907.2089 ↩︎
Navarro, G., & Providel, E. (2012). Fast, small, simple rank/select on bitmaps. In International Symposium on Experimental Algorithms (pp. 295-306). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-30850-5_26 ↩︎
特に、Compact Data Structures は分野の大家であるNavarro先生による書籍で、簡潔データ構造や索引に関する幅広いトピックをカバーしているようです。複数テキストへの応用についても言及されているかもしれません（未読）。 ↩︎
接尾辞（辞書順）	開始位置
$\text{\textdollar}$	6
$\text{a\textdollar}$	5
$\text{ana\textdollar}$	3
$\text{anana\textdollar}$	1
$\text{banana\textdollar}$	0
$\text{na\textdollar}$	4
$\text{nana\textdollar}$	2
$k$	$T[SA[k]]$	$i = \mathrm{rank}_\text\textdollar(L, k)$	$\mathrm{Doc[i]}$
5	$T_1[0]$	0	1
6	$T_2[0]$	1	2
7	$T_0[0]$	2	0
FM-indexを用いた複数テキストの全文検索

FM-index

FM-index の構築

接尾辞配列（ $SA$ ）

Burrows-Wheeler 変換（ $T_\mathrm{BWT}$ ）

文字の出現回数（ $C$ ）

FM-index のクエリ

パターンの出現回数（count）

パターンの出現位置（locate）

複数テキストのための FM-index

異なる終端文字で結合

構築

クエリ

計算量

同一の終端文字で結合

構築

クエリ

終端文字なしで結合

構築

クエリ

計算量

まとめ

Discussion

クエリ	説明
$\mathrm{count}$	テキスト中のパターンの出現回数を数える
$\mathrm{locate}$	テキスト中のパターンの出現位置を計算する
	テキストの結合方法	$T$
1	異なる終端文字で結合	$T = T_0\text\textdollar_0T_1\text\textdollar_1 \cdots T_{d-1}\text\textdollar_{d-1}$
2	同一の終端文字で結合	$T = T_0\text\textdollar T_1\text\textdollar \cdots T_{d-1}\text\textdollar$
3	終端文字なしで結合	$T = T_0T_1 \cdots T_{d-1}\text\textdollar$