二次元パターンマッチング

コンピュータサイエンスにおいて、2次元パターンマッチングとは、より大きな2次元行列（「画像」、または文字列検索になぞらえて「テキスト」）の中から、文字の2次元行列（「パターン」）の出現箇所を特定する問題である。^{[ 1 ]}

パターンが与えられたと仮定します${\displaystyle P[m\times m]}$そしてテキスト${\displaystyle T[n\times n]}$、 どこ${\displaystyle m\leq n}$最も単純なアプローチは、P をサイズ のすべてのサブ配列と比較することです。${\displaystyle m\times m}$Tにおいて、このアルゴリズムの最悪時間は${\displaystyle \Theta ((n-m+1)^{2}m^{2})}$通常は次のように想定されます。${\displaystyle m\leq n/2}$そこから、これは次のように書ける。$\displaystyle \Theta (n^{2}m^{2})$。

より効率的な解決策（主にバード1977によるもの）を例を用いて説明しよう。次のパターンとテキストがあるとしよう。

 abaab アババーブ P = bab T = abaab アバババブ アババ

まず、線形テキストからPの列の出現箇所を検索するAho-Corasickオートマトンを構築します 。副産物として、各列に識別子が割り当てられ、同一の2つの列には同じ識別子が割り当てられます。この例では、最初の（および3番目の）列は0で識別され、中央の列は1で識別されます。

次に、T の列に対してオートマトンを実行し、P の列のいずれかが T に現れるたびに（線形時間で）その表示を取得します。この例では、これは次の 3×5 行列 C になります（「-」は一致しないことを示します）。

 abaab アババーブ P = bab T = abaaa C = 01--- アバババブ 10--1 アババ 010-0

ここで、 Knuth-Morris-Prattアルゴリズムを使用して、Cの行からPと同一のパターン、すなわち010を検索します。パターンが見つかった場合、Tの中にPが出現したことがわかります。C全体またはT全体をメモリに保持する必要はないことに注意してください。Tは行ごとに読み込むことができ、Cからは1行だけをメモリに保持すればよく、Aho-CorasickオートマトンとKMPオートマトンの状態の行も一緒に保持する必要があります。

このアルゴリズムの実行時間は${\displaystyle O(n^{2})}$Aho-Corasickアルゴリズムに存在するアルファベットのサイズへの依存性を無視すれば、複雑さは${\displaystyle O(n^{2}\log k)}$ここで、kはアルファベットのサイズである。

アルファベットのサイズへの依存は、${\displaystyle O(n^{2})}$GalilとParkのアルゴリズム。^{[ 2 ]}

• 文字列検索アルゴリズム

• アポストリコ、アルベルト（1999）。「第13章：一般パターンマッチング」。アタラ（編）『アルゴリズムと計算理論ハンドブック』CRC Press、 13-11頁。ISBN  0849326494。
• Bird, Richard S. (1977). 「二次元パターンマッチング」. Information Processing Letters . 6 (5): 168–170 .
• Galil, Zvi; Park, Kunsoo (1996). 「アルファベットに依存しない2次元の証拠計算」. SIAM Journal on Computing . 25 (5): 907–935 .