正規表現 (regular expression)、表現自体はあれに想像してしまうが、情報科学の分野では古くから確立した数少ない学問のひとつ。大学にその専攻分野では必ずオートマトンとかいう授業がある。しかし、理解した学生はどれぐらいいるんだろう。複雑な証明に圧倒されてしまうかもしれないし、教える側の先生だって完全に理解してないかもしれない。

Unix のコマンドに古くから実装されてきたが、世間に広く知らしめたのはPerl のお陰だろう。いまでは正規表現が至る所に活用されている。

正規表現といっても、いろいろな定義があって、本アルゴリズムでは、照合パターンとしてつぎのようなものを受けつける。

  abc|def   abc または def
  a(b|)c    b があってもなくてもよい。すなわち ac または abc
  ab*c    b を何回繰り返してもよい。すなわち、ac、abc、abbc...のいずれか

より形式的に説明すると以下のようになる。ただし、PとQはいずれも正規表現とする。

  正規表現   意味(それに一致する文字列)
  文字     その文字自身
  \文字     その文字自身(特別記号 |、(、)、* 等を文字として使う場合)
  (P)     P
  PQ      PとQをつなげたもの(連結、concatenation)
  P|Q     PまたはQ(選択、union)
  P*      Pの0回以上の繰り返し(閉包、closure) 

連結と選択では、連結の方が優先度が高く、閉包はさらにそれよりも高い。

正規表現が与えられると、本アルゴリズムではそれをε遷移を含む非決定性オートマトン(NonDeterministic Automaton)に変換した上で、その非決定性オートマトンをシミュレートしながらテキストとの照合を行う。

より高速に照合を行いたいときは、非決定性オートマトンをさらにそれと等価な決定性オートマトンに変換することが考えられる。

<関数名>
  regMatch 正規表現による文字列照合アルゴリズム
  regNew  文字列照合のための非決定性オートマトンの作成

<形式>
  文字列照合
    char *regMatch(char *text, int len, PAIR *nda);

  非決定性オートマトンの作成
    PAIR *regNew(char *pattern, int patlen);

<引数>
  文字列照合関数において
    text  (入力)テキスト
    len  (入力)テキストの長さ
    nda  (入力)照合パターンに対応した非決定性オートマトン

  非決定性オートマトンの作成関数において
    pattern (入力)照合パターン
    patlen (入力)照合パターンの長さ

<関数値>
  文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

  非決定性オートマトンの作成関数について
    作成した非決定性オートマトン。作成できなかったときは 0 (NULL)。

<注意事項>
  regNew() を呼び出して非決定性オートマトンを作成した後、regMatch() を利用して文字列照合を行う。

用例

<ヘッダファイル>
  regMatch.h

<関数本体>
  regMatch.c

<説明>

Comments are closed.

Post Navigation