局部敏感哈希实现？

Question

在C/C++/Java/C#中是否有任何相对简单易懂(并且易于实现)的局部敏感哈希示例？

我想更多地了解这个概念,所以想尝试一些文本文件只是为了看看它是如何工作的,所以我不需要任何高性能或任何东西......只是一个哈希的例子为类似输入返回类似哈希的函数.之后我可以通过实例了解更多信息.:)

Answer 1

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

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

如果字符串与参考字符串等距,则很可能它们彼此相似.你去了你有一个字符串的局部敏感哈希实现.

您可以为一系列距离创建不同的散列桶.

编辑:您可以尝试其他字符串距离的变化.一个更简单的算法就是返回no.两个字符串之间的共同字符.

Answer 2

那么在MSDN博客上有一篇很好的文章:http://blogs.msdn.com/b/spt/archive/2008/06/11/locality-sensitive-hashing-lsh-and-min-hash.aspx

还有至少一次C++库,你可以检查这里的源代码:http://sourceforge.net/projects/lshkit/