Sam*_*ron 5 filesystems algorithm virtualfilesystem
对于一个开源项目,我在文件系统之上编写一个抽象层.
该层允许我将元数据和关系附加到每个文件.
我希望图层能够优雅地处理文件重命名,并在重命名/移动或复制文件时维护元数据.
为此,我需要一种计算文件标识的机制.显而易见的解决方案是为每个文件计算SHA1哈希值,然后根据该哈希值分配元数据.但是......这真的很贵,特别是对于电影来说.
所以,我一直在考虑一种算法虽然不是100%正确,但绝大多数时候都是正确的,并且很便宜.
一种这样的算法可以是使用文件大小和该文件的字节样本来计算散列.
我应该为样本选择哪些字节？如何保持计算的便宜和合理准确？我知道这里有一个权衡,但性能至关重要.用户将能够处理系统出错的情况.
我需要这个算法适用于非常大的文件(1GB +和小文件5K)
编辑
我需要这个算法来处理NTFS和所有SMB共享(基于Linux或基于Windows),我希望它支持将文件从一个位置复制到另一个位置的情况(存在2个物理副本被视为一个标识).我甚至可能会考虑在需要重新标记MP3的情况下(物理文件已更改,因此我可能每个文件类型都有一个身份提供程序).
编辑2
相关问题:确定文件身份的算法(优化)
在您正在讨论的文件范围内,分层,多层比较应该是最快且可扩展的.
第一级索引只是文件的长度.
第二级是哈希.低于一定大小,它是一个完整的文件哈希.除此之外,是的,我同意你对采样算法的看法.我认为可能影响采样速度的问题:
存储一些随机整数 r i并查找字节 (ri mod n)怎么样，其中 n 是文件的大小？对于带有标头的文件，您可以先忽略它们，然后对剩余字节执行此过程。
如果您的文件实际上非常不同（不仅仅是某个地方的单个字节的差异，而是至少有 1% 的差异），那么随机选择的字节会注意到这一点。例如，字节差异为 1%，100 个随机字节将无法注意到的概率为 1/e ~ 37%；增加您查看的字节数会使该概率呈指数下降。
使用随机字节背后的想法是，它们本质上保证（从概率上来说）与任何其他字节序列一样好，除了它们不易受到其他序列的一些问题的影响（例如，碰巧查看每个字节）文件格式的第 256 个字节，其中该字节必须为 0 或其他值）。
更多建议：
file程序。）