哈希函数，在相同的桶中散列相似的字符串

Question

我在找一个“坏”散列函数： 我想散列字符串并在一个桶中放入类似的字符串。

你能给我一个暗示从哪里开始我的研究？ 一些方法或算法名称...

Answer 1

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

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

实施例：

• 可以创建10桶（0到9） 和组琴弦通过他们的长度 模10

• 使用一个的strcmp（）像功能和组他们通过与定义的字符串的差异

Answer 2

你的问题是不是一件容易的事。两个想法：

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

这有点类似于jpeg压缩的功能：扔掉细节并留下重要的东西。如果你有两个几乎相同的图像，并且你用jpeg压缩它们，你通常会得到相同的输出。

pHash使用类似于此的方法。

再次，这将是一个相当复杂的方式来做到这一点。

设想二：最小哈希

为最小哈希的想法是，你选择一些标记，很可能是相同的，当输入是相同的。然后计算所有标记输出的矢量。如果两个输入具有相似的矢量，则输入相似。

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

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

这也可能是你的问题矫枉过正。