math - 故意散列冲突

Question

我正在尝试编写一些代码来执行“模糊哈希”。也就是说:我希望多个输入散列到相同的输出，以便我可以快速轻松地进行搜索等。如果 A 散列为 1，C 散列为 1，那么我很容易发现 A 等价于 C。

设计这样一个散列函数似乎很难，所以我想知道是否有人有过 CMPH 或 GPERF 的经验，可以指导我创建一个会导致这个散列函数的函数。

提前致谢!
斯特凡

@本

在这种情况下， bool 矩阵，但我可以轻松地将它们打包成 64 位整数。输入中的旋转、翻译等无关紧要，需要清除。因此:

000
111
000

相当于

111
000
000

和

001
001
001

(简化)

@Kinopiko

到目前为止，我最好的选择是确定某种“规范”表示和设计代码，当转换达到这样的表示时终止(例如……将所有位打包在底部)。然而，这很慢，我正在寻找更好的方法。我的数据集很大。

@杰森

这两个不会散列到相同的值。

000
010
000

000
011
000

Answer 1

我们拿 SOUNDEX ，作为您可能正在寻找的内容的说明......

它确实散列不同但相似的具有相同值的键

它允许断言实体 A(例如“麦当劳”)可能与实体 C(“MacDonnel”)相同

SOUNDEX 的一大特点是运行良好 在特定域中 (姓名，特定姓氏的名称)并且它利用 规则 与单词的发音相关[在英语中，以及延伸到许多同源语言中]。

您的散列(或者它几乎是一种索引形式？)只有在存在(或可以发现)一组[相对简单的]规则来表达所考虑的项目/记录的“相同性”时，算法才会成功。例如，如果底层数据库与汽车有关，并且“相同”的标准是大小和一般性能，那么散列算法可能应该基于记录中的属性，例如价格(转换为范围)、数量气缸，门的数量，以及估计的汽油里程(也转换为范围)。

简而言之，我希望以上说明 需要根据我们希望与哈希值身份相关联的语义来定制算法 (或接近度......因此看起来越来越像一个索引......)，以及这些语义在来自项目的可用数据中表示。

项目可能在许多非常维度上是相似的。定义这些维度是什么，以及如何将“在”这个维度上的属性用作散列函数的键是一个问题。

关于 CMPH 和 gperf ...
这些是完美的、可选的最小散列函数的实现。这种功能可以让你 防止碰撞 .不是这里需要的(我认为)