将相似字符串哈希到同一个哈希值

Question

有没有一种哈希算法可以将相似的文本文档哈希成一个特定的哈希值？

例如，

A =“这是示例文本1” B =“这是示例文本2”

需要将A和B哈希到同一个值。

我已经进行了一些研究并阅读了关于SimHash和LSH算法的文章。 Simhash会导致哈希冲突，并且可以使用汉明距离来定义相似性。

理想情况下，我希望有一种类似于“如果字符串A和字符串B的相似度差异在可接受的阈值范围内（t < tmax），则将A和B哈希到相同的哈希值”。

- thickblood

---

我不确定是否有一种方法。我记得在某个“好的哈希函数属性”文章中读到过，其中之一的属性是类似的值不会产生相似的哈希值，因此数据中的任何结构相似性（这在现实生活数据中很常见）都不会反映在哈希中，因此项目可以均匀地分布在哈希表中。 - Tom

嗨Tom，是的，一个好的哈希属性是不会产生相似的哈希值。但是有些算法专门设计来引起碰撞。SimHash算法就是其中之一的例子。 - thickblood

Answer 1

一个明显的选择是使用Soundex或其变体之一（取决于这些单词的语言）。

您没有说明您需要这个的原因。

• 如果您需要创建某种哈希表变体，其中将类似的字符串放置在同一个桶中，那么声音编码变体可能有效，但您需要考虑到可能会发生碰撞的可能性。
• 如果您只需要一些关于两个字符串相似程度的指示，您还可以查看称为Simil的算法；请参见this link，或拼写检查相关算法。

- Wernsey

---

是的，基本上我希望做的事情如下：1）将相似项散列到同一个桶中；2）对于来自数据流的新字符串，进行查找，如果找到，则视为近似副本并忽略它们。 - thickblood