是否有针对字符串的哈希函数，使得编辑距离较小(例如，拼写错误)内的字符串会映射到相同或非常接近的哈希值，而不同的字符串往往不会？
最佳答案
一个选项是计算所有 k-mers(长度为 k 的子串)的集合，对它们进行散列并计算最小值。
因此，您将带状疱疹的想法与 minhashing 的想法结合起来。
(重复多次以获得更好的结果，与 LSH 方案一样)
其工作方式是两个字符串具有相同最小哈希值的概率与其 k-mer 集的 Jackard 相似度相同。
k-mer 集的相似性与编辑距离有关(但不相同)。
关于algorithm - 字符串的局部敏感散列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45870962/