algorithm - 字符串的位置敏感散列？

Question

是否有字符串的散列函数，这样在小的编辑距离内的字符串（例如，拼写错误）会映射到相同或非常接近的散列值，而不同的字符串往往不会？

Answer 1

一种选择是计算所有k-mers（长度的子串k）的集合，对它们进行散列并计算最小值。因此，您将带状疱疹的想法与 minhashing 的想法结合起来。（重复多次以获得更好的结果，与 LSH 方案一样）

它的工作方式是两个字符串具有相同 minhash 的概率与它们的k-mer 集的 Jackard 相似性相同。-mer 集的相似性k与编辑距离有关（但不相同）。