确定文件标识的算法

如何存储一些随机整数r _我 ,并查找字节(r _我 mod n)文件大小在哪里?对于带有头的文件,可以先忽略它们,然后对剩余的字节执行此过程。

如果您的文件实际上非常不同(不仅仅是某个地方的单个字节的差异,而是至少有1%的差异),那么随机选择的字节会注意到这一点。例如,如果字节差为1%,100个随机字节将无法注意到概率为1/e~37%;增加您看到的字节数将使此概率呈指数下降。

使用随机字节的想法是,它们基本上被保证(好吧,从概率上讲)和任何其他字节序列一样好,除了它们 不是 易受其他序列的某些问题的影响(例如,在文件格式中每256字节查看一次,该字节必须为0或其他值)。

更多建议:

• 而不是抓取字节,抓取更大的块来证明寻找的成本。
• 我建议总是查看文件的第一个块左右。由此,您可以确定文件类型等。(例如,您可以使用 file 程序。
• 至少要权衡一下整个文件的CRC之类的东西的成本/收益。它不像真正的加密散列函数那样昂贵,但仍然需要读取整个文件。好处是 将 注意单字节差异。

Bucketing,多个比较层应该在您讨论的文件范围内是最快和可扩展的。

第一级索引只是文件的长度。

第二级是散列。在一定的大小下,它是一个完整的文件哈希。除此之外,是的,我同意你关于抽样算法的想法。我认为可能影响采样速度的问题:

1. 为了避免碰到高度相似或相同的规则间隔的报头,您需要输入一个不一致的数字,例如:素数或连续素数的倍数。
2. 避免可能最终遇到常规记录头的步骤,因此,如果从示例字节中获得相同的值(尽管位置不同),请尝试用另一个质数调整该步骤。
3. 处理具有大量相同值的异常文件,要么是因为它们是未编码的图像,要么只是填充了空值。

做第一个128K,另一个128K在1MB标记处,另一个128K在10MB标记处,另一个128K在100MB标记处,另一个128K在1000MB标记处,等等。随着文件大小变大,并且越来越可能只根据文件大小来区分两个文件,您散列的数据越来越小。128K以下的一切都得到了彻底的照顾。

信不信由你,我在最后一次写入文件时使用了记号。它虽然便宜,但我仍然看到不同文件之间的冲突。

如果您可以放弃Linux共享要求并将自己局限于NTFS,那么NTFS备用数据流将是一个完美的解决方案,它可以:

• 不需要任何类型的散列;
• Renames幸存;以及
• 存活移动(即使在不同的NTFS卷之间)。

你可以多读一些 here . 基本上,您只需为流附加一个冒号和一个名称(例如“:meta”),然后编写您喜欢的内容。因此,如果您有一个目录“d:\movies\terminator”,请使用普通文件I/O将元数据写入“d:\movies\terminator:meta”。如果要保存特定文件(而不是整个文件夹)的元数据,也可以这样做。

如果您希望将元数据存储在其他地方,并且只能够在同一个NTFS卷上检测移动/重命名,则可以使用getfileinformationByhandle API调用(请参阅msdn/en-us/library/aa364952(vs.85.aspx)获取文件夹的唯一ID(将volumeserialnumber和fileindex成员组合在一起)。如果在同一卷上移动/重命名文件/文件夹,则不会更改此ID。

首先,您需要更深入地了解文件系统是如何工作的。您将使用哪些文件系统?大多数文件系统都支持硬链接和软链接,因此“文件名”信息不一定存储在文件本身的元数据中。

实际上,这是一个可堆叠的分层文件系统的全部要点,您可以用各种方式扩展它,比如支持压缩或加密。这就是“Vnodes”的意义所在。实际上,你可以用几种方法来做到这一点。其中一些非常依赖于您所看到的平台。这在使用VFS概念的UNIX/Linux系统上要简单得多。例如,您可以在ext3的顶部实现自己的层,或者实现您拥有的层。

** 看完你的编辑后,你会发现更多的东西。如前所述,文件系统已经使用inode之类的东西来完成这项工作。散列可能是一个坏主意,不仅因为它很昂贵,而且因为两个或多个预映像可以共享同一个映像;也就是说,两个完全不同的文件可以具有相同的散列值。我认为您真正想要做的是利用文件系统已经公开的元数据。当然,在开源系统上,这会更简单。:)

我应该为示例选择哪个字节?

我想我会尝试使用一些算术级数,比如斐波那契数。它们很容易计算,而且密度也在减小。小文件比大文件具有更高的采样率,并且样本仍然会覆盖整个文件中的点。

这项工作听起来可以在文件系统级别更有效地实现,或者使用版本控制系统的松散近似(两者都是?).

为了解决最初的问题,可以为每个文件保留一个数据库(文件大小、哈希字节数、哈希字节数),并尽量减少每个文件大小的哈希字节数。无论何时检测到冲突,您要么有一个相同的文件,要么增加哈希长度以刚好超过第一个差异。

毫无疑问,还需要进行优化,以及CPU与I/O之间的权衡,但对于那些不会有误报的事情来说,这是一个很好的开端。