位置敏感哈希实现

本文关键字：实现 哈希 位置 | 更新日期: 2023-09-27 17:53:11

在C/c++/Java/c#中是否有相对简单的理解(和简单实现)位置敏感的哈希示例?

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

位置敏感哈希实现

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

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

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

你可以为不同的距离创建不同的哈希桶。

EDIT:您可以尝试字符串距离的其他变化。更简单的算法只会返回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/

在Hadoop上也有一个Java实现。它在文档上做得很好。

叫做likeke

目前只支持最小独立排列。最小独立排列是适用于的建议谷歌新闻

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

相关文章：