21

在 C/C++/Java/C# 中是否有任何相对易于理解(且易于实现)的局部敏感哈希示例?

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

4

4 回答 4

9

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

如果字符串与参考字符串等距,那么它们很可能彼此相似。你去那里你有一个字符串的位置敏感哈希实现。

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

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

于 2011-04-24T11:02:37.910 回答
6

好吧,这里的 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/

于 2011-04-24T10:45:41.337 回答
2

Hadoop 上还有一个 Java 实现。它在文件方面做得很好。

它被称为LikeLike

目前 Likelike 仅支持 Min-Wise 独立排列。Min-Wise 独立排列应用于谷歌新闻的推荐

于 2011-04-24T13:37:01.750 回答
2

我意识到您明确要求使用 C/C++/C#,但是有一个nilsimsa 哈希的 Python 端口,它可能比其他更大的库更容易理解。

于 2011-05-27T15:57:05.233 回答