nakatani @ cybozu labs

Yahoo! Japan から 日本語形態素解析Webサービス がリリースされて、「ほほう」と思っている人も多いかと思います。
mecab などをサーバにインストールすれば今まででも形態素解析を使用したサービス(特に需要が多いのは分かち書きかな？)を提供することは可能だったわけですが、形態素解析は結構重い処理なので、非力なサーバだと少々しんどくて困っていたり、そもそもそういったアプリケーションをインストールできないサーバなために形態素解析の利用を断念していたなんて人には結構朗報かもしれません。
個人的には JSONP に対応して欲しかったところ。あんなことやこんなことやもやもやいろいろできるんだけどなあ……

でもまあこのサービスをちょっと試してみたかったので、GreaseMonkey で今見ているページのキーワードクラウドをページの一番上に付加するスクリプトなんてのを書いてみました。

このような感じで表示されます。ちょっと楽しげ？
Yahoo の形態素解析には uniq というオプションがあり、これを指定しておくと単語の出現頻度情報が得られます（使用回数を算出の上、多い順に並べて返す）。また、品詞を指定してフィルタリングもしてくれるので、実は帰ってきた結果をそのまま出力するだけでキーワードクラウド完成です(笑)。

GreaseMonkey で本文を取得して形態素解析サービスに送っているので、イントラのページなどでも解析できてしまいます。
逆に言えば、極秘のページであっても Yahoo! さんに内容を送ってしまいますので、利用は少々試してみるという範囲にとどめてくださいまし。
というわけで決まり文句ですが「万一本スクリプトでなんらかの被害が生じたとしても、無責任無保証」でお願いします。

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

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

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

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

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

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

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

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

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

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

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