/
算法

局部敏感的散列

11. 07. 2022

Obsah článku

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

Související články

1.
5.