用 JavaScript 作 HTML 比較(diff)

為了做到文字比較，我利用『最長共同部分序列』(Longest Common Subsequence)演算法，這是屬於動態規劃演算法的一種，特點就是以空間換速度，在比較過程需要 (m+1)*(n+1) 的記憶體空間，效率是 m*n，m 跟 n 的數量取決於文章的長度與切割的大小，我的切割方式是以空白符號及 HTML tag 作分界，對英文的切割有正向的優勢，所以在中文上就有點糟，但因為切割的長度大效率會比較快。

/*切割文字*/
function toReg(str){
    var array = str.match(/<[^>]*>|[^< ,.\r\n\t]+[ ,.\r\n\t]*/ig);
    result = [];
    for(var i = 0, l = array.length; i < l; i++) {
        if(array[i].charAt(0) == '<') {
            temp = array[i].match(/[^<][^> ]*/i);
            result[i] = {
                txt: array[i],
                tag: temp
            };
        }else{
            result[i] = {
                txt: array[i],
                tag: false
            };
        }
    }
    return result;
}

/*最長共同部分序列*/
function LCS(na, oa){
    var m = na.length, n = oa.length;
    var i, j;
    var d = [];

    /*Dynamic*/
    for(i = 0; i <= m; i++) {
        d[i] = [];
        d[i][0] = 0;
    }
    for(j = 1; j <= n; j++) {
        d[0][j] = 0;
    }

    /*動態規劃演算法*/
    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            if(na[i - 1].txt == oa[j - 1].txt) {
                d[i][j] = d[i - 1][j - 1] + 1;
            }else if(na[i - 1].tag && na[i - 1].tag==oa[j - 1].tag) {
                d[i][j] = d[i - 1][j - 1] + 1;
            }else if (d[i][j - 1] > d[i - 1][j]) {
                d[i][j] = d[i][j - 1];
            }else {
                d[i][j] = d[i - 1][j];
            }
        }
    }

    /*標註共同部分序列*/
    i = m;
    j = n;
    while (i > 0 && j > 0) {
        if(d[i][j] == d[i - 1][j]) {
            i--;
        }else if(d[i][j] == d[i][j - 1]) {
            j--;
        }else{
            i--;
            j--;
            na[i].com = j;
            oa[j].com = i;
        }
    }
    delete d;
}

/*合併比較陣列*/
function merge(na, oa){
    var m = na.length, n = oa.length;
    var result = [];
    if(!m && !n) { return null; }

    var i;
    var oldPrint = 0;
    for(i = 0; i < m; i++) {
        /*有共同的資料*/
        if(na[i].com != undefined) {
            /*有刪除的舊資料*/
            if(na[i].com > oldPrint) {
                var maxRow=(na[i].com < n) ? na[i].com : n;
                for(j = oldPrint; j < maxRow; j++) {
                    if(oa[j].tag) {
                        result.push(oa[j].txt);
                    }else{
                        result.push('<del>' + oa[j].txt + '</del>');
                    }
                }
            }
            /*記錄下一次舊資料的指標*/
            oldPrint = na[i].com + 1;
            /*儲存共同的資料*/
            result.push(na[i].txt);

        /*新的差異資料*/
        }else{
            if(na[i].tag) {
                result.push(na[i].txt);
            }else{
                result.push('<ins>' + na[i].txt + '</ins>');
            }
        }
    }
    return result;
}

展示(demo)