局部敏感哈希实现？

Question

20

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

我想了解更多关于此概念的知识，因此想尝试在几个文本文件上实现它，只是为了看看它是如何工作的，所以我不需要高性能或其他任何东西...只需要一个返回类似输入的相似哈希的哈希函数示例。之后我可以通过示例学习更多知识。:)

- user541686

4个回答

6

此外，至少有一个C++库可以查看其源代码，该库位于此处：http://sourceforge.net/projects/lshkit/

- Teoman Soygul

与 @Mehran 的链接相同的问题，但无论如何感谢您，+1。 - user541686

2

我知道你明确要求使用C/C++/C#，但是这里有一个Python版本的nilsimsa哈希，可能比其他更大的库更容易理解。

- Alec Thomas

+1，这太棒了，我也在学习Python，所以一举两得。谢谢分享！ :) - user541686

2

此外，Hadoop上还有一个Java实现，它在处理文档方面表现良好。

它被称为LikeLike

目前，LikeLike仅支持最小哈希值独立排列。最小哈希值独立排列已应用于Google News的推荐。

- Mehran

谢谢提供链接，但对于我的情况来说似乎有点太复杂了...我正在尝试在理解简单库之前避免使用大型库。 :-) 无论如何，还是谢谢，+1。 - user541686

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Muhammad Hasan Khan · Accepted Answer

9

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

如果这些字符串与参考字符串的距离相等，则它们很可能彼此相似。因此，您可以为一系列距离创建不同的哈希桶。

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

- Muhammad Hasan Khan

+1 看起来正是我正在寻找的，我会再仔细看一下。非常感谢！ :) - user541686

2

@Hasan：我有点困惑...字符串“abcd”和“xyzw”距离随机字符串“6pGO”都是4，但它们完全不同。这是怎么回事？（对于长度为4的任何随机字符串，距离都是4...） - user541686

1

@Mehrdad 这个算法告诉你需要多少次变换才能将输入字符串转换为参考（随机）字符串。你也可以尝试一个更简单的算法，其中距离是随机字符串和输入字符串之间共同字符的数量。 - Muhammad Hasan Khan

2

@Hasan：是的，我明白算法的作用，但问题在于它根本就不起作用，就像我所展示的那样。你有没有听说过更好的算法？（你刚提到的那个看起来很棒，我会考虑一下的。） - user541686

这样的哈希解决方案对于相似的字符串效果很好，但对于不相关的字符串，它将给出无用的结果。但是，在这种情况下，您没有相似的字符串，因此任何算法都不起作用。在第一种情况下，所有不相关的字符串都将落在哈希码4下，然后您可以维护另一个哈希列表以进一步分解它。 - Muhammad Hasan Khan

显示剩余2条评论