用 JavaScript 作 HTML 比較(diff)

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

原始碼

1. /*切割文字*/ 
2. function toReg(str){ 
3.    var array = str.match(/<[^>]*>|[^< ,.\r\n\t]+[ ,.\r\n\t]*/ig); 
4.    result = []; 
5.    for(var i = 0, l = array.length; i < l; i++) { 
6.        if(array[i].charAt(0) == '<') { 
7.            temp = array[i].match(/[^<][^> ]*/i); 
8.            result[i] = { 
9.                txt: array[i], 
10.                tag: temp 
11.            }; 
12.        }else{ 
13.            result[i] = { 
14.                txt: array[i], 
15.                tag: false 
16.            }; 
17.        } 
18.    } 
19.    return result; 
20. } 
21.  
22. /*最長共同部分序列*/ 
23. function LCS(na, oa){ 
24.    var m = na.length, n = oa.length; 
25.    var i, j; 
26.    var d = []; 
27.  
28.    /*Dynamic*/ 
29.    for(i = 0; i <= m; i++) { 
30.        d[i] = []; 
31.        d[i][0] = 0; 
32.    } 
33.    for(j = 1; j <= n; j++) { 
34.        d[0][j] = 0; 
35.    } 
36.  
37.    /*動態規劃演算法*/ 
38.    for(i = 1; i <= m; i++) { 
39.        for(j = 1; j <= n; j++) { 
40.            if(na[i - 1].txt == oa[j - 1].txt) { 
41.                d[i][j] = d[i - 1][j - 1] + 1; 
42.            }else if(na[i - 1].tag && na[i - 1].tag==oa[j - 1].tag) { 
43.                d[i][j] = d[i - 1][j - 1] + 1; 
44.            }else if (d[i][j - 1] > d[i - 1][j]) { 
45.                d[i][j] = d[i][j - 1]; 
46.            }else { 
47.                d[i][j] = d[i - 1][j]; 
48.            } 
49.        } 
50.    } 
51.  
52.    /*標註共同部分序列*/ 
53.    i = m; 
54.    j = n; 
55.    while (i > 0 && j > 0) { 
56.        if(d[i][j] == d[i - 1][j]) { 
57.            i--; 
58.        }else if(d[i][j] == d[i][j - 1]) { 
59.            j--; 
60.        }else{ 
61.            i--; 
62.            j--; 
63.            na[i].com = j; 
64.            oa[j].com = i; 
65.        } 
66.    } 
67.    delete d; 
68. } 
69.  
70. /*合併比較陣列*/ 
71. function merge(na, oa){ 
72.    var m = na.length, n = oa.length; 
73.    var result = []; 
74.    if(!m && !n) { return null; } 
75.  
76.    var i; 
77.    var oldPrint = 0; 
78.    for(i = 0; i < m; i++) { 
79.        /*有共同的資料*/ 
80.        if(na[i].com != undefined) { 
81.            /*有刪除的舊資料*/ 
82.            if(na[i].com > oldPrint) { 
83.                var maxRow=(na[i].com < n) ? na[i].com : n; 
84.                for(j = oldPrint; j < maxRow; j++) { 
85.                    if(oa[j].tag) { 
86.                        result.push(oa[j].txt); 
87.                    }else{ 
88.                        result.push('<del>' + oa[j].txt + '</del>'); 
89.                    } 
90.                } 
91.            } 
92.            /*記錄下一次舊資料的指標*/ 
93.            oldPrint = na[i].com + 1; 
94.            /*儲存共同的資料*/ 
95.            result.push(na[i].txt); 
96.  
97.        /*新的差異資料*/ 
98.        }else{ 
99.            if(na[i].tag) { 
100.                result.push(na[i].txt); 
101.            }else{ 
102.                result.push('<ins>' + na[i].txt + '</ins>'); 
103.            } 
104.        } 
105.    } 
106.    return result; 
107. } 

/*切割文字*/
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)