2012.03.13 Tuesday
FSTとGraphViz
LuceneのFSTというクラスを見ていたら、同じパッケージのUtilクラスにtoDot()というメソッドがあったので、FSTオブジェクトをGraphVizで表示してみた。そのプログラムと手順を紹介しよう。
FSTはFinite State Transducer（有限状態変換器）の略でそのままの名称のクラスがLuceneで提供されている。FSAと異なり受理した言語（バイトシーケンス）を任意の出力にマップする。Lucene/Solrでは単語辞書をさまざまなメタ情報にマップしたり、類義語辞書を持ったりするので、FSTがいろいろなところで活用できる。FSTを構築するのにすぐれたアルゴリズムがあり、こちらの論文で紹介されている方法を使ってFSTクラスが実装されている。この方法では入力単語はあらかじめソートされている必要があるが、Luceneの単語辞書はUnicode順でソートされており、また類義語辞書などソートされていないものについてはソートした上でadd()すればよい。
FSTを使った簡単なプログラムを次に示す。
このプログラムを実行すると、out.dotというファイルができるので、GraphVizのdotコマンドを次のように実行する。
すると、out.pngという次のような画像ファイルが出力される。
このアルゴリズムではプレフィックスだけでなくサフィックスも文字列が共有されており、非常にメモリ効率が高いことがわかる。
あの米Clouderaディレクターも参加したロンウイットのSolrトレーニング・・・受講者インタビュー記事
決算期の今は実は受講の大チャンス！あなたの部署の余った予算を有効活用しましょう。 Solr 3.5 4月 トレーニング受講者募集中
FSTはFinite State Transducer（有限状態変換器）の略でそのままの名称のクラスがLuceneで提供されている。FSAと異なり受理した言語（バイトシーケンス）を任意の出力にマップする。Lucene/Solrでは単語辞書をさまざまなメタ情報にマップしたり、類義語辞書を持ったりするので、FSTがいろいろなところで活用できる。FSTを構築するのにすぐれたアルゴリズムがあり、こちらの論文で紹介されている方法を使ってFSTクラスが実装されている。この方法では入力単語はあらかじめソートされている必要があるが、Luceneの単語辞書はUnicode順でソートされており、また類義語辞書などソートされていないものについてはソートした上でadd()すればよい。
FSTを使った簡単なプログラムを次に示す。
public final class TestSimple {
static final String[] DATA = {"station", "commotion", "elation", "elastic", "plastic", "stop", "ftop", "ftation", "stat"};
public static void main(String[] args) throws IOException {
List<String> list = new ArrayList<String>();
for(String d : DATA){
list.add(d);
}
Collections.sort(list);
NoOutputs outputs = NoOutputs.getSingleton();
Object nothing = outputs.getNoOutput();
Builder<Object> b = new Builder<Object>(FST.INPUT_TYPE.BYTE1, outputs);
final BytesRef term = new BytesRef();
final IntsRef scratchIntsRef = new IntsRef();
for (String d : list) {
term.copyChars(d);
b.add(Util.toIntsRef(term, scratchIntsRef), nothing);
}
FST<Object> fst = b.finish();
Writer w = new PrintWriter("out.dot");
Util.toDot(fst, w, true, true);
w.close();
}
}
このプログラムを実行すると、out.dotというファイルができるので、GraphVizのdotコマンドを次のように実行する。
$ dot -Tpng -o out.png out.dot
すると、out.pngという次のような画像ファイルが出力される。
このアルゴリズムではプレフィックスだけでなくサフィックスも文字列が共有されており、非常にメモリ効率が高いことがわかる。
あの米Clouderaディレクターも参加したロンウイットのSolrトレーニング・・・受講者インタビュー記事
決算期の今は実は受講の大チャンス！あなたの部署の余った予算を有効活用しましょう。 Solr 3.5 4月 トレーニング受講者募集中
