パターンマッチングとは、あるデータ集合の中から、あらかじめ定義された特定のパターンに合致する部分を検出・抽出・認識する操作の総称である。コンピュータサイエンスにおける最も基本的かつ汎用的な処理の一つであり、単純な文字列検索から複雑な画像認識まで幅広い領域で利用される。
パターンマッチングの目的
パターンマッチングの主たる目的は、膨大なデータの中から所望の情報を高速かつ正確に発見することにある。具体的には、テキスト中のキーワード検索、データの妥当性検証、信号中の特定波形の検出、画像中の物体認識などが挙げられる。これにより、人間が手動で行うには非現実的な規模のデータ処理を自動化し、情報抽出や意思決定を支援する。
対象データの種類（テキスト、バイナリ、多次元データ）
パターンマッチングの対象となるデータは多岐にわたる。最も古典的かつ広く研究されているのはテキストデータであり、文字列として表現された文書やコードが対象となる。バイナリデータでは、ファイルヘッダやネットワークパケットのパターン照合が行われる。さらに、画像や音声のような多次元データ（2次元配列や時系列信号）も重要な対象であり、ここでは画素値の空間的パターンや周波数特性が照合される。
完全一致と近似一致（曖昧検索）
パターンマッチングは、完全一致と近似一致の二つの観点から分類される。完全一致は、パターンとデータが厳密に同一である場合のみマッチとみなす手法であり、例えば文字列検索における完全な部分文字列照合が該当する。一方、近似一致は、ノイズや誤差、変形を許容し、類似度に基づいてマッチを判定する。スペルチェックやDNA配列の類似検索、画像のテンプレートマッチングなどがその例である。曖昧検索では、編集距離や相関係数などの尺度が用いられる。
文字列パターンマッチング
文字列パターンマッチングは、テキスト中から特定の文字列（パターン）を検索する問題である。最も古くから研究されている古典的課題であり、多くのアルゴリズムが提案されている。
単一パターン検索アルゴリズム
単一パターン検索は、与えられた一つのパターンをテキスト中から探す問題である。代表的なアルゴリズムとして、ナイーブ法、KMP法、BM法が挙げられる。
ナイーブ法（力任せ法）
ナイーブ法は、テキストの各位置からパターンを一文字ずつ比較し、不一致が生じた場合に次の位置へ進む最も単純な手法である。時間計算量は最悪でO(nm)（n:テキスト長、m:パターン長）となり、大規模データには不向きだが、実装が容易で短いパターンやランダムなデータでは平均的に良好な性能を示す。
KMP法（Knuth-Morris-Pratt）
KMP法は、パターン内の部分一致情報を前処理して「失敗関数」を構築し、不一致発生時にテキストの読み戻しを発生させずに効率的に次の照合位置へジャンプするアルゴリズムである。時間計算量はO(n+m)と線形であり、最悪の場合でも安定した性能を発揮する。特に、繰り返しパターンを含むデータで効果を発揮する。
BM法（Boyer-Moore）
BM法は、パターンの末尾から照合を開始し、不一致が生じた場合に「悪文字規則」と「良接尾辞規則」の二つのヒューリスティックを用いてテキストポインタを大きくスキップするアルゴリズムである。平均的な時間計算量はO(n/m)と非常に高速で、実際のテキスト処理において広く使われる。ただし、前処理にO(m+Σ)（Σ:アルファベットサイズ）の空間を要する。
複数パターン検索アルゴリズム
複数パターン検索は、同時に複数のパターンをテキストから検索する問題である。代表的なアルゴリズムにAho-Corasick法がある。
Aho-Corasick法
Aho-Corasick法は、複数のパターンをトライ木に登録し、さらに失敗リンク（failure link）を構築することで、テキストを一度走査するだけで全てのパターンの出現位置を検出するアルゴリズムである。時間計算量はO(n+m+k)（k:全パターンの総出現数）であり、侵入検知システムやウイルス対策ソフトウェアなどで実用されている。
正規表現によるパターンマッチング
正規表現は、文字列のパターンを記述するための強力な表現手法であり、文字クラス、量指定子、グループ化、選択などの演算子を提供する。正規表現エンジンは、このパターンを内部で有限オートマトンに変換して実行する。
NFA（非決定性有限オートマトン）とDFA（決定性有限オートマトン）
正規表現の処理には、主にNFAとDFAの二つの方式がある。NFAは複数の状態遷移を同時に探索するため構築が容易でバックトラッキングによる実装が一般的だが、最悪時に指数時間となりうる。DFAは状態空間を決定論的に縮退させたもので、一回の文字読み取りで一意の遷移が決まるため処理は線形時間だが、状態数の爆発によりメモリ消費が大きくなる。多くの正規表現エンジンは、実用性と効率のバランスからNFAベースの実装を採用している。
構造化データのパターンマッチング
木構造（XML/HTMLのXPath、CSSセレクタ）
木構造データにおけるパターンマッチングは、特定のノードやサブツリーを検索する操作である。XMLやHTML文書に対しては、XPathがパス式を用いてノード集合を選択する標準的な手法として広く使われる。同様に、CSSセレクタはHTML要素のスタイル適用のために、要素名、クラス、ID、属性、擬似クラスなどを組み合わせてノードを特定する。これらの実装は、木構造の枝刈り探索やインデックス化によって効率化される。
グラフ構造（部分グラフ同型問題）
グラフ構造におけるパターンマッチングは、与えられたパターングラフと同型な部分グラフをデータグラフ内から見つける問題である。これはNP困難な問題として知られ、大規模グラフに対しては近似アルゴリズムや索引構造（グラフデータベースのVF2アルゴリズムなど）が用いられる。化学構造検索やソーシャルネットワーク分析などで応用される。
画像・音声パターンマッチング
テンプレートマッチング
テンプレートマッチングは、入力画像内でテンプレート画像と最も類似する領域を探索する手法である。通常、テンプレートを入力画像上でスライドさせ、各位置での相違度（SSDや正規化相互相関）を計算し、最小値または最大値を与える位置をマッチとする。計算コストが高いため、画像ピラミッドや高速フーリエ変換（FFT）を用いた高速化手法が開発されている。
特徴点ベースマッチング（SIFT、SURF）
特徴点ベースマッチングは、画像からスケール・回転・照明変化に不変な特徴点（キーポイント）を抽出し、それらの局所特徴記述子を比較することで対応点を求める手法である。SIFT（Scale-Invariant Feature Transform）は、異なるスケール空間での極値検出と勾配方向ヒストグラムによる記述子を提供する。SURF（Speeded Up Robust Features）は、SIFTを高速化した手法で、Haar-wavelet応答を用いる。これらの手法は、パノラマ画像合成や物体認識で広く使われる。
バイオインフォマティクスにおけるパターンマッチング
配列アラインメント（BLAST、Smith-Waterman）
配列アラインメントは、DNAやタンパク質の配列間で類似した領域を見つけ、対応関係を取る手法である。Smith-Watermanアルゴリズムは動的計画法に基づく局所アラインメントであり、厳密な最適解を与えるが計算量が大きい。BLAST（Basic Local Alignment Search Tool）は、ヒューリスティックな高速近似手法であり、まず短いシードパターンで一致箇所を探し、それを伸張することで高速な検索を実現する。
モチーフ発見
モチーフ発見は、複数のバイオ配列間で統計的に有意に保存された短いパターン（モチーフ）を発見する問題である。MEME（Multiple EM for Motif Elicitation）などのアルゴリズムは、期待値最大化法を用いてモチーフの位置とコンセンサス配列を推定する。これにより、転写因子結合部位やタンパク質ドメインなどの機能的領域が同定される。
テキスト処理と検索エンジン
テキスト処理の分野では、文書内のキーワード検索、スペルチェック、正規表現を用いたパターン置換などが日常的に行われる。検索エンジンは、膨大なWeb文書からユーザーのクエリに合致するページを瞬時に返すため、インデックス作成と高速なパターンマッチング技術（転置インデックス、Aho-Corasick法など）を基盤としている。
コンパイラの字句解析（トークン認識）
コンパイラの字句解析フェーズでは、ソースコードをキーワード、識別子、リテラル、演算子などのトークンに分割する。これは正規表現によるパターンマッチングを用いた有限オートマトン（字句解析器生成ツールLex/Flex）によって実現される。各トークンはパターンとアクションの組として定義され、入力文字列を先読みしながらマッチしたトークンを出力する。
ネットワークセキュリティ（侵入検知システムのパターン照合）
侵入検知システム（IDS）は、ネットワークパケットのペイロードを解析し、既知の攻撃パターン（シグネチャ）と照合する。SnortやSuricataなどの実装では、Aho-Corasick法や改良版のアルゴリズムを用いて、複数のシグネチャを同時に高速に照合する。リアルタイム性が要求されるため、メモリ使用量と処理速度のバランスが重要となる。
パターン認識と機械学習（ニューラルネットワークのパターン抽出）
機械学習、特に深層学習の分野では、畳み込みニューラルネットワーク（CNN）を用いたパターン抽出が盛んに行われる。CNNは画像や音声などの多次元データから、エッジやテクスチャなどの局所パターンを学習・抽出する。これは従来のテンプレートマッチングや特徴点ベース手法とは異なり、データ駆動で最適なパターンを自動獲得する点が特徴である。また、Transformerモデルでは、自己注意機構を用いて系列データ内の長距離パターンを捉える。
時間計算量と空間計算量
パターンマッチングアルゴリズムの性能は、主に時間計算量と空間計算量で評価される。時間計算量は、テキスト長nとパターン長m（またはパターン数k）に対する漸近的な比較回数や処理手順数を指標とする。ナイーブ法はO(nm)、KMP法はO(n+m)、BM法は平均O(n/m)である。空間計算量は、前処理テーブルやオートマトンの状態数に依存し、Aho-Corasick法はO(Σ×全パターン長)程度、DFAベースの正規表現エンジンは指数爆発の可能性がある。
主なベンチマーク問題（DNA配列、Webページなど）
性能評価には現実的なデータを用いたベンチマークが重要である。DNA配列（数十億塩基対）の検索では、パターン長が短くアルファベットサイズが小さいため、BM法やAho-Corasick法が有効である。一方、Webページの検索では、パターン長が中程度でテキストが自然言語であるため、BM法や改良版のSunday法が好まれる。また、正規表現のパフォーマンス評価では、Perl互換正規表現（PCRE）やRE2などのエンジン間の比較が行われる。
実用的な実装の選択基準
実用的な実装を選択する際には、以下の基準が考慮される。まず、検索パターンの数が一つか複数かによってアルゴリズムが変わる。次に、パターンが静的に決まっているか（前処理が一度で済む）動的に変化するかで、前処理のコストが影響する。さらに、マッチングが正確一致か曖昧一致かによって近似アルゴリズムの要否が決まる。メモリ制限が厳しい環境では、DFAよりNFAベースの実装が選ばれる。また、並列実行やSIMD命令（AVX2など）を活用した実装も近年は一般的である。総じて、応用領域の特性に応じて、速度、メモリ、実装容易性のトレードオフを評価することが肝要である。