接尾辞配列とトライ木（全文検索の基盤）

なぜ全文検索に専用の索引が要るのか

長さ n のテキストから長さ m のパターンを毎回探すなら、文字列照合アルゴリズムの KMP などで O(n+m) で済みます。しかし同じテキストに対して何度も検索する全文検索では、テキストを毎回なめ直すのは無駄です。索引（インデックス）を一度作っておき、検索をパターン長 m だけに依存させたい。これがトライ木・接尾辞木・接尾辞配列の動機です。木構造の基礎はデータ構造で扱ったので、本稿はその上に立つ文字列専用索引の内部に踏み込みます。

鍵となる発想は「テキストの全接尾辞を索引化すれば、任意の部分文字列はどれかの接尾辞の接頭辞である」という事実です。テキスト banana の部分文字列 nan は、接尾辞 nana、na のうち nana の接頭辞になっています。つまり接尾辞の集合を接頭辞検索できる構造に入れれば、部分文字列検索が接頭辞検索に帰着します。

トライ木 — 文字を辺に持つ多分木

トライ（trie、別名 prefix tree）は、文字を辺のラベルに、文字列を根からの経路に対応させた木です。同じ接頭辞を持つ文字列は経路の前半を共有します。{to, tea, ten} を入れると次のようになります。

        (root)
          | t
         (1)
          | o\     \e
         [to]      (2)
              a/      \n
            [tea]     [ten]

検索は1文字ずつ辺をたどるだけで、長さ m の文字列の検索・挿入は O(m)、しかもテキスト全体のサイズ n に依存しません。これがハッシュテーブルにない強みで、トライは接頭辞一致（te で始まる語を全部）や辞書順列挙、オートコンプリートを自然に扱えます。各ノードに「ここで単語が終わる」フラグを持たせ、語の終端を区別します。

基数木（パトリシア木）— 連鎖を畳んで圧縮する

トライをたどると、子が1つしかないノードが鎖状に続く区間が頻出します。基数木（radix tree / Patricia trie）は、この分岐のない連鎖を1本の辺に畳み込み、辺のラベルを1文字ではなく部分文字列にします。{romane, romanus, romulus} なら、共通する rom を1辺にまとめ、分岐点だけにノードを置きます。

(root) --rom--> (・) --an--> (・) --e--> [romane]
                  |  \              \us-> [romanus]
                  \ulus-> [romulus]

ノード数が分岐の回数で抑えられるため、メモリと走査コストが大きく下がります。基数木は文字列だけでなくビット列の索引としても強力で、IP ルーティングテーブルの最長接頭辞一致や Linux カーネルのページキャッシュ（ファイルのページ管理）で使われます。考え方は範囲をまとめて持つ平衡木とは異なり、キーの接頭辞構造そのもので木を畳む点が特徴です。

接尾辞木 — 全接尾辞をトライ化した万能索引

ここで全文検索に戻ります。テキスト T のすべての接尾辞を基数木に入れたものが**接尾辞木（suffix tree）**です。banana の接尾辞は banana, anana, nana, ana, na, a の6本。これらを圧縮トライ化すると、根からの任意の経路がテキストのどこかの部分文字列に一致する木ができあがります。終端記号 $ を末尾に付けて、ある接尾辞が別の接尾辞の接頭辞になる事態を防ぐのが定石です。

接尾辞木の威力は検索計算量に出ます。パターン P（長さ m）の出現は、根から P の経路をたどれるかを見るだけ。たどり切れれば、その部分木の葉が出現位置すべてに対応します。つまり部分文字列の存在判定が O(m)、出現回数や全出現位置の列挙も部分木サイズに比例して取れます。さらに最長共通部分文字列、最長反復部分文字列なども木構造上の操作で解けます。

接尾辞配列 — 接尾辞を辞書順に並べた整数列

接尾辞配列（suffix array）は、接尾辞木のほぼ全機能を整数1個ぶんのメモリ/文字で実現する構造です。定義は単純で、テキストの全接尾辞を辞書順にソートし、その開始位置（添字）だけを並べた配列 SA です。banana（末尾に番兵を想定）の接尾辞を辞書順に並べると次のようになります。

順位  開始位置  接尾辞
 0      5        a
 1      3        ana
 2      1        anana
 3      0        banana
 4      4        na
 5      2        nana

このとき SA = [5, 3, 1, 0, 4, 2]。配列はテキスト長ぶんの整数列に過ぎず、メモリは文字あたり実質4〜8バイトと接尾辞木より桁違いに軽い。検索は接尾辞がソート済みである性質を使い、パターン P を接頭辞に持つ接尾辞の範囲を二分探索で絞り込みます。1回の比較に最大 m 文字かかるので、素朴には O(m log n) で部分文字列を引けます。

構築計算量は手法で幅があります。全接尾辞をそのまま比較ソートすると O(n² log n)。実用的には倍々で順位を確定していく接尾辞ランクの手法（プレフィックス・ダブリング）で O(n log n)、DC3（Skew）や SA-IS といった専用アルゴリズムなら線形 O(n) で構築できます。SA-IS は実装が比較的簡潔で省メモリなため、現代の標準的な構築法になっています。

LCP 配列 — 隣接接尾辞の共通接頭辞で照合を削る

接尾辞配列だけだと、二分探索の各ステップで P を毎回先頭から比べ直すため log n 段ぶん m 文字の重複比較が生じます。これを削るのが LCP 配列（Longest Common Prefix array）です。LCP[i] は「SA 上で隣り合う2つの接尾辞 SA[i-1] と SA[i] の最長共通接頭辞の長さ」を持ちます。

順位  接尾辞    LCP（直前との共通接頭辞長）
 0    a         -
 1    ana       1   （"a" を共有）
 2    anana     3   （"ana" を共有）
 3    banana    0
 4    na        0
 5    nana      2   （"na" を共有）

LCP 配列は接尾辞配列から Kasai のアルゴリズムで O(n) で構築できます。これが効くと、二分探索中に「ここまでは一致済み」という情報を隣接接尾辞間で引き継げるため、各文字を高々一定回しか比べず、検索がO(m + log n) まで改善します。さらに区間最小値クエリ（RMQ）と組み合わせれば、任意の2接尾辞の最長共通接頭辞を O(1) で得られ、最長反復部分文字列などの問題に直接効きます。

構造の比較と使い分け

ここで σ はアルファベットサイズ、n はテキスト長、m はパターン長です。判断の起点は「何を索引したいか」に尽きます。

• 語の集合を接頭辞で引く（辞書、入力補完、IP ルーティング） → トライ／基数木。共有接頭辞でメモリを節約でき、辞書順列挙も自然。
• 1本の長いテキストの任意部分文字列を高速に引く → 接尾辞配列+LCP 配列。線形構築・省メモリ・O(m+log n) 検索で、全文検索エンジンや平衡木では扱いにくい部分文字列クエリに最適。
• 複雑な文字列問題を理論的に最短で解きたい（最長共通部分文字列など） → 接尾辞木。ただし定数倍とメモリの重さを許容できる範囲で。

いずれの構造も「部分文字列を、接尾辞の接頭辞検索に帰着させる」という同じ原理を、木で持つか整数配列で持つかの違いで実装しています。全文検索の高速さの正体は、検索のたびにテキストをなめる代わりに、接尾辞という冗長だが規則的な集合を一度だけ索引化しておく――この前計算の置き換えにあります。