我正在进行一些网络爬虫类的工作，其中我正在查找网页中特定的术语并找到其在页面上的位置，然后将其缓存以供以后使用。我希望能够定期检查页面是否有任何重大变化。像md5这样的东西可以被简单地将当前日期和时间放在页面上来欺骗。
是否有任何适用于这种情况的哈希算法？
有没有一种哈希算法能够容忍细微的差异？
10
- Jason Baker
4
6不，这就是所有哈希算法的关键所在，它们会在输入稍有变化时发生很大的改变。 - halfdan
2@halfdan - 维基百科不同意你的观点。但很遗憾，他们没有提到除声纹识别之外的任何算法。 - Jason Baker
可能是哈希相似性的重复问题。 - Nick Johnson
你能找到什么吗？我正在寻找完全相同的东西。 - alex
4个回答
11
一种常见的文档相似度计算方法是shingling，它比哈希稍微复杂一些。另外，可以了解一下内容定义分块的方法来拆分文档。
我几年前读过一篇关于使用Bloom过滤器进行相似性检测的论文。使用Bloom过滤器优化网络搜索结果。这是一个有趣的想法，但我从未尝试过实验。
我几年前读过一篇关于使用Bloom过滤器进行相似性检测的论文。使用Bloom过滤器优化网络搜索结果。这是一个有趣的想法，但我从未尝试过实验。
- Jim Mischel
3
这可能是使用Levenshtein距离度量的好地方，它量化了将一个序列转换为另一个序列所需的编辑量。
这种方法的缺点是您需要保留每个页面的完整文本以便稍后进行比较。 另一方面，使用基于哈希的方法，您只需存储某种小型计算值，而不需要先前的完整文本进行比较。
您还可以尝试某种混合方法--让哈希算法告诉您已经进行了任何更改，并将其用作触发器，以检索文档的归档副本，进行更严格（Levenshtein）的比较。
这种方法的缺点是您需要保留每个页面的完整文本以便稍后进行比较。 另一方面，使用基于哈希的方法，您只需存储某种小型计算值，而不需要先前的完整文本进行比较。
您还可以尝试某种混合方法--让哈希算法告诉您已经进行了任何更改，并将其用作触发器，以检索文档的归档副本，进行更严格（Levenshtein）的比较。
- Drew Hall
1
对于图片，http://www.phash.org/ 做了类似的事情。基本思路是：模糊图像，转换为灰度图像，执行离散余弦变换，并查看结果的左上象限（重要信息所在）。接下来，记录小于平均值的每个值为 0，大于平均值的每个值为 1。结果对于小变化非常好。
Min-Hashing 是另一个可能的方案。在文本中查找特征并将它们记录为值。连接所有这些值以生成哈希字符串。
对于上述两种方法，使用视点树进行近似匹配搜索。
- Eyal
-4
很抱歉，但哈希算法是精确的。没有一种能够容忍微小差异的。你应该采取另一种方法。
- Rafael Colucci
2
1好的，也许它不会被称为哈希算法。但是似乎没有人对我正在寻找什么感到困惑。只是是否应该称其为哈希算法。 - Jason Baker
我刚回答了你的问题。你问：“有没有一种哈希算法能够容忍轻微的差异？”而我的回答是否定的。也许你应该问另外一件事。 - Rafael Colucci
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接