string - 是否有可用于查找相似（不一定相等）字符串的散列函数？

Question

我需要的是一个对固定数据大小进行操作的散列函数，显然是出于非安全目的。它需要将相似的字符串映射到相似或相等的散列，换句话说，字符串中的微小变化应该不会对散列产生或非常小的变化。

例如：我的名字是 John，我的名字是 Jon应该具有相同或非常相似的哈希值。 我的名字是 John，你的名字是 Liam应该会产生一些相似的哈希值。 我的名字是约翰，我住在美国应该给出完全不同的哈希值。等等！

是否有用于类似目的的散列函数？

Answer 1

没有可靠的方法来实现这一点。这是由于鸽巢原理；两个短字符串可以“关闭”的方法比两个长字符串要少得多。

但是，有模糊散列的概念，它可能会让你成为其中的一部分。

Answer 2

听起来您正在寻找 Levenshtein 距离（请参阅http://en.wikipedia.org/wiki/Levenshtein_distance）。

有很多不同语言的实现。

Answer 3

我认为在这种情况下，Jacard指数可能会有所帮助。Jaccard 指数是衡量两组相似程度的简单指标。它只是集合的交集大小与集合并集大小的比率。

有一个博客讨论了Jaccard Similarity Index for measure Document Similarity，我发现它更接近您的需求。