パターンマッチング

パターンマッチング（英えい: Pattern matching、パターン照合しょうごう）とは、データを検索けんさくする場合ばあいに特定とくていのパターンが出現しゅつげんするかどうか、またどこに出現しゅつげんするかを特定とくていする手法しゅほうのことである。

文字もじ列れつのパターンマッチングには、固定こていされたパターンの検索けんさくではKMP法ほうやBM法ほうなど各種かくしゅの文字もじ列れつ探索たんさくアルゴリズムがある。また正規せいき表現ひょうげんを利用りようする手法しゅほうも多数たすう提案ていあんされている。

いくつかの高水準こうすいじゅんプログラミング言語げんごには、多た分岐ぶんきの一種いっしゅで、場合ばあい分わけと同時どうじに構成こうせい要素ようその取とり出だしのできる言語げんご機能きのうがあり、パターンマッチと呼よばれている。Haskellでの例れいを示しめす。

listSumCase lst =
  case lst of
    []       -> 0
    (x : xs) -> x + listSumCase xs

listSumPtn []       = 0
listSumPtn (x : xs) = x + listSumPtn xs

なお、この例れいの listSumCase は expression style、listSumPtn は declaration style である。

歴史れきし

パターンマッチング構造こうぞうを備そなえた初期しょきのプログラミング言語げんごには、COMIT (1957)、SNOBOL (1962)、Refal (1968)、ツリーベースのパターンマッチング、Prolog (1972)、 SASL (1976)、NPL (1977)、およびKRC (1981)がある。

多おおくのテキストエディタはさまざまな種類しゅるいのパターンマッチングをサポートしている。QEDエディタは正規せいき表現ひょうげん検索けんさくをサポートし、一部いちぶのバージョンのTECOでは、検索けんさくでOR演算えんざん子こをサポートしている。

数式すうしき処理しょりシステムは通常つうじょう、代数だいすう式しきのパターンマッチングをサポートしている。

「正規せいき表現ひょうげん#歴史れきし」も参照さんしょう

参考さんこう文献ぶんけん

• 『Analytic Pattern Matching: From DNA to Twitter』 Philippe Jacquet・Wojciech Szpankowski、Cambridge University Press、2015年ねん、ISBN 9780521876087

関連かんれん項目こうもく

• 索引さくいん
• 検索けんさく
• 検索けんさくエンジン
• データベース
• ワイルドカード (情報処理じょうほうしょり)
• 画像がぞう処理しょり