本地敏感哈希实现？

Question

在C / C ++ / Java / C＃中是否有相对简单易懂（易于实现）的局部敏感哈希示例？

我想了解更多有关此概念的信息，因此想在几个文本文件上尝试实现只是为了了解其工作原理，因此我不需要任何高性能或任何内容……仅是哈希示例对于相似的输入返回相似的哈希值的函数。我可以通过后面的例子从中学到更多。:)

Answer 1

对于字符串，您可以使用近似匹配算法。

• 产生随机字串
• 对于所有字符串，使用http://www.dotnetperls.com/levenshtein之类的算法计算它们与该随机共享字符串的距离

如果字符串与参考字符串等距，则它们很可能彼此相似。然后您就可以对字符串进行局部敏感哈希实现。

您可以为一定距离范围创建不同的哈希桶。

编辑： 您可以尝试字符串距离的其他变体。一个更简单的算法只会返回“否”。两个字符串之间的共同字符。