文字列検索アルゴリズム完全ガイド：KMP・Boyer-Moore・Rabin-Karpから応用まで

2025年12月13日 最終更新日時 : 2025年12月13日 エバープレイ編集部

はじめに

文字列検索は、IT・ソフトウェア開発における基礎かつ非常に重要な問題です。テキスト処理、ログ解析、検索エンジン、コンパイラ、バイオインフォマティクスなど多くの分野で必要とされます。本稿では、代表的な文字列検索アルゴリズムを理論的な性質と実装上の注意点を含めて詳述し、用途別の選び方や実務上の落とし穴にも触れます。

文字列検索の問題定義と評価指標

基本問題は、長さ n のテキスト T と長さ m のパターン P が与えられたとき、T の中に P が出現する位置を全て（または最初の位置のみ）求めることです。評価指標としては計算時間（平均・最悪ケース）、空間使用量、前処理コスト、ストリーミング対応の可否、最悪ケースの振る舞い（例：ハッシュ衝突での劣化）などが重要です。

愚直法（ナイーブ法）

最も単純なのは各位置でパターンを1文字ずつ比較する方法で、最悪計算量は O(nm) です。ただし平均的には多くのランダムデータで高速に動作します。局所的にパターンの前半が一致した場合に多く比較が発生するため、悪意ある入力や特定の反復構造に弱い点に注意が必要です。

Knuth-Morris-Pratt（KMP）アルゴリズム

KMPは文字列パターンの『接頭辞と接尾辞の一致』情報を利用して不要な比較を飛ばし、全体で O(n + m) の時間で検索を行います。前処理でパターンの部分一致表（failure function, prefix function）を O(m) で構築し、テキスト走査時にその情報を使ってシフト量を決定します。

  • 利点：最悪ケース O(n + m)、安定して高速。
  • 欠点：ヒューリスティックのような平均的な超高速化は期待できない（だが安定性が強み）。

実装上は prefix 関数の定義と境界条件に注意すること、0-index/1-index の取り扱いを間違いやすい点に気をつけてください。

Zアルゴリズムとprefix関数

Zアルゴリズムは文字列の各位置で先頭からどれだけ一致するかを示す Z 配列を O(n) で計算します。パターンとテキストを結合した文字列（P + '#' + T）に対して Z を計算すれば、Z の値が m と等しい位置がマッチ位置になります。KMP の prefix 関数と役割は近く、選択は実装のしやすさや用途に依存します。

Rabin-Karp法（ローリングハッシュ）

ローリングハッシュを用いてテキストの各長さ m の部分文字列のハッシュ値を O(1) 更新で求め、パターンのハッシュと比較します。ハッシュが一致した場合に実際の文字列を比較して真の一致を確かめます。典型的には平均 O(n + m)（ハッシュ関数が良好な分布を仮定）ですが、ハッシュ衝突が多発すると最悪 O(nm) まで劣化します。

  • 実装上の注意：モジュロ演算に使う素数の選択、ベースの選択、オーバーフロー対策（64ビットのオーバーフローを利用する手法や二重ハッシュ）、Unicodeの取り扱い。
  • 利点：複数パターンを同時に扱いやすい、ストリーミング処理に向く。

Boyer-Moore と Boyer-Moore-Horspool（BM/BMH）

Boyer-Moore はパターンを右から左へ比較し、2つのヒューリスティック（bad-character rule と good-suffix rule）を組み合わせて大きくシフトできる点が特徴です。平均的には非常に高速で、実際のテキスト検索ライブラリでも採用されることが多いです。Boyer-Moore-Horspool は good-suffix の簡略化版で実装が容易かつ実用上は十分高速です。

  • 利点：平均的にサブリニア（nの下回る）時間で動作することが多い。
  • 欠点：最悪ケースは O(nm)、パターンが短いと効果が薄い。

Aho-Corasick（多パターン検索）

Aho-Corasick は複数のパターンを同時に検索するための有力な手法で、パターン集合のトライ（Trie）を構築し、失敗リンク（failure links）を張ることでテキストを一回走査するだけで全ての一致を O(n + total_pattern_length + output) の時間で得られます。大量のパターンをまとめて検索する場合に非常に有効です。

  • 注意点：構築時にメモリを消費する（配列や map を大量に使用することがある）。パターン数や総長さが大きいとトライが巨大化する。

