面白い記事があったので自分でもやってみる。

使える特殊記号は4つのみ。

文字	意味
`^`	文頭。正規表現の先頭にあるときだけこれとして解釈される。
`$`	文末。正規表現の末尾にあるときだけこれとして解釈される。
`.`	任意の一文字
`*`	直前の文字の0回以上の繰り返し
その他の文字	その文字

カッコによるグループ化がないため、* が直前の正規表現でなく文字の繰り返ししかできないという点で、これは正規表現と名乗ってはいけない。有限オートマトンはもっと強い。| もないし。これでは command.com のファイル名ワイルドカードに毛が生えた程度だ。

本家のコード

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
// regexpの先頭が ^ なら、regexpを一文字進めたところとtextでmatchhere()を呼ぶ
// そうでないとき、textを0文字以上順に先頭を飛ばしたところでmatchhere()を呼び
// textが無くなる前に成功したら成功

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text)
// regexpが空なら成功
// regexpの2文字めが `*` なら、1文字め、3文字目以降、textでmatchstar()を呼ぶ
// regexpが "$\0" なら、textが空かどうかが答え
// textが空でなく、regexpの先頭が.か互いの先頭が一致するなら、再帰呼び出しで次の文字へ進む
// それら以外なら失敗

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
// textを0文字以上順に先頭を飛ばしたところでmatchhere()を呼び、
// textが無くなるか、飛ばす文字が c と異なるため飛ばせなくなる前に成功したら成功

末尾再帰について

matchhere() の中の自己再帰を含む関数呼び出しは、return に入っているので末尾再帰最適化が可能な形。matchstar()（と同等の ^ でない場合の matchhere() の起動）は、失敗したときに巻き戻す必要があるため、return の中には入っていない。

コードクローンについて

match()で先頭が ^ でないときのコードが、matchstar() の c が . なときの振る舞いと同じなので、自前で書く代わりに return matchstar('.', regexp, text); とした方がよいのでは。

という振る舞いと意味を読み取って、Haskellで書き下すと自分ならこうなるかな。

import Data.List (tails, unfoldr)

match2 :: String -> String -> Bool
match2 = start
  where
-- REの先頭が^なら、txtの先頭だけ試す
-- そうでないとき、全ての位置から開始してみる
    start ('^':re) txt = tryhere re txt
    start re       txt = any (tryhere re) (tails txt)
                      -- tryhere ('.':'*':re) txt -- コードクローン回避

-- txtの先頭からマッチするか調べる
    tryhere "$"          txt = null txt
    tryhere ('.':'*':re) txt = any (tryhere re) (tails txt)
    tryhere ( c :'*':re) txt = any (tryhere re) (txt : unfoldr (pop c) txt)
    tryhere ('.':re)     txt = not (null txt) &&                  tryhere re (tail txt)
    tryhere ( c :re)     txt = not (null txt) && c == head txt && tryhere re (tail txt)
    tryhere ""           _   = True

-- txtの先頭にcがあるだけ毟ったものを列挙する
    pop c (x:xs) | c == x = Just (xs, xs)
    pop _ _               = Nothing

re に関しては、先頭の文字で動作を切り替えるためパターンマッチを使い、txt に関しては、その内容は結果を算出する情報源なので等式の右辺で計算している。
（tryhere (c:re) (t:txt) | c == t = ... のようにはしない、ということ）

リンク元のコード

これ match "a*" "" が False になってしまう。スターが付いていようとなんだろうと、match_here で最初を喰ってしまうから、1文字以上の繰り返しという意味になっちゃってるんだな。

計算量の問題

このミニマムな正規表現、* の意味が貪欲とは定義されていないため、c を食べ残した状態でマッチするかも含めて全ての場合を確認しに行っている。
これが多段に積み重なると、計算量が爆発する。
文字列 aa....aac に対して正規表現 ^a*b と ^a*a*b のマッチ判定が失敗して終了するまでの時間を計ってみる（単位は秒）：

