用于索引相似文本的哈希函数

看见 http://en.wikipedia.org/wiki/Locality_sensitive_hashing

对于字符串之间的许多距离函数,您的问题几乎是无法解决的。

edit distance

"AAAA" -> "AAAB" -> "AAABC"

如果我们允许距离为1的一对具有相同的散列值。

更好的方法是找到一个 equivalence relation 在字符串集上,使每个等价类中的每个字符串具有相同的哈希。一种可能性是根据类与预定义字符串的距离来定义类(例如,编辑与“AAAAA”的距离),距离本身就是散列值。也许这种方法在你的例子中不是最好的,但是也许有一些关于这个问题的额外信息,我们可以得到一个更好的等价关系。