【动态规划：最短编辑路径】的应用：excel diff功能

开篇说明

如果在这里获得过启发和思考，希望点赞支持！对于内容有不同的看法欢迎来信交流。
技术栈 >> java
邮箱 >> 15673219519@163.com

描述

• 在游戏行业中通常使用excel做配表，修改配表是一个频繁的操作。在修改之后，为减少认为的误操作。为此我们需要指定两个版本的配表进行对比功能。
• 本文excel diff不限于游戏行业，适用于任意两个excel直接的对比。

动态规划：最短编辑路径 介绍

• 最短编辑路径，简单的说就是"字符串1"改成"字符串2"需要经过多少步；如字符串"ABC"改成"ADCE"需要如下步骤
  • 1,删除B
  • 2,新增D
  • 3,新增E
    通过以上步骤我们就可以实现：字符串"ABC"改成"ADCE"
• 通过上面的我们可以知道，这些步骤就是两个字符串之间的不同。
• 动态规划-最短编辑路径

实现思路

• 通过上面介绍的字符串"ABC"改成"ADCE"案例，类比到excel就是每一行的删除/新增就可以重任意一个excel表格变成另一个excel表格。其中变化的每一步就是这两个excel的不同之处。
• excel我们可以理解就是可以通过一个二维数组保存数据,这里我们做一个降维操作,把它变成一个一维数组。也就是每一行的数据当作一个元素处理。

实现效果

实现步骤

• 第一步: 读取excel的数据，并且把每一行的数据当作一个元素,整个excel表格的数据可以直接存入一个List中。
• 第二步：写一个方法传入两个List,返回差异List

    @Data
    @AllArgsConstructor
    public static class Row {
        // 格子信息
        private List<Cell> cells;
        // diff + - =
        private String diff;
        // 行号
        private Integer rowNum;
        // 旧行号
        private Integer oldRowNum;
    }
1
2
3
4
5
6
7
8
9
10
11
12

private static List<Row> compareLines(List<Row> lines1, List<Row> lines2) {

        List<Row> differences = new ArrayList<>();
        int[][] LCS = new int[lines1.size() + 1][lines2.size() + 1];

        // 计算LCS矩阵
        for (int i = 1; i <= lines1.size(); i++) {
            for (int j = 1; j <= lines2.size(); j++) {
                if (lines1.get(i - 1).equals(lines2.get(j - 1))) {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;
                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }

        // 从LCS矩阵中提取差异
        int i = lines1.size();
        int j = lines2.size();
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && lines1.get(i - 1).equals(lines2.get(j - 1))) {
                Row row = lines2.get(j - 1);
                row.setDiff("=");
                row.setRowNum(j);
                row.setOldRowNum(i);
                differences.add(row);
                i--;
                j--;
            } else if (j > 0 && (i == 0 || LCS[i][j - 1] >= LCS[i - 1][j])) {// +
                Row row = lines2.get(j - 1);
                row.setDiff("+");
                row.setRowNum(j);
                differences.add(row);
                j--;
            } else { // -
                Row row = lines1.get(i - 1);
                row.setDiff("-");
                row.setRowNum(i);
                row.setOldRowNum(i);
                differences.add(row);
                i--;
            }
        }
        // 翻转差异列表
        List<Row> reversed = new ArrayList<>();
        for (int k = differences.size() - 1; k >= 0; k--) {
            reversed.add(differences.get(k));
        }
        return reversed;
    }
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

• 第三步：compareLines返回的就是excel的diff结果。需要新增那些行，需要删除那些行。就可以由excel1编辑成excel2。

拓展

• 目前上面的实现仅仅diff到行的维度，那么如何实现diff中每个格子的变化。这边需要分情况考虑…
• 最终的两个excel的行数是否发生变化。
• 如果excel1(10行)，变化后的excel(20行),这种目前是没有我没有想到很好的处理到每个格子，只能diff到行。
• 如果excel1(10行),变化后的excel(10行)，可以根据行号相同的行数再次通过compareLines方法找出差异格子，注意这里传入的应该是格子的数据列表。