大富豪家2.0の日記
2005年10月04日
00:44
状態遷移機械ライブラリ
ふたつの状態遷移機械の"cross"を計算する良いライブラリって無いでしょうか。ふたつの状態遷移機械の両方にマッチするシーケンスを表現する状態遷移機械を高速に計算したいのです。
Grail+というシステムのfmcrossというコマンドが使えるのですが、いろいろ制約があるもので...
コメント
2005年10月04日
01:15
Mike
ほ、ほう。遺伝的アルゴリズムとしても利用できそう。
うーん、意外と計算は面倒そうですね。
2005年10月04日
01:19
大富豪家2.0
NDFAからDFAを計算するのと同じ要領でやればいいのかな? 富豪的手法がどの程度通用するか...
2005年10月05日
17:17
shinji
もしチェックするだけだったら、複数のチェックを平行に走らせた方が簡単だと思います。
NDFA/DFA変換は状態数の指数オーダであることが知られてます。けど例の通り最小かどうかは知られてないはず。
なんだけどand/orの計算はもっと簡単です。DFAでもNDFAでも、両方の状態数n,mで、n x m の状態を作り、その遷移を計算すれば良いです。これでn x m x transition 数で計算可能です。それで計算量が大きすぎるんだったら、まぁ、頑張ってください。いろいろ工夫できます。
not が入るとDFA/NDFA変換を避けられなくなるので指数オーダになります。
2005年10月06日
00:27
大富豪家2.0
notは要らないです。例文集をNDFAで表現したnと、ユーザが入力したパタンから生成されるmのマッチをとりたいわけですが、m は比較的小さい(< 10?)からなんとかなるかもしれません。
NDFAのまま並行してmとのチェックすればいいんですな。
2005年10月06日
00:38
shinji
regcomp library では、そのような方法をとっているようです。そのあたり読んでみたらどうでしょう。ちなみに僕は挫折しました。
でも正規表現にはandってないんだよね。なんでだろう? grep | grep すれば良いからかな。
2005年10月06日
00:46
大富豪家2.0
情報ありがとうございます。調べてみます♪
> でも正規表現にはandってないんだよね。なんでだろう?
他にも不便な点はいろいろありますよね。万能みたいに信奉されるのはどうかと思う。
