alt-depgraph-new の前の状態で試しています。
現状の rule (ノード間の状態遷移を記述したもの)は 962、wtab.h の品詞から
最初のノードを示したものが 162 あります。
これで、., H, C, S と値を加えているところを別のノードとして、文字列の遷移を
文字に展開し、NFA (Nondeterministic Finite Automaton) を構成し、
@名詞1のあと, @名詞6のあと, @名詞11のあと, @名詞21のあと, @名詞26のあと,
@名詞31のあと, @名詞36のあと, @名詞16のあと はないので除いて、
さらに値が加わっていないノードのうち、ここへの遷移がない
@形容動詞仮定形, @形容動詞連体形, @形容動詞連用形, @形容動詞未然形,
@の(名詞化内部), @といけない, @う, @ラ行L5段活用動詞名詞化語幹,
@名詞化動詞のあと も除くと、状態の数は、
11797
でした。この NFA に対して subset construction [1]で DFA を計算すると
(僕のノートパソコンでナイーブなプログラムで 2GB メモリを食って半日以上
かかって)、状態の数は、
46100
となりました。今、この DFA を minimize しようとしています。ナイーブな
O(N^2)のアルゴリズムでやってますので結果はいつになることやら。結果が出
たらまたお知らせします。(Hopcroft optimization [2], [3] でやれば
O(N log N) ですか。[4] によればいろいろ手はあるようです。)
[1] http://en.wikipedia.org/wiki/Powerset_construction
[2] ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf
[3] http://ecommons.library.cornell.edu/bitstream/1813/6002/1/72-151.pdf
[4] http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-03.pdf
--
_______________________________________________
Anthy-dev mailing list
Anthy-dev@lists.sourceforge.jp
http://lists.sourceforge.jp/mailman/listinfo/anthy-dev
