五千年(敝帚自珍)

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

共:💬233 🌺560
全看分页树展 · 主题 跟帖
家园 应该不是简单的分割

我去年和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是树形的等等。这些都可以帮助我们建立这个分割。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河