主题：【原创】浏览器是怎么变成操作系统的 -- 美人他爹

我去年和data domain的人聊过，他们的领域是用硬盘做差分备份，他们也面对同样的问题：如何在一个文件的两个版本里面找到最小的差异，这样可以帮他们节省空间，在我们这个问题里面，可以节省的是带宽。

他们的做法，貌似是用版本v1的某些字段，在版本v2里面找对应，然后这个查找有窗口，可以对付v2里面的添加删除和修改。和diff的办法差不多，但是我想里面应该有很多的heuristics。

嗯，添一段数学描述。

这个问题如师兄所言，是一个比较两个串的距离的问题：串s1和串s2之间的最短距离diff(s1, s2)。这个问题有经典解法，但是如果串很长，比如数百兆，那么计算起来太困难。

那么我们加入一些heuristics：比如我们知道其实s2是s1的更新，那么其实s2和s1只有有限的差别，其他地方都是一样的。我们就可以用分而治之的办法，也就是说，存在一个对s1和s2的分割D，使得：

D将s1和s2分割成相同数目的段p，每个段长度不同，但是这里面sigma(diff(p1i, p2i)) = diff(s1, s2)

那么我们的目标，就是找到一个分割D',使得这个分割计算出来的diff，最接近D的diff值。

如果再加一些heuristics，我们知道一般的文件都是有内部结构的，我们对于这些结构，可以加以利用，比如mpeg4的文件是分帧的，html/xml是树形的等等。这些都可以帮助我们建立这个分割。