我应该使用哪种哈希算法来比较文本片段？

Question

我有大量文本，我需要将它们相互比较以检查它们是否相似。每篇文章长约10000字。
因此，我将预先计算每个哈希值并比较哈希值。

问题是，哪种哈希算法更适合呢？ md5？沙1？ sha256？或者也许是base64？ 或者也许这根本不重要？

我知道即使是单个空格也可以改变哈希值，这对我来说没问题。

Answer 1

使用 zlib.crc32 然后对文本与匹配的哈希值进行文本比较以确保。

Answer 2

哈希什么时候起作用？

散列的作用是减少搜索空间，以便更快地找到等效项。只要有可靠的方法为等价类的所有成员生成单个规范值，它就可以工作。

在等效字符串中选择唯一值

在散列之前，需要将字符串转换为规范值（所有等效字符串中的一种唯一表示形式）。

我知道即使是一个空格也可以改变 a 的值 哈希，我觉得没问题。

对于您的应用程序，这里有可能的规范化函数，仅删除空格：

>>> def canonical(s):
        return ''.join([c for c in s if not c.isspace()])

>>> s = 'the   quick\nbrown\tfox jumped'
>>> t = '  the\tquick   brown  fox  jumped'
>>> canonical(s)
'thequickbrownfoxjumped'
>>> canonical(t)
'thequickbrownfoxjumped'

应用哈希函数

A sha256() 速度很快，几乎没有误报的可能性。

在Python 2中，您可以直接从字符串计算sha256。然而，在Python 3中，字符串必须首先被编码为字节：

>>> from hashlib import sha256
>>> sha256(canonical(s).encode()).hexdigest()
'2c31c202821431b015cb800ab6315289884e87f1ed023abc876915685c620919'
>>> sha256(canonical(t).encode()).hexdigest()
'2c31c202821431b015cb800ab6315289884e87f1ed023abc876915685c620919'

哈希什么时候不起作用？

如果您只想按文本相似性进行分组，则散列效果不佳，因为没有直接的方法来选择代表性元素，并且相似性不是传递关系（a 接近 b 并且 b 接近 c 并不意味着 a 接近 c)。

Answer 3

哈希值基本上只给你一条信息：不同的哈希值=不同的字符串。如果这就是您所需要的，那么任何常规哈希都可以，因为它们对文本更改或多或少同样敏感。

所有不是直接答案的事情

现在来看看那些阻止人们给你公平答案的问题。因为你没有准确说出你需要什么，每个人都被迫对你的问题做出假设，或者只是无法给出正确的答案。

如果您只是想要确认的差异并且可以接受未确认的差异（因为不同的字符串可以具有相同的哈希值，即哈希冲突），那么任何常规哈希码都可以。但因为你说检查相似性，这意味着你想要两件事之一。

相似即平等

如果需要平等，没有任何哈希算法可以保证平等。两个不同的字符串可以生成相同的哈希值。如果您需要更快地进行相等检查，则必须使用压缩或将字符组合为 64 位整数等技巧。

作为伪平等的相似性

如果您使用相似性来过滤掉明显不同的字符串，那么您最好创建自己的算法来快速过滤掉不同的字符串。一个普遍的问题是哈希值是不可逆的，这通常涉及大量的数学计算。

您可能需要哈希，因为它们是将文本一次性转换为单个整数，并且对更改高度敏感，但有更好的算法。混沌理论可以提供帮助，但即使只是

result = result ** (i * text[i])

也非常擅长对变化敏感。

但是由于您的具体用例，使用字符串生成可比较的数字可能不是最好的主意。由于文本如此大，每 1000 个字符仅采样 5 个字符可能会更有效。 （例如，对于这两个数字：“8149154147...”和“4396666666...”，仅比较第一个数字比散列更快。）

如果您了解自己的数据集，则可以存在更优化的解决方案。如果是人类文本，则只需比较第一段即可。我一生中从未见过两个文本具有相同的起始段落。如果由于文本都是基于提示而初始文本通常相同，则可以使用最后一段。如果字符或单词是随机的，那么前 10 个实际上不可能相同。

tl；博士：

哈希值不具有代表性且不可逆，因此在数学上很复杂。创建您自己的“哈希”，但更好的是，使用启发式方法。

附注- 我知道这是一个古老的帖子，我正在破坏它，但我认为这是一个最合理的问题，值得一个实际的答案。