Pediator リリース

google chrome用拡張機能、Pediator をリリースしました。
https://irts.jp/program/browserplugin/pediator/

なんか、凄く時間かかった。。作り始めてから一年くらい経ってるんじゃないかこれ。
最初は楽勝と思ったものの、いろんなところで躓きました。
A HREF++(あ・は~ふ)と違い実用というよりはおふざけに近く、また、技術的な挑戦の側面もあったりします。

せっかくなので、以下に Pediator のポイントをいくつか書いておきます。

発端

友人K 『勝手に Wikipedia とか Uncyclopedia とかの項目にリンクができたらウザくて面白いんじゃねー。』
  俺  「おーそれいいね。それくらいならすぐできるだろ。作るわ。」
     ※これくらいささっと作れる、そんなふうに考えていた時期が俺にもありました。

形態素解析

まずはページを解析する必要があります。適当に MeCab 使えばいいんじゃねとか思っていたのですが、
さすがに MeCab の Javascript 実装はありませんでした。そりゃそうか。

Firefox なら、XPCOM を使って MeCab を動かす事も可能(実際にやってる人がいました)ですが、
今回はなぜか Chrome で作り始めちゃったので Firefox は諦めました。
てかめんどくさそうだし。MeCab の辞書も一緒に配布するの?みたいな。

あとは Javascript から叩ける MeCab の WebAPI があったり、Yahoo が形態素解析を行ってくれる WebAPI を
提供していたりしたのですが、さすがにページの単語を毎回リクエストしたら怒られそうだったのでこれもやめました。
どこかに cgi を設置して毎回問い合わせを行う方法も検討したけど、どれくらいアクセスがあるか不明なので諦め。

最終的に、Javascript で分かち書きを行う TinySegmenter を使う事にしました。
って、これ MeCab の人じゃん。結局お世話になってる感じ。

辞書作成

分かち書きはできました。
そしたら後はそれぞれの単語が Wikipedia/Uncycropedia に存在するかどうかを調べるだけですね。
あれ、どうやって?

ちなみに、Wikipedia の項目数は 120万項目を超え、タイトルだけのリストがテキストで 25MBほどあります。
 ・Wikipedia:データベースダウンロード
どんだけー。

最初に考えたのが、タイトルリストをそのまま連想配列にブチ込んで、形態素解析した単語を
順次Key の存在確認を行う方法。これなら単語の検索速度もほぼゼロに近い。

んで、やってみるとわりと上手く行きました。
辞書を読み込んだ時点で 100MB程メモリを持っていかれましたが。。
4GBのメモリが数千円で手に入る昨今、100MBくらいどうって事ないですがさすがに拡張機能一つで
メモリ 100MBとかは無いわー。配布パッケージが zip圧縮で 8MBとかも無いわー。
早さが売りの Chrome が、起動時に辞書読み込みでもたつくとか無いわー。

次に考えたのが、辞書の圧縮。
120万項目あるのなら、120万個のハッシュ値を作り、項目をなるべく短い文字列に変換して
それを辞書とし、形態素解析結果をハッシュにしつつ辞書と比較する事で上手く行くのでは!?

結論から言うと、この方法はボツになりました。
最初、自分でハッシュ関数を作ってみた所、当然と言うかなんと言うか、衝突しまくるw
諦めて MD5 にした所、衝突は無くなりましたが辞書が小さくならない。。
MD 5の上 10数桁だけを使ったとしても、120万項目だと結局 10数MBを超えるサイズになってしまいます。
さらに桁数を少なくすると衝突するし。

そこでいろいろ調べているうちに素敵な解決方法に出会いました。
それが Bloom Filter。これで勝つる。

Bloom Filter

Bloom Filter とは何か。
ある文字列が、特定の文字列(辞書)の中に含まれているかどうかを効率よく調べる手法です。
これだけだと何を言っているのかわかりませんね。

具体的には以下のように動作します。
まず、m個のビット列(最初は全部 0とする)を用意し、登録したい単語を辞書に登録して行きます。
辞書の作成方法は、0から mの値を一意に取るハッシュ関数を k個用意して、登録したい単語を
ハッシュ化し、0-mの間に k個のビットフラグ(1)を立てて行くだけ。

ある単語が辞書内に含まれているかどうかは、k個のハッシュ関数を通して辞書と照らし合わせる
(辞書中の k個のフラグがすべて 1だと含まれると判断する)事で容易に判別できます。

Bloom Filter を使う事で、辞書サイズをかなり小さくする事ができ、検索も一瞬。
良い事尽くめのように見えますが、いくつか弱点があります。

まず、稀に誤検知する事。
Bloom Filter はその特性上面白い事に、辞書に含まれていない事は 100%保証できますが、
辞書に含まれている事は 100%保証できません。
どういう事かと言うと、k個の関数を通した結果が、偶然すべて一致する単語が複数あった場合は、
それらを区別できずどちらも「辞書に含まれている」としてしまいます。

