我熟悉SimHash和MinHash的LSH(Locality Sensitive Hashing)技术.SimHash使用余弦相似性而不是实值数据.MinHash计算二元向量的相似度.但我不能决定使用哪一个更好.
我正在为一个网站创建一个后端系统,以查找半结构化文本数据的近似副本.例如,每条记录都有标题,位置和简短的文字说明(<500字).
除了特定的语言实现,哪种算法最适合绿地生产系统？
Ben*_*ore 10
Simhash更快(非常快)并且通常需要更少的存储空间,但是对两个文档的不同程度有严格的限制,并且仍然可以检测为重复文件.如果您使用64位simhash(一种常见的选择),并且根据您能够存储的置换表的数量,您可能仅限于汉明距离低至3或可能高达6或7.小汉明距离!您将被限制在检测大多数相同的文档,即使这样,您可能需要仔细调整您选择进入simhash的功能以及您给予它们的权重.
相似的一代由谷歌获得专利,但在实践中它们似乎至少允许非商业用途.
Minhash使用更多内存,因为你通常每个文档存储50-400个哈希值,并且它不像simhash那样具有CPU效率,但是它允许你找到相当遥远的相似性,例如低至5%的估计相似度,如果你想.它比simhash更容易理解,特别是在表的工作方式方面.实现起来非常简单,通常使用带状疱疹,并且不需要进行大量调整即可获得良好的结果.它(据我所知)不是专利的.
如果您正在处理大数据,那么minhash方法中CPU占用最多的部分可能是在您为文档生成minhashes 后,当您在查找表中找到其他文档时哈希值.可能有数十或数十万个文档与它共享至少一个哈希值,你必须清除所有这些文档以找到那些共享例如至少一半哈希值的文档.Simhash在这里要快得多.
正如Otmar在下面的评论中指出的那样,minhash的优化允许您在相似性估计上达到相同的精度,每个文档的哈希值更少.这可以大大减少你必须做的除草量.
编辑:
我现在尝试过superminhash.这是相当快的,虽然我使用单个哈希函数实现minhash 以及用于生成所有其他哈希的位变换对我来说更快.它提供了更准确的jaccard估计,在我测试的某些情况下大约提高了15%(尽管在其他情况下几乎没有差别).这意味着您需要大约三分之一的哈希才能达到相同的精度.在表中存储较少的哈希意味着需要较少的"除草"来识别近似重复项,从而显着提高速度.我不知道任何关于superminhash的专利.感谢Otmar!
| 归档时间： |
|
| 查看次数： |
6657 次 |
| 最近记录： |