主题:【原创】浏览器是怎么变成操作系统的 -- 美人他爹
我去年和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是树形的等等。这些都可以帮助我们建立这个分割。
- 相关回复 上下关系8
🙂google wave似乎已经在预定这些协同标准了 益者三友 字0 2009-08-27 17:49:23
🙂这是一个caching问题在网络时代的变形 5 美人他爹 字1515 2009-08-27 07:01:47
🙂5点同意,1点存疑 4 邓侃 字1174 2009-08-27 18:08:43
🙂应该不是简单的分割
🙂恩,你的diff patch的方式更好一些。 土豆丝 字0 2009-08-27 18:31:23
🙂谢谢:作者意外获得【通宝】一枚 鹦鹉 字60 2009-08-27 05:58:13
🙂应该是操作系统即浏览器 1 Bozhang 字402 2009-08-21 11:49:17
🙂【原创】【3】 ChromeOS与Android 11 邓侃 字2070 2009-08-20 19:16:45