最长公共子序列（LCS）到git diff

发表于 分类于 阅读次数：

当宿命从你门前走过的时候，芸芸众生总是显得那么渺小

0x00 LCS

最长公共子序列跟最长不降子序列以及最长公共字串都不是一回事。这种用搜索时间复杂度太高的问题一般都会选择用DP来解决。状态转移方程为：

$$c[i,j] = \begin{cases}
0, & i=0 \text{ or } j=0
\\ c[i-1,j-1]+1, & x_i =y_j
\\ max(c[i-1,j],c[i,j-1]), &x_i \neq y_i
\end{cases}$$

然后我们顺手就可以写出伪代码：

1
2
3
4
5
6
7
memset(c,0)
for i=1->len(x)
  for j=1->len(y)
    if x[i]==y[j]
      c[i,j]=c[i-1,j-1]+1
    else
      c[i,j]=max(c[i-1,j],c[i,j-1])

那么问题来了，开个二维数组进行dp实在是太浪费空间了。仔细观察上面的伪代码，i作为最外层循环在循环内部只调用了i和i-1两个数值，所以事实上只需要当前行(i)和前一行(i-1)。这篇文章有一个很优美的解决方案，定义一个2×len(x)的数组，和pre now两个变量作为指针，每一次循环分别交换这两个变量的值。伪码如下：

1
2
3
4
5
6
7
8
9
memset(c,0)
now=1,pre=0
for i=1->len(x)
  for j=1->len(y)
    if x[i]==y[j]
      c[now,j]=c[pre,j-1]+1
    else
      c[now,j]=max(c[pre,j],c[now,j-1])
  swap(now,pre)

通过交换指针的值来实现交换两行数组确实实现了函数的优美。那么还有没有更优的方案了呢。

经过分析，对于pre行，其实也只是使用了第j和j-1列。类系这篇文章我们定义两个变量leftabove, above代替pre行。

1
2
3
4
5
6
7
8
9
memset(c,0)
for i=1->len(x)
  for j=1->len(y)
    if x[i]==y[j]
      c[j]=leftabove+1
    else
      c[j]=max(above,c[j-1])
    leftabove=above
    above=c[j+1]

这样，空间便缩减为了len(x)+2

0x01 diff

现在广泛采用的 diff 算法，也是类似上面所说的 LCS 算法。但为什么对两个超大的文件进行diff依然速度飞快呢？现在的diff基本上采用的是 Eugene Myers 的论文 An O(ND) Difference Algorithm and its Variations 上面写的方法的变种

现在实在看不懂，留个坑回头慢慢写

为了生存你展翅高飞
但是你要学会随波逐流
才能在汹涌的浪尖上从容不迫
否则就是铤而走险，自掘坟墓