最後まで読みました. 対話的に書かれていて読みやすかったのと, ソースコードがほとんどそのまんま動いたため楽しかったです.
正直言って, 正規表現のエンジン書いたのは初めてでした. この論文の素晴らしい所は, そんなぼくでも, ACT1を読むだけで, 取り敢えずなんか動くエンジンが作れてしまうことですね. ただ, 指数関数的にメモリーを食うからがんばろうって言ってACT2に続くわけですが...
ACT2からもすごく良かった. Semiringを使って正規表現の返す値を一般化する方法は, とても美しく, 気持よかったです. そして, 最終章のLazinessにきた時, 興奮が収まりませんでした.
少しコード貼っておきます. 最初に出てくる, 正規表現を表すデータ型はこんな感じです.
data Reg = Eps | Sym Char | Alt Reg Reg | Seq Reg Reg | Rep Reg instance Show Reg where show Eps = "" show (Sym a) = [a] show (Alt a b) = "(" ++ show a ++ "|" ++ show b ++ ")" show (Seq a b) = show a ++ show b show (Rep a) = "(" ++ show a ++ ")" ++ "*"
例えば,
main = do let a = Sym 'a' print a let b = Sym 'b' print b let ababs = Seq a (Seq b (Rep (Seq a b))) print ababs let aorb = Alt a b print aorb
とかだと
a b ab(ab)* (a|b)
のようになります. ええ.
で, で, で!!!
Haskellのlaziness使えば { a{n}b{n} | n >= 0} == /|ab|aabb|aaabbb|aaaabbbb|.../みたいな, 無限長の正規表現を作れるよ的な話が最後にあって,
main = do let a = Sym 'a' b = Sym 'b' anbn = Alt Eps (Seq a (Seq anbn b))
＼ほれ, できた／
んでもって
print a print b print (match_w (weighted anbn) "" :: Bool) print (match_w (weighted anbn) "ab" :: Bool) print (match_w (weighted anbn) "aabb" :: Bool) print (match_w (weighted anbn) "aaaabbbb" :: Bool) print (match_w (weighted anbn) "aaabbbb" :: Bool) let a300b300 = let n = 300 in replicate n 'a' ++ replicate n 'b' print (match_w (weighted anbn) a300b300 :: Bool)
とかすると,
a b True True True True False True
みたいに返ってきます (論文の最後までちゃんと読めばmatch_wやweightedの意味が分かります).
気になったので, nを変化させた時の実行時間の変化をプロットして見ました. コードは
import System main = do let a = Sym 'a' b = Sym 'b' anbn = Alt Eps (Seq a (Seq anbn b)) args <- getArgs let n = read (head args) :: Int let str = replicate n 'a' ++ replicate n 'b' print n print (match_w (weighted anbn) str :: Bool)
みたいな感じね.
うげげ, 指数関数的... 結構ゆっくりだけど...
でも1000*2=2000の長さの文字列をHaskellで20秒ほどで評価できたからまぁいいかな(´・ω・｀)
取り敢えず読んで下さい. 面白いです.
読みきった後に知ったのですが, ソースコードのリポジトリがgithubで公開さています. 今から落としてコード読みます. 素晴らしい論文を有難う御座いました.
Weighted RegExp Matching (ソースコードは見ずに論文を読みながらコード書いたほうが絶対楽しいです)
