背景
许多游戏策划使用Excel来配置数值。策划需要保存所有版本的数值表，有时需要查看两个数值表有何差异，有时想把差异或者叫修改应用到另一张数值表中，这非常类似于版本控制，但是市面上的版本控制系统svn和git都是针对文本文件，不能用于Excel的版本控制
Excel比对算法
一维数据比对算法
假设有两个序列和，我们可以通过对A序列进行一些列操作，使之变为B序列。对每种操作都定义个Cost，如何找到总Cost最小的使A变为B的操作序列，可以通过动态规划解决。这是一个已经被广为研究的算法问题，本文就不再整述，读者可以在网上搜索Edit编辑距离获取更多信息。
操作集合的定义有多种方式，一种较为常见的操作集合定义如下(Cost均为1) :
- 在序列中插入一个元素:
- 在序列中删除一个元素;
比如，将字符串kiten变换为sitting，需要删除k，插入s，删除e，插入i，在尾部插入g。如果在原序列和目标序列中去掉删除和插入的元素，那么原序列和目标序列就是完全相同的了(比如上面的例子两者都变为itn了)，因此这种编辑距离被命名为LCS (Longest Common Subsequence) 编辑距离。LeetCode 1143. 最长公共子序列
再回到本文要讨论的差异比较问题，要比较两个序列的差异，实际上就是要找到二者之间尽量多的公共部分，剩下的就是差异部分，所以这和最短编辑距离问题是完全等价的。
此外，除了LCS编辑距离之外，还有一种常用的编辑距离，允许插入、删除和修改操作，叫做Levenshtein编组距离。另外，还可以定义一种广义的Levenshtein编辑距离，删除元素和插入元素;的Cost由一个单参数函数决定，记为Cost()或Cost(); 将修改为;的操作的Cost由一个双参数函数决定，记为Cost2()。
/**
* 比对的基本单位是单个字符
* @param text1 字符串1
* @param text2 字符串2
* @return levenshteinDP数组
*/
static int[][] levenshteinDP(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
// dp[i][j]表示从text1[0...i-1]到text2[0...j-1]的最小编辑距离（cost）
dp = new int[len1 + 1][len2 + 1];
// path记录此方格的来源是多个此类枚举值的布尔或值
path = new int[len1 + 1][len2 + 1];
for (int i = 0; i < len1 + 1; i++) {
dp[i][0] = i;
path[i][0] = FROM_INIT;
}
for (int j = 0; j < len2 + 1; j++) {
dp[0][j] = j;
path[0][j] = FROM_INIT;
}
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
path[i][j] = FROM_INIT;
int left = dp[i][j - 1] + 1;
int up = dp[i - 1][j] + 1;
int leftUp;
boolean replace;
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
leftUp = dp[i - 1][j - 1];
replace = false;
} else {
leftUp = dp[i - 1][j - 1] + 1;
replace = true;
}
dp[i][j] = Math.min(Math.min(left, up), leftUp);
if (dp[i][j] == left) {
path[i][j] |= FROM_LEFT;
}
if (dp[i][j] == up) {
path[i][j] |= FROM_UP;
}
// 对应：两字符完全一样或者可以修改成一样
if (dp[i][j] == leftUp) {
if (replace) {
path[i][j] |= FROM_LEFT_UP_REPLACE;
} else {
path[i][j] |= FROM_LEFT_UP_COPY;
}
}
}
}
return dp;
}
同样的，对于广义Levenshtein编辑距离，如果去掉删除和插入的元素，那么两个序列中剩下的元素即为一一对应的关系，每组对应的两个元素，要么是完全相同的，要么前者是被后者修改掉的。从这部分论述中我们不难看出，比较算法的核心思路实际上就是找到元素与元素之间的一一对应关系
二维数据比对算法
Excel的一个分页可以认为是一个二维数据阵列，阵列中的每个元素是对应单元格内容的字符串值。根据前面的论述，比较两个二维阵列的核心就是找到他们公共的行/列，或者说原阵列和目标阵列的行/列对应关系。比如，对于下面两张表:
甲表的第1、2、3列对应乙表的1、2、4列，甲表的1、3行对应乙表的1、2行。那么这两张表的差异通过下列方式描述:
- 在第2列的位置插入新列
- 删除第2行
- 将(原表中) 第3行第3列的元素从9修改为0;
如何计算两张表对应的行/列，一个比较容易想到的方案是将其拆分为两个独立求解的问题，计算对应的行和计算对应的列。对于前者，我们可以把阵列的每一行当成一个元素，所有行组成一个序列，然后对这个序列进行比较:后者亦然。这样我们就把二维比较问题转化成了一维比较的问题。关于编辑距离的定义，可以采用广义Levenshtein编辑距离，定义删除、插入元素的Cost为该行(列)的元素数，定义修改元素的Cost为这两行(列)之间的LCS编辑距离.于是两个二维阵列的比较过程如下:
找到二者对应的 (或者叫公共的) 行/列，非公共的行/列记为删除、插入行/列操作；两张表只保留公共的行/列，此时他们尺寸完全相同，对应位置的单元格逐一比较，如果值不相同，则记为单元格修改操作;
算法优化
上一个部分介绍的二维阵列比较方案只是一个理论上可行的方案，在实际应用中，存在以下问题:
- 删除、插入行/列的操作都是对于整个行/列的，而计算两行/列之间的LCS编辑距离是独立计算的，因此算法本身有一定不合理性;
- 计算修改Cost里又包含了LCS编辑距离的计算，二层嵌套，性能开销比较大;
针对上述问题，从游戏开发的实际应用场景出发，做了如下优化:
首先计算列之间的对应关系，只取表头前h行(不同项目表头行数h可能不同，可以通过参数配置) ，这样就把对整列的LCS编辑距离计算优化为h个单元格逐已比较，大幅优化了效率，而且对准确度基本不会有什么影响;
根据上一步的计算结果，去掉非公共的列(即删除、添加的列)，这样，剩下的列都是两边一一对应的了，此时再计算行的对应关系，修改操作的Cost定义就可以从LCS编辑距离改为单元格的逐一比较了，这样又大幅优化了性能
在上面所述基础之上，还可以再做优化，因为在实际应用中，绝大多数情况下，绝大多数行都不会有修改，因此可以先用LCS编辑距离对所有行的对应关系进行计算，即只有当两行内容完全相同时才会被当做是对应的; 然后再把剩下的未匹配的行分组用广义Levenshtein编辑距离进行对应关系匹配。这样么做的原因是LCS编辑距离比广义Levenshtein编辑距离的求解速度要快很多。
功能扩展
在开发过程中，我们经常会将单行或者连续若干行单元格上移或下移到另一位置，按照目前的比较逻辑，该操作会被认为是删除这些行，然后在新的位置重新插入这些行。这样的结果和不合理的。为此，我们可以引入一种新的操作: 移动行到另一位置。加入了这个新的操作之后，我们依然可以建立之前所述的行对应关系，只不过两边行的顺序可以是乱序的。这种不保序对应关系可以通过多个轮次的编辑距离匹配计算，每次匹配之后去掉匹配上的行，剩下未匹配的行组成一个新的序列进行下一轮的匹配。每轮匹配是采用LCS编辑距离还是广义Levenshtein编指距离可以灵活决定，比如前若干轮或者行数较多时采用LCS编辑距离，后面的轮次再用广义Levenshtein编辑距离。
