MIN-DIFF

一个一百行代码不到的基于动态规划lcs算法的迷你文本比较器
github地址：https://github.com/kimlongli/min-diff

文件1

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function lcs(arr1, arr2) {
    matrix = [];
    for(i = 0; i < arr1.length + 1; i++) {
        matrix.push([]);
        for(j = 0; j < arr2.length + 1; j++) {
            matrix[i].push(0);
        }
    }
    for(i = 1; i < arr1.length + 1; i++) {
        for(j = 1; j < arr2.length + 1; j++) {
            if(arr1[i - 1] == arr2[j - 1]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
            }
            else if(matrix[i - 1][j] >= matrix[i][j - 1]) {
                matrix[i][j] = matrix[i - 1][j];
            }
            else if(matrix[i - 1][j] < matrix[i][j - 1]) {
                matrix[i][j] = matrix[i][j - 1];
            }
            else {
                console.log("unexpected error");
            }
 
        }
    }
 
    return matrix[i - 1][j - 1];
}
                

文件2

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function lcs(arr1, arr2) {
    matrix = [];
    route = [];
    for(i = 0; i < arr1.length + 1; i++) {
        matrix.push([]);
        route.push([]);
        for(j = 0; j < arr2.length + 1; j++) {
            matrix[i].push(0);
            route[i].push([]);
        }
    }
    for(i = 1; i < arr1.length + 1; i++) {
        for(j = 1; j < arr2.length + 1; j++) {
            if(arr1[i - 1] == arr2[j - 1]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
                route[i][j] = [[i - 1, j - 1]].concat(route[i - 1][j - 1]);
            }
            else if(matrix[i - 1][j] >= matrix[i][j - 1]) {
                matrix[i][j] = matrix[i - 1][j];
                route[i][j] = route[i - 1][j];
            }
            else if(matrix[i - 1][j] < matrix[i][j - 1]) {
                matrix[i][j] = matrix[i][j - 1];
                route[i][j] = route[i][j - 1];
            }
 
        }
    }
 
    return route[i - 1][j - 1];
}
                

比较结果

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
  function lcs(arr1, arr2) {
    matrix = [];
+   route = [];
    for(i = 0; i < arr1.length + 1; i++) {
        matrix.push([]);
+       route.push([]);
        for(j = 0; j < arr2.length + 1; j++) {
            matrix[i].push(0);
+           route[i].push([]);
        }
    }
    for(i = 1; i < arr1.length + 1; i++) {
        for(j = 1; j < arr2.length + 1; j++) {
            if(arr1[i - 1] == arr2[j - 1]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
+               route[i][j] = [[i - 1, j - 1]].concat(route[i - 1][j - 1]);
            }
            else if(matrix[i - 1][j] >= matrix[i][j - 1]) {
                matrix[i][j] = matrix[i - 1][j];
+               route[i][j] = route[i - 1][j];
            }
            else if(matrix[i - 1][j] < matrix[i][j - 1]) {
                matrix[i][j] = matrix[i][j - 1];
-           }
-           else {
-               console.log("unexpected error");
+               route[i][j] = route[i][j - 1];
            }
   
        }
    }
   
-   return matrix[i - 1][j - 1];
+   return route[i - 1][j - 1];
  }