FMインデックス

コンピュータサイエンスにおいて、FMインデックスは、バロウズ・ウィーラー変換に基づく圧縮された全文部分文字列インデックスであり、サフィックス配列といくつかの類似点があります。これは、パオロ・フェラーギナとジョバンニ・マンジーニによって作成されました^[1 ] 。彼らはこれを、入力テキストを圧縮しながらも高速な部分文字列クエリを可能にする日和見的データ構造であると説明しています。名前は、Full-text index in Minute space（分単位のフルテキストインデックス）の略です。^[2]

圧縮されたテキスト内のパターンの出現回数を効率的に見つけ、各出現の位置を特定するために使用できます。クエリ時間と必要なストレージ スペースは、入力データのサイズに対して 線形以下の複雑さを持ちます。

オリジナルの著者らは、オリジナルのアプローチを改良し、「FM-Index バージョン 2」と名付けました。^[3]さらに改良されたアルファベット対応の FM-index では、圧縮ブーストとウェーブレット ツリー^[4]を組み合わせて、大きなアルファベットのスペース使用量を大幅に削減しています。

FMインデックスはバイオインフォマティクスなどの分野で利用されています。^[5]

インデックスの使用は、大量のテキストを効率的に検索するための一般的な戦略です。テキストがコンピューターのメイン メモリに適切に収まるサイズよりも大きい場合、テキストだけでなくインデックスも圧縮する必要があります。FM インデックスが導入されたとき、従来の圧縮方法に基づいて、圧縮されたマッチングの問題を解決しようとするいくつかのソリューションが提案されました。対照的に、FM インデックスは圧縮された自己インデックスであり、データを圧縮すると同時にインデックスを作成します。

FM インデックスは、まず入力テキストのBurrows–Wheeler 変換(BWT) を実行して作成されます。たとえば、文字列T = "abracadabra$" の BWT は "ard$rcaaaabb" であり、ここでは各行がテキストの回転であり、行が辞書式に並べ替えられている行列Mで表されます。この変換は、最後の列 (ラベルL )の文字の連結に対応します。

BWT 自体は、たとえば先頭への移動やハフマン エンコーディングによる圧縮を可能にしますが、変換にはさらに多くの用途があります。マトリックスの行は、基本的にテキストのソートされたサフィックスであり、マトリックスの最初の列 F はサフィックス配列と類似点があります。サフィックス配列が BWT とどのように関係するかは、FM インデックスの核心です。

count演算はパターンP[1..p]を受け取り、元のテキストT内でのそのパターンの出現回数を返します。行列Mの行はソートされており、Tのすべての接尾辞が含まれているため、パターンPの出現は1 つの連続した範囲内で互いに隣り合うことになります。この演算はパターンを逆方向に反復します。パターン内のすべての文字について、その文字を接尾辞として持つ範囲が検索されます。たとえば、「abracadabra」内のパターン「bra」の数は次の手順で計算されます。

1. 最初に探す文字はパターンの最後の文字であるaです。初期範囲は[C[a] + 1 .. C[a+1]] = [2..6]に設定されています。L 上のこの範囲は、aで始まるサフィックスを持つTのすべての文字を表します。
2. 次に探す文字はrです。新しい範囲は、 start が範囲の開始インデックスで end が終了インデックスである場合、[C[r] + Occ(r, start-1) + 1 .. C[r] + Occ(r, end)] = [ 10 + 0 + 1 .. 10 + 2] = [ 11..12]です。L 上のこの範囲は、raで始まるサフィックスを持つTのすべての文字です。
3. 最後に見る文字はbです。新しい範囲は[C[b] + Occ(b, start-1) + 1 .. C[b] + Occ(b, end)] = [6 + 0 + 1 .. 6 + 2] = [7..8]です。L 上のこの範囲は、braで始まるサフィックスを持つすべての文字です。これでパターン全体が処理されたので、カウントは範囲のサイズと同じになります: 8 - 7 + 1 = 2。

パターン全体が検索される前に範囲が空になったり、範囲の境界が交差したりした場合、パターンはT内に出現しません。Occ (c, k) は定数時間で実行できるため、カウントはパターンの長さの線形時間、つまりO(p)時間で完了します。

操作locateは、 L内の文字のインデックスを入力として受け取り、 T内のその位置iを返します。たとえば、locate(7) = 8です。パターンのすべての出現箇所を特定するには、まず、 count操作が範囲を見つけたのと同じ方法で、サフィックスがパターンである文字の範囲を見つけます。次に、範囲内のすべての文字の位置を特定できます。

LのインデックスをTのインデックスにマッピングするには、 LのインデックスのサブセットをTの位置と関連付けます。 L[j]に位置が関連付けられている場合、 locate(j)は簡単です。関連付けられていない場合は、関連付けられたインデックスが見つかるまで文字列の後にLF(i)を続けます。適切な数のインデックスを関連付けることで、上限を見つけることができます。 Locate は、テキストT[1.. u ]内のパターンP[1.. p ]のocc出現を、任意のk ≥ 0に対して入力シンボルあたりビット数でO( p + occ log ^ε u )時間で見つけるように実装できます。^[1] ${\displaystyle O\left(H_{k}(T)+{{\log \log u} \over {\log ^{\epsilon }u}}\right)}$

バックトラッキング付き FM インデックスは、文字列マッチング/配列アラインメントの近似に成功しています (引用数 2000 件以上)。Bowtie を参照してください (http://bowtie-bio.sourceforge.net/index.shtml)。

• バロウズ・ウィーラー変換
• サフィックス配列
• 圧縮された接尾辞配列
• 配列アライメント
• ウェーブレットツリー