moco(beta)'s backup: Lucene FST のアルゴリズム (2) 〜実装編〜
Lucene FST のアルゴリズム (1) ～図解編～ の続きです。絵まで書いたなら実装しろよということで、、、実装してみました。実装言語はみんなだいすき Python です。 // fst.py https://gist.github.com/mocobeta/8e20a0c21b83bc98b880#file-fst-py コードを引用するとちょっと長いのですが、120行目〜231行目(create_minimum_transducer 関数) で FST を構築しています。こったことは全然していなくて、論文中の擬似コードを素直に落とし込んでいます。 FST のモデルを構築しただけでは実際に使えないので、バイトコードに落としこむ必要があるのですが、それは 234行目〜296行目の compileFST という関数でやっています。作った FST (状態のリスト) を、辺 (Arc) の
moco(beta)'s backup: [翻訳] Using Finite State Transducers in Lucene
Lucene/Solr Advent Calendar 2014 22日めです。 第15回Solr勉強会で、ごく軽くLucene FST の紹介をしたのですが、自分もまだまだ勉強中です。ということで Lucene 開発者の Mike さんに、だめもとで「ブログのFST 関連のエントリを翻訳していいですか？」とメールを送ってみたところ、「いいよ！」と快諾してもらえたので、ここに掲載します。 —- 関連する話題ですが、 Golang で書かれた形態素解析器 kagome を作っている @ikawaha さんが、Lucene を絡めて猫にもわかる（かもしれない） FST の解説を書いてくださいました。ありがとうありがとう（；ω；）！アルゴリズムの説明から Double Array との比較まで至れり尽くせりなのであわせてどうぞ。 Luceneで使われてるFSTを実装してみた（正規表現マッチ：VM
![moco(beta)'s backup: [翻訳] Using Finite State Transducers in Lucene](https://cdn-ak-scissors.b.st-hatena.com/image/square/77d318a372491738cf7b65d7f6175d3c375a4701/height=288;version=1;width=512/http%3A%2F%2Fmedia.tumblr.com%2F572c54507b5a6157d76d225cfc7fa3bf%2Ftumblr_inline_ngwt2vmr2e1qmxdmr.png)
Finite-state transducer - Wikipedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (August 2014) (Learn how and when to remove this message) This
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"を先ほど
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
