局部敏感的散列

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

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

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

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

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

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

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

本地敏感散列的原则

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

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

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

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

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

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

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

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

散列函数的实现

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

Jan Barášek     更多关于 作者的信息

作者在布拉格担任高级开发人员和软件架构师。 他设计和 管理着你所知道和 使用的大型网络应用。 自2009年以来,他获得了丰富的经验,并通过这个网站传递给大家。

我很乐意帮助你:

联系我们