Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)

Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J

[efcl]

javascriptでdiffを取る。 google-diff-match-patch と条件を同じ「文字単位 diff」にして比べても速度は２～３倍

[TakiTake]

現在のページとGoogle Cacheを単語単位で比較

[decoy2004]

自然文が対象。形態素解析で分かち書きして、単語単位で diff する。Yahoo! の 日本語形態素解析Webサービス を呼び出す。

[mxg]

日本語形態素解析Webサービス後diff

[webmarksjp]

diff

[T-miura]

　形態素解析　のWebサービスあったんだ

[favril]

- diff

[teahut]

>diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例... Yahoo! の 日本語形態素解析Webサービス を呼び出すために、今回も GreaseMonkey スクリプトになっています

[sawat]

O(NP)のアルゴリズムは共通箇所がほとんど無い場合にクソ重くなるので、googleの方は精度を落としてその辺に対応しているのではないかと思う。（憶測）

[bwhr]

diff。Yahoo!形態素API。処理軽減化。

[monjudoh]

Yahoo! の 日本語形態素解析Webサービスを利用した日本語自然文diff

[asiamoth]

色々応用できそうで面白いスクリプト。

[lockcole]

パフォーマンスにも留意したJavascriptのdiff。Greasemonkeyスクリプトで動作を確認できる。アルゴリズムは「An O(NP) Sequence Comparison Algorithm」を利用。

[Malan]

いろいろ使えそう。流石cyboz :)

[irohiroki]

nlp, 自然言語

[khiker]

diff

[HISAMATSU]

形態素解析のサービス＋diff で卒業”制作”くらいにはなりそう。研究にするにはどうしたものかな。

[sakura3942]

形態素解析

[nitoyon]

diff は計算量が多い。形態解析で単語単位にしてから「An O(NP) Sequence Comparison Algorithm」という論文のアルゴリズムで実装。さらに amachang で高速化。

[nettabo]

これは良さげ。diffってけっこう大変なのね。

[mainyaa]

単語単位でDiffを実装するために、Yahoo!の日本語形態素解析Webサービスを利用。

[hiboma]

すげー

[n_shuyo]

なるほどー。\s、漢字/ひらがな、「を」で分離するだけでもっぽいものになるかな。少なくとも文字単位とそれが選択できるとなかなかいい感じですね > 形態素解析はなんちゃってでいいんじゃないか@kazuhooku

[kdaiba]

すごいなこれ

[ZIGOROu]

さすがです！

[kazuhooku]

おもしろい。形態素解析はなんちゃってでいいんじゃないかとこっちでコメントしてみる

[TAKESAKO]

これはすごい → google-diff-match-patchよりも約2～3倍高速かつ精度が高い