有效区分大文件的算法

Question

我必须存储两个非常大的文件A和B(如100GB).然而,B在大部件中可能与A类似,因此我可以存储A和diff(A,B).这个问题有两个有趣的方面:

1. 文件太大,无法通过我所知道的任何差异库进行分析,因为它们位于内存中
2. 我实际上并不需要差异 - 差异通常具有插入,编辑和删除,因为它意味着人类可以阅读.我可以用更少的信息逃脱:我只需要"新的字节范围"和"从任意偏移的旧文件复制字节".

我目前在如何计算在这些条件下从A到B的增量变得茫然.有谁知道这个算法？

同样,问题很简单:编写一个算法,可以使用尽可能少的字节存储文件A和B,因为两者非常相似.

附加信息:虽然大部件可能相同,但它们可能具有不同的偏移并且可能出现故障.最后一个事实是为什么传统的差异可能不会节省太多.

Answer 1

你可以使用rdiff,它适用于大文件.在这里,我创建的两个大文件DIFF A和B:

1. 创建一个文件的签名,例如

   rdiff signature A sig.txt
   

2. 使用生成的签名文件sig.txt和其他大文件,创建增量:

   rdiff delta sig.txt B delta
   

3. 现在delta包含了你需要重新创建文件中的所有信息B,当你有两个A和delta.要重新创建B,请运行

   rdiff patch A delta B
   

在Ubuntu中,只需运行sudo apt-get install rdiff即可安装它.它非常快,我的PC每秒大约40 MB.我刚刚在8GB文件上试过它,rsync使用的内存大约是1MB.

Answer 2

看看RSYNCs算法,因为它的设计非常适合这样做,所以它可以有效地复制增量.我记得,这个算法已经很好地记录了.

Answer 3

这正是称为"重复数据删除"的问题.最常用的方法是:

• 读取块中的文件:
  • 拆分所谓的"块"的数据.最常用的方法称为"内容定义分块使用Rabins指纹识别方法"(代码).使用该分块方法可以在大多数数据集上实现更好的重复数据删除,然后使用静态大小的块(例如,此处显示).
  • 使用加密指纹识别方法(例如SHA-256)对块进行指纹识别.
  • 如果指纹已知,则将指纹存储在索引中并查找每个块.如果指纹已知,则无需再次存储块.只有当指纹未知时,才必须存储数据.

这种重复数据删除算法不像xdelta那样精确,但对于大型数据集来说它更快,更具可扩展性.分块和指纹识别以每个核心约50 MB/s(Java)执行.索引大小取决于冗余,块大小和数据大小.对于200 GB,它应该适合内存,例如16KB的块大小.

Bentleys和Mciloys压缩方法非常相似(例如由Googles BigTable使用),但是我不知道使用压缩技术的任何开箱即用的命令行工具.

该"FS-C"的开源项目中包含最是必要的代码.但是,fs-c本身只会尝试在内存中或使用Hadoop集群测量冗余和analzye文件.

Answer 4

一个问题是文件中的记录大小是多少,即偏移量可以逐字节改变,还是文件包含1024B块.假设数据是面向字节的,您可以执行以下操作:

1. 为文件A创建一个后缀数组.这个数组是文件A的所有索引值的排列.如果A有2 ^ 37个字节,那么索引数组最容易用64位整数表示,所以每个字节(偏移到file)对应索引数组中的8个字节,因此索引数组将长2 ^ 40个字节.例如800 GB.例如,您也可以仅为每个第1024个位置编制索引,以减小索引数组的大小.然后,这取决于可复制片段的平均运行时间长度,从而降低了包装质量.

2. 现在贪婪地打包文件B,从偏头o = 0开始,然后使用索引数组找到A中与"o"开头的数据匹配的最长匹配.您在打包文件中输出该对.这样就可以在没有任何16字节编码的情况下使用,因此如果运行时间<16字节,则实际上会丢失空间.这可以通过使用随后的位级编码并使用位标记来标记是否编码隔离字节(标记+ 8位= 9位)或偏移/长度对(标记+ 40位+ 40位= 81)来轻松解决比特),比方说.在o处打包最长片段后,将o增加到片段后的下一个字节,然后重复到文件末尾.

后缀数组的构造和使用很容易,您应该很容易找到参考.在高速应用程序中,人们使用后缀树或后缀尝试,这些操作更复杂但提供更快的查找.在您的情况下,您将在二级存储上安装阵列,如果打包阶段的运行速度不是问题,则后缀数组应该足够了.