あとは、辞書への追加は可能ですが、削除はできません。
削除したい場合は辞書を作り直す事になります。

誤検知について、辞書に登録する単語が多ければ多いほど、Bloom Filter のビット列が
1で埋まって行き、間違える可能性が高くなります。ここら辺は辞書のビット列を多く取れば取る程
誤検知の確率は下がるものの、結局はメモリとのトレードオフになります。

辞書に登録する単語数を n、辞書用のビット数を m、ハッシュ関数の数を k とすると、
それぞれの数によって誤検知率は変わってきます。そして事前にそれらを計算した表がありました。
 ・Bloom Filters – the math

ちなみに Pediatorの場合、9/11時点で
  n = 1231017  (Wikipedia項目数)
  m = 29544408 (用意するビット数)
  k = 15      (ハッシュ関数の数)
なので、上記表からすると m/n=24 で誤検知率は 1.02e-05 つまり 0.0000102 となり、
100,000単語に付き一回間違えるとかそんな感じでしょうか。Pediator が生成したリンク先に Wikipedia の
ページが無かったとしたらそれは誤検知です。開き直ってそのページを作る等の対応をお願いします。

Bloom Filter について調べた際、分かりやすかったのは以下のページです。
 ・ありえるえりあ – Bloom filterの説明
 ・よくわかる BloomFilter

高速化と政教分離の歴史

さて、形態素解析と辞書は準備できました。
そうするとあとは一ページを解析するのにかかる時間をいかに短くできるかです。

最初は、DOMで全てのテキストノードを取得し、ちまちま置換して行っていたのですが、
ページが大きくなるといまいち待たされる。もうこれは考えうる最大のページを参考に、
それをベンチマークにしようと思い、探すとこんなものを見つけました。
 ・Wikipedia:長いページ

トップの「政教分離の歴史」は 500kbを超えるビッグサイズ!
とりあえずこのページで普通に解析を行ってみると、約一分程ブラウザがフリーズ orz

これじゃダメだという事で、DOM のループを XPath 一本釣りにしたり、TinySegmenter を高速化した
TinySegmenter_mod を使ったり、MD5 計算ライブラリを入れ替えたりいろいろやってみたものの
劇的な効果は得られず。恐るべし政教分離の歴史。

それはそうと、Pediator のページ内メニューをアニメーションさせる為に setInterval と setTimeout の
違いなんかを調べたりしていたのですが、そこで閃いた。ページを一気に書き換えじゃなくて逐次処理して行けば、
遅くなってもキャンセルできるし、ブラウザが固まる事はないんじゃね?

ここでヒントになったのは小飼弾さんのこの記事です。
 ・javascript – ページはいつ再描画されるか
これまで画面描写が計算後一気に行われていた所を setTimeout に書き換えて逐次処理にしたところ、
ページ処理時間は 5倍になりましたが、リアルタイムで処理状況が分かるので時間はあまり気にならなく
なりました。処理中もブラウジングできるし、プログレスメニュー(左下に出るパーセント表記ね)も表示
するようにしたし。

あとは、setTimeout のタイミングを 0ms にしても何か遅いので、こんなのを使ったりとか。
 ・setTimeout with a shorter delay
これは結構効果的でした。

まあ、それでも「政教分離の歴史ページ」だとページ解析に 5分くらいかかるんですけどね。
途中でキャンセルできるようにしたから許して。

フレームとの戦い

あと困ったのがフレームを使ったページの場合。
前に管理していたサイトが frameset 使いまくりのくせにこんなことを言うのもなんですが、
フレームページは扱いにくい。まず、ページ内 Pediatorメニューを表示することができない orz
正確に言うと埋め込みはできるんだけど、普通にやると全フレームにメニューを埋め込んじゃう。

これじゃいかんという事で、いろいろ考えた結果、フレームページの場合は、Pediatorメニュー用に
もう一つフレームを作るという力技で対処しました。そしてプログレスメニュー表示は諦め。。
プログレスメニューを出さないので、フレームを使ったページの場合は、一気に書き換える
ようになっています。ちょっと引っかかるような感じはあるけど、まあこれはこれで。

いやほんと、フレームとかなくなればいいのに。
HTML5 では無くなるけどね!わーい!

まとめ

・Bloom Filter いいよ Bloom Filter
・Wikipedia/Uncycropedia の辞書は気が向いた時に更新します。
・Wikipedia はともかく、Uncycropedia はマジ時間泥棒です。オススメ!

という事で、意外と面白いからみんな Pediator使ってみてね!

コメントする

メールアドレスが公開されることはありません。 が付いている欄は必須項目です