aの個数	`^a*b`	`^aab`	`^aaa*b`
100		0.02	0.20
1,000		0.59	(返ってこない)
10,000	0.02	61.84
100,000	0.14
1,000,000	1.32
10,000,000	13.03

a を $x$ 文字取り去った列に対して、a を $y$ 文字取り去った列に対して、先頭に b があるか、を $x = 0,1,2,…, N$ に対して $y = 0,1,2,\dots, N-x$ で繰り返すので $O(N^2)$ になる。
3段なら $O(N^3)$ だ。

真面目に正規表現から非決定性オートマトンを作って、同等な決定性オートマトンに変換して、とやらないからこういうことになる。

DPを使った実現

テキストと正規表現の両方が長くなると空間計算量で破綻するかもだけど、
「テキストの x 文字め以降は正規表現の y 文字め以降とマッチするか」
という表を構成することで、重複した検査を回避して高速に実行できそう。

import Data.Array

data RE = EoRE      -- end of RE
        | Dollar    -- '$'
        | Dot       -- '.'
        | DotStar   -- '.*'
        | Star Char -- 'c*'
        | Char Char -- 'c'

match3 :: String -> String -> Bool
match3 reg txt = marr ! (0,0)
  where
    rts = parse reg

    parse ('^':re) = parseloop re
    parse re = DotStar : parseloop re

    parseloop "$" = [Dollar,EoRE]
    parseloop ('.':'*':re) = DotStar : parseloop re
    parseloop ( c :'*':re) = Star c  : parseloop re
    parseloop ('.':re)     = Dot     : parseloop re
    parseloop ( c :re)     = Char c  : parseloop re
    parseloop "" = [EoRE]

    bnds = ((0,0),(length rts, length txt))
    marr = listArray bnds
        [ matchf irt jcs
        | irt <- zip [0 ..] rts, jcs <- zip [0 ..] $ tails txt]
    marrr ij = inRange bnds ij && marr ! ij -- はみ出したらアウトにするラッパー
    matchf (i,rt) (j,cs) =
      case (rt, cs) of
        (EoRE,_) -> True     -- REが末尾に達したらマッチ成功
        (Dollar, "") -> True -- テキスト末尾なら '$' はマッチ
        (Dot, _:_) -> next   -- 文字があれば '.' はマッチ
        (Char c, t:_) -> c == t && next -- 文字が一致すれば c はマッチ
        (DotStar, _) -> marrr (i1, j) || marrr (i, j1)
-- 0文字で.*を終わらせてこの位置から続きのREをするか、1文字.で読んでこの.*を再開するか
        (Star c, _)  -> marrr (i1, j) || not (null cs) && c == head cs && marrr (i, j1)
-- 0文字でc*を終わらせてこの位置から続きのREをするか、cを1文字読んで再開するか
        _ -> False            -- 以上に当てはまらないものは失敗
      where
        i1 = succ i
        j1 = succ j
        next = marrr (i1, j1) -- 続き

テキスト終端の \0 が欲しかったので、tails を使うことで _:_ か [] かで見分けた。
先頭が ^ でなかった場合、^.* で始まると読み替えている。

性能を計測してみる。

aの個数	`^a*b`	`^aab`	`^aaa*b`
100	0.00	0.00	0.00
1,000	0.01	0.00	0.02
10,000	0.05	0.09	0.10
100,000	0.62	0.72	0.91
1,000,000	5.15	10.90	9.33
10,000,000	^C	未計測	未計測

正規表現の複雑さが実行時間に影響を与えていないことが読み取れる。3段重ねでも平然と動く。
ただし、普通の正規表現の場合の性能はnaiveな実装を下回っている。
遅延配列による暗黙の集めるDPにより単純に実装した代わりに遅いという面もある。
配るDPで命令型プログラムで作ればもっと速いだろうけど、これどうやって配るんだろうね？

おしまい。