问Algo在文件中查找冗余数据

EN

一种可能是获取文件的大小并对其进行因子分析。例如，如果文件大小为1280，则您知道记录大小为下列之一：

1,2,4,5,8,10,16,20,32,40,64,80,128,160,256,320,640,1280

然后，你可以测试每一个假设，直到你找到一个匹配或用尽的可能性。

当然，这假定文件没有被截断或以其他方式损坏。

这可能不是最有效的方法，但它的编码速度很快，而且可以非常快地完成您的任务。这取决于您的文件有多大，以及您想要这样做的频率。有时，蛮力解决方案是正确的解决方案，即使它不是“最好的”解决方案。

您可以查看后缀树，可以将字符串的所有后缀插入后缀树中，并计算某个子字符串发生的次数，然后执行树遍历并找到答案。

​

​

1. 首先假设记录的长度l为1
2. 通过比较随后所有大小为l的块，检查您的假设是否正确。一旦你发现不匹配就停止。
3. 如果没有发现错配，您就完成了。回去吧。
4. 搜索长度为l的块的下一个匹配项。这给了另一个候选记录长度。如果下一个匹配块开始于索引i (基于零)，则设置l = i并转到步骤2。

如果您知道总是有一个解决方案，您可能会稍微加快步骤2。如果你检查了50%的数据，你可以停止。

注：这个答案假设您正在寻找最短的可能记录。例如，如果您的所有字节都是FF，则可以找到许多其他解决方案，而不是l=1 (例如，只有一个大记录)。

示例：从大小为1的记录开始，在您的例子中是3F。然后通过检查所有后续字节是否也是3F来检查这是否是完整的记录。您可以停止使用下一个字节，因为它不同。现在寻找下一个3F。它发生在索引3(以零为基础)。现在您知道您的记录至少有3个字节长。假设您的记录有3个字节长。检查随后的三个字节块是否与您的记录匹配。完成了！