算法进行有效的比较庞大的文件

题

我有储存的两个文件A和B这两者都非常大的(像100GB).但是B很可能是类似的，在大部分这样我就可以存储和差异(A，B)。有两个有趣的方面这个问题：

文件太大，不能进行分析的任何差异的图书馆我知道的因为他们是在存储器
我实际上并不需要一个差的差异通常具有插入、修改和删除，因为它意味着要读通过人类。我可以逃脱下信息：我只需要"新范围的字节"和"副本字节的旧文件，从任意offset"。

我目前正在亏损时如何计算增量从A到B的根据这些条件。任何人都不会知道的一个算法为这个?

再次，问题是简单的：写一个算法，可以储存的文件A和B为几个字节，尽可能给予的事实，两者都颇为相似。

额外信息：虽然大部分可能是相同的，他们很可能有不同的偏移和以出的顺序。最后的事实是，为什么一个传统的差异可能不会节省很多。

解决方案

看看RSYNCs算法，因为它的设计很多工作要做的正是这一点使它可以有效复制的三角洲。和算法是很好的记录，作为我记得。

其他提示

你可以使用 rdiff, ，它工作得很好，大文件。我在这里创造一个比较的两大文件 A 和 B:

创建一个签署一个文件，例如
```
rdiff signature A sig.txt
```
使用所产生的签名的文件 sig.txt 和其他文件，创造delta：
```
rdiff delta sig.txt B delta
```
现在 delta 包含了所有你需要的信息，以重新创造文件 B 当你们两个 A 和 delta.重新B、运行
```
rdiff patch A delta B
```

在Ubuntu，只要运行 sudo apt-get install rdiff 安装它。它是相当快的，我得到大约40MB每秒我的电脑上。我只是试图在一个8GB文件，并将使用的存储器可以通过约1MB.

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

阅读过的文件在块：
- 分的数据的所谓"块".最常用方法被称为"定义的内容分割使用Rabins指纹识别方法"(代码).使用的分块的方法会导致更好地去重复在大多数数据集，然后使用的是静态型的区块(例如示在这里，).
- 指纹块使用一个密码指纹识别方法，例如沙-256.
- 储存的指纹在一的索引和搜索对每个区块如果指纹是已经知道的。如果指纹是已知的，有没有必要存储大块的第二时间。只有当的指纹是不是已知的，该数据将被存储。

这样一个数据删除重复的算法是不确切为如 xdelta, 但它是更快和更可扩展为大型的数据集。该分块和指纹是进行大约50MB/s每个核心(Java)。该索引的大小取决于裁员，大块的大小和数据规模。200GB，它应该适合在内存块大小的，例如16KB。

宾利和Mciloys 压缩的办法非常相似(例如使用通过谷歌大表)，但是我不知道有任何出的命令行工具使用压缩技术。

的 "fs-c" 开放源码项目包含的大多数代码，是必要的。但是，fs-c本身的尝试只有以衡量的冗余和analzye文件存储或使用 Hadoop 集群。

一个问题是是什么记录的大小，在你的文件，即可以抵消更改逐字节或者文件组成的，也就是说，1024B块。假设的数据字节为导向的，你可以做到如下：

创建一个后缀列于文件A。这一系列是一个排列的所有指标数值的文件A。如果一个拥有2^37字节后的指标阵列是最简单表示的64位整数，因此每个字节(偏向文件)相当于8个字节中的指标阵列，所以指标阵列将2^40字节长。E.g。800GB。你也可以指数只有每1024th位置，比方说，降低大小的指标阵列。然后，这detoriates质的包装如何根据长期的平均运行的可复制的碎片。
现在，那么，贪婪地组的文件B你开始，从其开始在偏o=0然后使用的指标阵列中找到最长相匹配，在一个相匹配的数据开始，'o'。你输出的对于包装的文件。这需要在你的情况没有任何编码16字节，因此，如果运行 < 16字节你真的失去了空间。这个可容易地得到补救使用那位级别的编码和使用位的标记，以标记，你是否编码一个孤立的字节(标记+8位=9位)或偏/长对(标有+40位+40位=81位)，说。包装后最长的片段至o、增加o到下一个字之后的分段和重复，直到结束文件。

建造和使用中的后缀阵列是容易的，你应该找到参考容易。在高速应用人使用后缀树木或缀试图替代，这是更为复杂的操纵而更快地提供查找。在你的种情况下你会有阵在次级存储和如果运行的速度的装阶段不是一个问题的后缀列应该是足够的。

根据你的表现要求，你可以摆脱采样的区块，你的指纹，并增长他们时，他们相匹配。这样，你不需要运行一个检验和在整个大文件。

如果你需要任意字节的路线和你真的关心表现，看看 simhash 算法, ，并用它来寻找类似的但不对齐块。

许可以下： CC-BY-SA 和归因