diff_heckel.js αテスト中

ブラウザで差分処理をさせてみようと Heckel アルゴリズムで書いた Javascript のコードをαテストしています。
(2011年2月2日) バージョン 0.03へ。クラスにして、テストを追加しました。diff3 も追加。
(7月9日) バージョン 0.02へ。長いプロパティ名を使うのは気持ちが悪いので、行のハッシュ値を計算するように変更しました。
(7月9日) バージョン 0.01へ。出力表示を diff コマンドに近づけ、行番号だけでなく変更行の内容も表示するようにしました。
https://tociyuki.sakura.ne.jp/archive/diff_test.html
https://tociyuki.sakura.ne.jp/archive/diff_heckel.js (ソースコード)
長い文字列を javascript のオブジェクトのプロパティにできるのかどうか不安ですので、αテストをしています。プロパティにする前に文字列を escape していますが、必要ならば escape をハッシュ関数に替えたいと思います。
うまくいかない例を見つけられた方は、コメントでお知らせくださると助かります。ぜひ、お願いします。
これを作った動機は、数日前のアドバイザリ、wiki クローンが大量の差分処理をおこなうことでサーバ資源を消費するという問題でした。Hiki のアドバイザリがわかりやすいので引用します。

http://hikiwiki.org/ja/advisory20060703.html
現在、Hiki が用いている差分取得アルゴリズムは、最大で O(n**2) の計算量を要します。このため、ページの状態によっては、差分を求める処理に極めて長い時間を要する場合があります。

Wiki クローンは、過去の編集履歴を記録するとき、ディスク利用効率を重視して差分を保管する作り方をしているものが多いのですが、現在はハードディスク容量がアップしており、富豪的に全バージョンのドキュメントをそのまま保管しておける時代になりつつあります。全文保管して、ブラウザで差分を計算して表示したらどうでしょうか。
もしくは、ブラウザで差分を取って AJAX で POST してサーバで保管するやりかたもあるでしょう。
どちらにせよ、最大 O(n**2) の処理をサーバでおこなう必要はなくなります。
そのためには、ブラウザで動作する差分ルーチンが必要になりますので、作ってみることにしました。