局部敏感的散列

大多数文件指纹散列函数的原理是，它们对每一个输入总是返回相同的输出。这被称为决定性的行为。同时，输入的微小变化将导致输出的巨大变化（有效地返回一个完全不同的哈希值）。当我们想检查输入文件是否有变化时，这一点特别有用，如果有变化，我们就会得到完全不同的东西。这种函数的一个例子是MD5或SHA1。

如果我们想从哈希值中推断出原始输入的内容，没有简单的方法，我们别无选择，只能对每个选项进行暴力破解，直到我们得到一个命中。这是因为，由于输出的巨大变化，我们无法通过迭代来确定我们是否正在接近目标。

一些散列函数，如BCrypt，对于相同的输入，每次都会返回一个不同的输出，以使它们对密码散列具有强大的能力。事实上，输出直接包含盐，这使得所谓的字典攻击不可能发生。这个功能只是对密码散列有用，但非常不适合用于文件审查。

文件相似性检查和内容重复搜索

想象一下，我们正在解决一个网络搜索引擎的算法，该算法想要检查一个网页的变化程度。另外，它想快速检查一个页面的文本是否与另一个页面的文本相似，甚至完全重复。

验证的一个方法是将每个页面相互比较，这非常消耗系统资源。另一个选择是计算SHA1散列值，但这是对整个文件内容的散列，如果页面只改变了一个字符，我们就会得到一个不同的散列值--所以它不适合这些目的。

因此，一个可能的解决方案是以不同的方式计算文件的不同区域的散列值，然后寻找散列函数输出的变化。

本地敏感散列的原则

我们已经下载了一个网页的HTML代码，我们想为其计算一个哈希值。我们通过一种需要正确配置的算法将文件分成不同的区域（单元）。

我们使用一个共同的算法对每个区域进行独立的散列，并将结果串联成一个单一的字符串。

然后，输出结果可以是，例如，3791744029724361934（这个内容哈希是由Ahrefs工具提供的）。

例如，如果我们知道页眉的内容代表前5个字符，页脚代表最后5个字符，我们就知道字符串的中间代表页面的内容。如果所有页面的页脚内容都发生了变化（例如，网站管理员添加了一个新的链接，更新日期发生了变化，等等），那么当新版本的页面被下载时，只有右侧区域的哈希值中的几个字符发生了轻微变化，我们就知道只有页脚发生了变化，但内容没有变化。因此，我们可以忽略这样的变化，不必翻阅整个网站。

谷歌是如何优化网络抓取的？

互联网机器人需要在他们能够做到的地方进行拯救。网络抓取是非常昂贵的，更新需要花费计算时间。

例如，在观察谷歌的机器人算法的行为时，我观察到它只对内容的巨大变化做出反应。如果页面变化不大，它就会以正常方式进行抓取。但是，比如说，当一个网站的页脚和页眉发生重大变化时，它就会将其评估为重新设计，并一次性浏览网站的大部分内容，以尽快获得新的外观。

它还以类似的方式检测跨网站的重复。当一组页面非常相似或有相同的内容时，它们会得到一个非常相似的哈希值，机器人可以用它来快速验证这些文件是否相似，并可以选择规范的那一个，而忽略其他的。

散列函数的实现

在PHP中没有现成的对本地敏感的散列函数的实现。同时，我不知道有哪个免费提供的软件包能很好地实现这一功能。

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt