遅い→起動時

http://d.hatena.ne.jp/pmint/

例えばWikiEngineの、自動リンクのアルゴリズムの説明

d:id:pmint:20130204:p1の続き。


1つの長文 対 多数の短文を照合して、長文内からすべての短文を検索するアルゴリズム


日本語の文書が分かち書きされてたならWikify @ appointment.atのやり方でもいいね。テキスト解析 - Yahoo!デベロッパーネットワークのように分かち書きにしてくれるWebサービスもあるし。でも今回は分かち書きせずにひと続きの長文を対象にする方法について。


以前と同じくn-gramを作るけど、今度は「そのn-gramが長文中のどこにあるか」を示す転置インデックスを作成する。
n-gram辞書のサイズが短文リストの十何倍とかになるけどね。28.5MB(およそ135万語)の短文辞書から作られるインデックスが493MBとかね(・∀・;)
でも必要のないスキャン処理を無くすことができた。唯一スキャンしてるのが長文側のn-gramリストだけ。


通常の全文検索にも使えなくはないけど、長文側をスキャンしているので効率は悪そう。(未調査)この場合は 多数の長文 対 検索欄に入る程度の短文 なので数が全くの想定外。両方に通用するアルゴリズムにしたいところだね…。((まあ長文側n-gramと短文側n-gramの少ない方をイテレーターにすればいいだけの気がするけど。
その場合は長文側も短文側と同様に同じn-gramをまとめて、n-gram → 長文上の(そのn-gramの)出現位置リスト ができるようにしておけばもっと早くなりそう。
でも長文側イテレーションと短文側イテレーションでコードが別になってしまうね…。なぜなら長文側は一部分だけ適合すればいいけど、短文側は一単語まるごと適合しないといけないから。短文側は長文側に包含されていなければいけないので、どちらでイテレーションするかは大きな違い。))

サンプル

長文テキストに含まれる言葉を現在第2回 出典をつけよう大会開催中のWikipediaへのリンクに変える。リンク化するのはWikipedia日本版にある項目名だけ。

稼働中(135万語を自動リンク
http://x04-1.pmint.name/?w=00
長文側データ (54.1KB) 短文側データ (28.5MB)


コードは最後に。
d:id:pmint:20130204:p3




動かしてみるとひどく遅い。
この環境でもレスポンスが返ってくるまで1分近くかかったりする。その理由は…

  • まずデータが多い
    それを克服するのが目的なんだけどね(汗
    実験で使ってる長文テキストのサイズは54.1KB、短文のほうは135万語あって28.5MB。
    長文側にするのは前回と同様に2007年2月19日の「枕投げ」のテキスト。
    短文側にするのはWikipedia日本版の項目名(2013年1月25日時点のもの)。長短織り交ぜて135万語。
  • n-gram辞書のデシリアライズ
    1万語規模になるとn-gram辞書の使う部分だけをロードしないと実用にならないかも。Google製の爆速ライブラリがあるみたいだけど今回はサンプルということで.NET Frameworkだけで済ませとく。
  • シリアライズしたn-gram辞書の参照(!)
    なんかね、Dictionaryオブジェクトのキーが複雑だと遅いらしい。このアルゴリズムを実用化するためには致命的かもね。




結果を見てみるとリンク化した部分には隙間があって、Wikipedia日本版には「最新」や「投げ」という項目が無いのが分かる。あと「前」はあるけど「次」は無い、「勝」はあるけど「敗」は無いとかも。


「余裕」も無いね。寄付募ってるくらいだからね。
兄弟プロジェクトのWiktionaryには「余裕」があるみたい。


データを減らしてみた

検索処理だけならまだましだけど、データロードに時間がかかりすぎるので短文側の語数を減らしてみた。


リンク処理が多いテキスト──この例ではWikipediaの項目リスト──を28.5MB分与えても…秒程度。もしこのサーバーで実用するとしたらちょっとデータが大きいか。項目名にやたらヒットする1文字ひらがなみたいなのがあるのも遅さの理由。

では2文字以下の項目名を取り除いてみると…漢字の2文字熟語は残してあるから、Wikipediaの項目にリンクするならこれが現実的な計測なのかな…?
結果を見てみると事典にありそうな言葉だけがリンクされてる。

(2文字以下の語を排除した例。135万語)
http://x04-1.pmint.name/?w=01
長文側データ (54.1KB) 短文側データ (28.5MB)


Wikipediaでもない限りそんなにデータは大きくならないよね、ってことで…

(ひらがな/カタカナ語を削除した例。68万語)
http://x04-1.pmint.name/?w=02
長文側データ (54.1KB) 短文側データ (12.1MB)


(漢字始まりの語を削除した例。52万語)
http://x04-1.pmint.name/?w=03
長文側データ (54.1KB) 短文側データ (14.0MB)


(現実的な例。適当に作った1万語)
http://x04-1.pmint.name/?w=04
長文側データ (54.1KB) 短文側データ (0.24MB)


1万語程度だと今の環境と実装でも0.5秒…使えそう?(サーバーは鉄道マニア