senはいらない子？
QMACloneの類似問題検索エンジンに使っていたsenが重い+メモリリーク疑惑なため、senがやっていた部分を自作ルーチンで置き換えようと考えました。senがやっていたのは問題文の固有名詞を抜き出すというところ。固有名詞を抜き出すだけであれば自分で書いても問題ないだろうと思い、やってみました。
固有名詞を抜き出すにあたり問題となるのが時間計算量です。senを使っていたときにはデータベースを全てなめ終わるまでに5分程度かかってしまっていました。これより遅くては開発に支障をきたします。
そこで考えたのがTrie木(http://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8)を使った高速化です。Trie木は大量の短い単語を記録し、対象の文章にマッチするかどうかを判定するのに非常に適したデータ構造です・・・だと思います。日本語版Wikipediaの項目名からTrie木を作成し、問題文とマッチさせるといった感じです。
一番単純な形で組んでみたところ、メモリを700MB程食うとんでもないルーチンになってしまいました。ArrayList
もっとメモリが節約できないか？と思い、intとしてみました。二次元目の偶数が文字を、奇数がエッジを表します。二次元目はあらかじめソートしておき、二分探索できるようにしておきます。この部分が最悪ケースだとO(logN)かかってしまいますが、どうせ一番大きいノードは先頭のノードなので気にしないことにします(いいのか？)。これによりメモリ使用量を80MBに抑えることができました。これなら十分使えます。
作ったルーチンと先日書いたtfidf+コサイン尺度のルーチンを組み合わせたところ、なかなかいい結果が出ました。"坊ちゃん"は普通に出てきます。
さて、次は夜間に重くなる原因を探らなくては・・・。
