在 C/C++/Java/C# 中是否有任何相对易于理解(且易于实现)的局部敏感哈希示例?
我想了解更多关于这个概念的信息,所以想在几个文本文件上尝试一个实现,看看它是如何工作的,所以我不需要任何高性能或任何东西......只是一个哈希的例子返回相似输入的相似哈希的函数。之后我可以通过示例从中学到更多。:)
在 C/C++/Java/C# 中是否有任何相对易于理解(且易于实现)的局部敏感哈希示例?
我想了解更多关于这个概念的信息,所以想在几个文本文件上尝试一个实现,看看它是如何工作的,所以我不需要任何高性能或任何东西......只是一个哈希的例子返回相似输入的相似哈希的函数。之后我可以通过示例从中学到更多。:)
对于字符串,您可以使用近似匹配算法。
如果字符串与参考字符串等距,那么它们很可能彼此相似。你去那里你有一个字符串的位置敏感哈希实现。
您可以为一系列距离创建不同的哈希桶。
编辑:您可以尝试其他的字符串距离变化。一个更简单的算法只会返回 no。两个字符串之间的公共字符。
好吧,这里的 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/
我意识到您明确要求使用 C/C++/C#,但是有一个nilsimsa 哈希的 Python 端口,它可能比其他更大的库更容易理解。