はてなキーワードっぽいものの実装方法を調べる

テーマ指向SNS改めテーマ指向短文投稿サイトの企画の関係で、どうしてもはてなキーワードっぽいキーワード自動リンクものの実装方法を調べる必要がありそうなので、その中間調査。

軽くぐぐってみた感じ

いくつか見つかったのでおいておく。


はてなのような自動キーワードリンクをtx-rubyで実装
http://silentpower2.blogspot.com/2009/08/tx-ruby.html

僕もキーワードリンクを実装する機会があったのですが、そのときはtx-rubyを使いました。
〜中略〜
これはtrieというデータ構造を扱うtxというライブラリを、rubyから使うものです。


はてなのようなキーワードリンクをRubyで付与する実例
http://d.hatena.ne.jp/tasukuchan/20090810/senna_autolink_ruby

ニコニコ大百科では、キーワードリンク専用のRubyモジュールを書いています。「SENNA」というキーワードがあったら、「senna」とか「ＳＥＮＮＡ」とかにリンクさせたりとかもできます。


PHPとMecabでキーワード自動リンクを実装する
http://labs.unoh.net/2008/01/keyword-autolink-using-php-and-mecab.html

Webサービスを開発していると、特定のキーワードを自動でURLリンクにする処理が必要になることがあると思います。今回は、このキーワード自動リンク機能を形態素解析ツールMecabを使ってPHPで実装する方法を紹介したいと思います。


稼動実績的にSennaが一番いけてる気がするんだけど、ソースコードはtx-rubyの例が一番すっきり。
って、全部なんかしらサーバにインストールしてるなぁ。
こちとらロリポ生活なんでレンタルサーバで動いてほしいんだけど・・。


そもそも論として、最低10万件程度は想定しているであろうキーワードの処理を毎回読み込み直しってありえないだろうしねぇ。
こっち側の環境の問題さえ解決出来れば簡単なんだけど、こちとら貧乏なんだよ！
解決は無理という前提で、頑張って考えてみよう。


Trie

tx-rubyの記事からたどるに、どーもこの手の処理を実装するにはTrieっていうアルゴリズムがいいらしい。
Google IMEにも使われているらしいぞ。
http://research.preferred.jp/2011/05/trie_survey/

trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。
〜中略〜
この問題は簡潔木を利用することで解決できます。このアイディアを実装したものがtx, uxなどです。私もお世話になっているGoogle IMEもtxのクローンであるrxを利用することで大規模辞書を効率的に管理しています。


んー、こいつの簡単な実装をPerlかRubyかPHPかPythonで書けばとりあえず将来の移行もしやすそうだしいいのかな？
まあレンタルサーバにおいている時は俺専用ツールになるだろうし、速度もそれ程気にする必要もないだろう。間違ってユーザがついてしまっても、きっとどこかのえらい人が専用サーバくらいプレゼントしてくれて、専用のエンジンに置き換えればいいだろう！


という方向で仮決めして進めるのがいい気がする。


実装したいものの要件

念のため実装したいものの要件をまとめておく。こんなのだ。

  1. テーマがある
  2. テーマには三つ*1キーワードが定義出来る。これをテーマワードと仮に呼ぶ
  3. Twitterみたいな短文投稿ツールを作る
  4. 短文投稿すると、テーマワードで自動的に投稿とテーマが紐付けられる
  5. 短文投稿する際に、明示的にテーマを指定することも可能

世界創造ツールとかを作ったら、世界創造ツールとか、地図自動生成とかを適当にキーワード定義しておけば、後は適当につぶやいてけばハッシュタグ使わなくても自動カテゴライズされますよと。


このツール自体は掲示板とTwitterを足して2で割ったようなもので、どっちかっていうと掲示板寄り。
テーマと呼んでるものが、掲示板でいうスレッドになる。


一点思想上の問題があって、掲示板ってのはテーマを先に決めるコミュニケーションツールなんだけど、Twitterの場合は発言が先に来る。
なんの気なしにイカとタオル間違えたと呟けば、そのイカとタオルの話題が元々なんの気なしにつぶやいた発言をルートにどんどん発展していく。
テーマを先に決めるとすると、このTwitterのつぶやきファーストによるコミュニケーションの気楽さを消しそうだなと。


つまり、つぶやく時にテーマにヒットするようにいちいち「世界創造ツールについて - 1」とか入れないといけない気にさせるとか。これって短文投稿としては結構アウトだよねと。掲示板もスレッド選ぶのが面倒くせんだよ。
まあそんな懸念材料はあるけど、四の五の考えずに作ってみっかぁって感じで。


短文投稿で、かつ"テーマを後で作る"事をサポートしなければとりあえず処理速度遅くても大丈夫そう。
正直テーマを後で作る、は、サポートしたいけどね。全件走査じゃなくて、直近1万程度の発言から拾うくらいならぎり仮エンジンでも大丈夫そうな気がするがどうかな。まあ仮でサポートしないって事にしとこう。


マッチ方法

基本は最長一致かなぁと思うんだけど微妙。
世界創造ツール、ツール、世界って三つのキーワードがあったとして、世界創造ツールにマッチしたら世界とツールにはマッチしたことにしないってのが基本だと思うんだけど・・。


でも全部マッチしちゃってもいい気がすんだよな。だって発言に含まれてんだし。
とりあえずIMEで使えるって事は全マッチが確実に可能なんで、マッチ方法の面でも問題はなさそうかな。
最長一致だけにする場合にむしろちょいといじらないといけないのかも。でも最長一致だけにするのはそれ程面倒でもなかろう。

問題なさそう

利用用途的にも、アルゴリズム的にもそんなに問題はなさそう。
後は実際に仮エンジン書いてみて、速度的に問題ないか実験する感じっすなぁ。
11月開始予定だけど、時間あったら先に書いてみよう。

*1:三つがいいかは検討中