string - 散列函数，对同一桶中的相似字符串进行散列

Question

我正在寻找一个“坏”的哈希函数：我想对字符串进行哈希处理并将相似的字符串放在一个桶中。

你能告诉我从哪里开始我的研究吗？一些方法或算法名称...

score 4 · Accepted Answer

你的问题并不容易。两个想法：

此解决方案可能过于复杂，但您可以尝试傅立叶变换。将您的输入文本视为函数的一系列样本，然后运行傅立叶变换将您的输入转换为频域。低频部分是文本的大致内容，高频部分是微小的变化。

这有点类似于 jpeg 压缩所做的：丢掉细节，只留下重要的东西。如果您有两个几乎相同的图像并且您对它们进行了极大的 jpeg 压缩，那么您通常会得到相同的输出。

pHash 使用与此类似的方法。

同样，这将是一种非常复杂的方法。

第二个想法：minHash

minHash 的想法是，当输入相同时，您选择一些可能相同的标记。然后为所有标记的输出计算一个向量。如果两个输入具有相似的向量，则输入相似。

例如，计算单词“the”在文本中出现的次数。如果是偶数，则为 0，如果是奇数，则为 1。现在计算“数学”一词在文本中出现的次数。同样，0 表示偶数，1 表示奇数。做很多话。

现在你处理所有的文本，每个文本都会给你一个输出，比如“011100010101”或其他什么。如果两个文本相似，那么它们将具有相似的输出字符串，仅相差 1 或 2 位。您可以使用多变量分区树 (MVP) 来有效地搜索输出。

对于您的问题，这也可能是矫枉过正。

score -1 · Accepted Answer

这取决于您所说的“相似字符串”是什么意思？

但是，如果您要寻找这样一个糟糕的，您必须自己构建它。

例子：

2 回答 2