« Yahoo形態素解析サービスを使って閲覧中ページのキーワードクラウドを表示するGreaseMonkeyスクリプト | メイン | サイボウズ・ラボの「COO」 »

Javascriptでdiffる ( with 形態素解析 )

Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。

実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変……
diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し(実際にはそれより小さくすることができるのですが、まあ話のイメージとして)、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。

比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない(わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう)。最小の文字単位だとギブアップ。
ということは形態素解析で分かち書きして、単語単位で diff するのが Javascript で処理する場合の正解なんでないの?

というわけで、がっっつり作ってみました(いつもなら「さっくり」というところですが、楽ではなかったので……w)。

Yahoo! の 日本語形態素解析Webサービス を呼び出すために、今回も GreaseMonkey スクリプトになっています。
適当なページを開いて、GreaseMonkeyのアイコンを右クリック>ユーザスクリプトコマンド>diff from google cache で現在見ているページの Google Cache を取得、Yahoo形態素解析サービスに投げて、単語単位で diff を表示します。ヘテロなのはわざとですw

diff-from-gc.jpg

このような感じで diff 結果がオーバーレイ表示されます。中谷のこの blog の平均的な記事量程度であれば4,5秒で処理が終了します。もっと大きいページの場合だと処理に時間がかかっているという警告が出てしまうかもしれません。

diff のアルゴリズムは下記論文を参照しました。
・ S. Wu, U. Manber, G. Myers, and W. Miller, "An O(NP) Sequence Comparison Algorithm" (1990)
このアルゴリズムの計算量は「(全体の要素数)×(比較した結果、削除される要素数)」に比例します。diff のシンプルなアルゴリズムの中では十分以上に速いものではないかと思います。

これを Ruby で実装したあと Javascript に移植したのですが、Ruby では特に問題にならなかったのに、Javascript だと最初遅くて遅くて、データサイズが大きくなると全く使い物にならず……。Javascript 用に実装を最適化する部分で一番時間がかかってしまいました(苦笑)。今月からラボに加わった amachang にも助けを求めたりしてw。

でもその甲斐あって、Javascript diff としては十分満足のいく性能と精度を確保できたと思います。
例えばライバルの一つ、Google の diff ライブラリである google-diff-match-patch と条件を同じ「文字単位 diff」にして比べても速度は2~3倍勝り、精度もこちらの方が上でした( google-diff-match-patch は共通部分を見逃すことがあります。Myers 氏の一つ前の論文のアルゴリズムをベースに実装したと説明に書いてあるのですが、そのアルゴリズムに忠実であれば共通部分を見逃すはずはないので、独自の工夫の部分で精度を落としてしまっているようです)。

Javascript diff ライブラリへの需要があるようだったら、もう少し手を加えてライブラリ化したいなと思います(例えば、IE向けの最適化とかまだ全然やってないので)。


実は、「Yahoo! の形態素解析サービスが JSONP に対応してくれれば、普通の web ページでもこの diff ライブラリと組み合わせて使えるのに!」という結論にしてやろうと思って作り始めたのですが、よく考えたら JSONP は POST できないのでやっぱり組み合わせられない……とほほ。
というわけで、形態素解析を当てにせず文字単位で diff れるようにするしかないのかなあ。

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1360

コメントを投稿