NIIBE Yutaka
gniib****@fsij*****
2010年 7月 14日 (水) 10:41:26 JST
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 --
