Luceneで使われてるFSTを実装してみた（正規表現マッチ：VMアプローチへの招待） - Qiita入力と出力のペアに対して，上のようなグラフを作るのが目標です．テーブルの出力のとこは数字が書いてありますが，文字列だと思ってとらえて下さい．map だと出力は1つに限られちゃいますが，ひとつの入力に対して出力が複数あってもいいです．たとえば入力 "feb" に対して，出力は "28" と "29" があります．（2月は28日と29日のときがありますね）． ノードの部分が状態で，そこから出ている矢印が状態遷移になります．矢印には a/b というラベルがついていますが，a の部分が入力とのマッチを意味し，b の部分がそのときの出力を意味します． 上の例で示すFSTで，"aug"を処理するには，"aug"を頭から読んで，入力"a"に対応するの(9)から(3)への矢印を選択します．そのとき，出力として"3"を記録しておきます．そのあと，"u"に対して(3)から(2)への矢印を選択し，"1"を先ほど
Palantir Blog