接尾辞構造（Suffix Array / Suffix Tree / Suffix Automaton）

接尾辞構造は文字列のすべての部分文字列に関する情報を事前に構築することで、後のクエリを高速化します。接尾辞配列（Suffix Array）は比較的メモリ効率が良く、二分探索により部分文字列検索を O(m log n) で行えます。接尾辞木（Suffix Tree）は Ukkonen のアルゴリズムなどで O(n) 構築でき、最長共通部分列や多数の複雑な文字列問題を線形時間で解けます。接尾辞オートマトンは部分文字列の包含関係や出現回数集計に便利で、構築は O(n) です。

  • 用途：多数の検索クエリを同一テキストに対して行う場合や、最長共通部分列、最長反復部分列などの高度な問題。
  • 注意：構築コスト（時間・メモリ）が高い点。実用ではライブラリや既存実装を利用することが多い。

実装上の現実的な注意点

以下は実務でよく遭遇する注意点です。

  • エンコーディングと Unicode：UTF-8 等のマルチバイトエンコーディングでは「文字」単位で正しく比較するにはデコードや正規化が必要。バイト列として検索するならバイト単位で扱う。
  • 正規化（Normalization）：合字や結合文字（例：e + ´ と é）を同一視する必要がある場合、NFC/NFD 等の正規化を先に行う。
  • 大文字小文字の扱い：ケースインセンシティブ検索は文字ごとの変換（Unicode のケースマッピング）やロケール依存性に注意する。
  • ストリーミング：テキストが逐次到着する場合、KMP やローリングハッシュ、Aho-Corasick は状態を持って継続できるので有利。
  • ハッシュの安全性：Rabin-Karp で単一モジュロだと衝突リスクがあるため、64ビットでの二重ハッシュや複数モジュロを用いると安全性が高まる。

用途別のアルゴリズム選択ガイド

  • 単一パターン、最悪ケースを気にする：KMP や Z アルゴリズム。
  • 短いパターンを大量に検索・高速な平均性能が欲しい：Boyer-Moore / Horspool。
  • 複数パターンを同時に検索する：Aho-Corasick。
  • ストリーミングデータや固定長スライディング検索：Rabin-Karp（ローリングハッシュ）。
  • 多数クエリを高速に答えたい（事前処理許容）：接尾辞配列・接尾辞木・接尾辞オートマトン。
  • 高度な文字列解析（最長反復、頻度解析など）：接尾辞構造。

ベンチマークと実務上のチューニング

実装ごとの差は大きいため、ライブラリや言語組み込みの最適化済み関数（例：C/C++ の strstr、Java の indexOf、Python の find メソッド）をまず検討してください。プロファイリングでボトルネックを確認し、ホットスポットに対して具体的なアルゴリズム変更や低レベル最適化（SIMD 利用、バイトレベル操作）を行うと良いでしょう。

例：簡単なローリングハッシュの実装上のポイント

典型的には次を守ります。

  • 基数（base）をランダムまたは固定の適切な値にする（英字なら 131 や 257 等）。
  • モジュロは 2^61-1 のような大きな素数か、64ビット自然溢出を利用する方法で衝突を減らす。
  • マルチハッシュ（二重ハッシュ）で安全性を高める。
  • マッチ確認はハッシュ一致時に実際の文字列比較を行うことで正確性を担保する。

まとめ

文字列検索アルゴリズムには用途ごとに最適な選択肢があり、KMP や Z が理論的に安定、Boyer-Moore 系が平均で高速、Rabin-Karp はストリーミングや近似検索に有用、Aho-Corasick は大量のパターン検索に強力、接尾辞構造は多数クエリや複雑な文字列問題に有効という特徴があります。実務ではエンコーディング、正規化、ハッシュ衝突、メモリ制約などの実装上の落とし穴に注意し、まずは組み込み関数や信頼できるライブラリを使ってプロファイリングし、必要に応じてアルゴリズムを切り替えるのが安全で効率的です。

参考文献

カテゴリー
IT
前の記事
ミニマルハウス徹底解説：起源・音像・制作法から名盤・現在の潮流までNew!!
2025年12月13日
次の記事
鬼武者シリーズ徹底解説：歴史観とゲーム性の進化、名作の系譜と復活の可能性New!!
2025年12月13日