c# - 局部敏感哈希实现？

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开， visit the help center寻求指导。

关闭 10年前。

在 C/C++/Java/C# 中有没有相对容易理解(并且易于实现)的局部敏感哈希示例？

我想了解更多关于这个概念的信息，所以想在几个文本文件上尝试一个实现，只是为了看看它是如何工作的，所以我不需要任何高性能或任何东西......只是一个例子一个散列函数，它为相似的输入返回相似的散列。之后我可以通过示例从中学到更多。 :)

Answer 1

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

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

如果字符串与引用字符串等距，那么它们很可能彼此相似。这样你就有了一个字符串的局部敏感哈希实现。

您可以为一系列距离创建不同的哈希桶。

编辑:您可以尝试其他的字符串距离变化。一个更简单的算法只会返回 no。两个字符串之间的公共(public)字符。