2008/09/13

多バイト文字とDFA

ときどきの雑記帖:

flex の森 - ひげぽん OSとか作っちゃうかMona-
誰か多バイト文字に対するDFA構築手法をわかりやすく解説してくだちい。

文字クラス中の文字は大抵近接した領域に固まってるので、 全部utf-8にしてオクテット列をacceptするDFAにできなくはなさそうな (文字クラスでの分岐が一段じゃなくツリーになるけど、近い領域に固まっていると ツリーの根元が多く共有される&リーフは何でも良い場合が出てくる、ので 圧縮できるんではないかなあと)。 ただ、DFAでそれをやってるのは見たことないから思ったより圧縮できないのかも。 Spencerの新しい方のDFA(Tclに使われてるやつ)も確かいちいちucs-4に展開して、 さらにDFAをon-demandで作ることでサイズを抑えていたと思う。

GaucheのregexpエンジンはNFAだけど基本的にオクテット列に対して動作する ように展開される。ただ、文字クラスについてはオクテット列のツリーに するのが面倒だったので、一度文字を構築してレンジチェックをかけている。 オクテット列のままやったらどのくらい差が出るか測ってみたいんだけど 当分そんな暇は無さそう。

Tags: Programming, Gauche