javascriptでdiff実装

高速とされるO(NP)のアルゴリズムをベースに 、javascriptで実装してみた。
[1]E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266 に論文を日本語に訳したものが載っており、参考になりました。
 http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
上記の論文中のコードは「ＳＥＤ Shotest Edit Distance」の値を求めるだけで、
Diffの結果をどう組み立て格納していくかについてと、fpという配列の初期値を
何で埋めればよいのかが分からず、 かなり苦労しました。

アルゴリズムは上記のO(NP)そのままですが、javascriptで実装していく中で、
メイン処理とした親関数内でのループの部分はかなりすっきりさせ、
snakeへのパラメータは整数kを1つだけとする、snakeは値を返さない、等、
サンプルコードの原形はほとんどなくなってしまった感じです。

また、O(NP)はarr1.lengthがarr2.length以下であることが前提なのですが、
最初の段階でパラメータをチェックし、arr1.lengthがarr2.lengthより大きければ、
順番をひっくり返して、自分自身を呼ぶことにより、前提を満たすようにしました。

動くサンプルページ http://www123.ddo.jp/tools/diff.html

//@license http://www.opensource.org/licenses/mit-license.html MIT License
//@author Mashiki
//@see http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
function diff(arr1, arr2, rev) {
    var len1=arr1.length,
        len2=arr2.length;
    // len1 <= len2でなければひっくり返す
    if (!rev && len1>len2)
        return diff(arr2, arr1, true);
    // 変数宣言及び配列初期化
    var k, p,
        offset=len1+1,
        delta =len2-len1,
        fp=[], ed=[];
    for (p=0; p<len1+len2+3; ++p) {
        fp[p] = -1;
        ed[p] = [];
    }
    // メインの処理
    for (p=0; fp[delta + offset] != len2; p++) {
        for(k = -p       ; k <  delta; ++k) snake(k);
        for(k = delta + p; k >= delta; --k) snake(k);
    }
    return ed[delta + offset];

    // snake
    function snake(k) {
        var x, y, e0, o,
            y1=fp[k-1+offset],
            y2=fp[k+1+offset];
        if (y1>=y2) { // 経路選択
            y = y1+1;
            x = y-k;
            e0 = ed[k-1+offset];
            o = {edit:rev?'-':'+',arr:arr2, line:y-1}
        } else {
            y = y2;
            x = y-k;
            e0 = ed[k+1+offset];
            o = {edit:rev?'+':'-',arr:arr1, line:x-1}
        }
        // 選択した経路を保存
        if (o.line>=0) ed[k+offset] = e0.concat(o);

        var max = len1-x>len2-y?len1-x:len2-y;
        for (var i=0; i<max && arr1[x+i]===arr2[y+i]; ++i) {
            // 経路追加
            ed[k+offset].push({edit:'=', arr:arr1, line:x+i});
        }
        fp[k + offset] = y+i;
    }
}