パターン照合

文字列処理における最も基本的な技術がパターン照合（Pattern Matching）です。パターン照合とは、2つの文字列が与えられたとき、一方の文字列がもう一方の文字列中に出現するかどうかを調べる技術です。照合する文字列をパターン、照合先の文字列をテキストと呼びます。

例えば、「ないてい」をパターンとして考えてみましょう。

テキストが「ないていがないとないている」のとき、パターンはテキストに出現していると言えます。一方、テキストが「ないてからではおそい」のときはどうでしょう。「ないてい」がそのままテキストに現れている部分はありません。

・パターンが出現

ないていがないとないている

・パターンが出現しない

ないてからではおそい

「ないていがないとないている」や「ないてからではおそい」のようなとても短いテキストの場合には、パターンが出現するかを一瞬で判断することができると思います。しかし、例えばテキストとして与えられる文字列が書籍やウェブサイトだった場合はどうでしょうか？瞬時にパターンが出現するか判断するのはとても難しいということが、容易に想像できると思います。

パターン照合問題には、上述したような

（１）　テキスト中にパターンが出現するか？

といった問題の拡張として、

（２）　テキスト中のどの位置にパターンが出現するか？

（３）　テキスト中に何回パターンが出現するか？

などのバリエーションが容易に考えられます。

例えば、テキストが「ないていがないとないている」、パターンが「ないてい」の例では、（１）（２）（３）の答えはそれぞれ、

（１）Yes

（２）1、9の位置

（３）2回

となります。

（１）（２）（３）のような問題の他にも、パターン照合問題にはパターンの出現の仕方やパターン・テキストの数に応じて実に多くのバリエーションと応用が存在します。