使SIM卡哈希（局部敏感的哈希）算法更准确？

Question

我有两个名称和一个地址的“记录”（基本上是CSV字符串）。我需要找到彼此相似的记录：基本上的名称和地址部分看起来都“相似”，就好像它们是由人解释的一样。

我使用了这篇出色的博客文章中的想法： http://knol.google.com/k/simple-simhashing# 写一个简单的simhash。如果两个或多个字符串的Simhash的结果相同，我将此子集的所有记录都传递给了一个细粒度的匹配程序，该程序是O（n^2），将集合的每个记录与其他所有记录进行比较。

对于Simhash部分，我有参数，可以在其中定义数据报大小（基本上是字符串上的大小为n的滑动窗口）以及用于确定我需要用于Simhash计算的迭代次数（随机）哈希。到目前为止，数据报大小为4，并使用4个哈希来计算Simhash。我尝试了其他各种组合，但是到目前为止，这是最佳结果。

我遇到的问题是，该方法在我拥有的数据集中发现了约80％的重复项。我之所以知道这一点，是因为我已经验证了上面提到的痛苦慢的O（n^2）完整匹配的整个数据集。对于小于10^4的数据集，o（n^2）匹配器是可以的，但是很快就变得不可行，因为我需要运行大小10^8的集合。

关于我如何提高Simhash的准确性的任何想法，建议或想法，因此更多的“类似”记录被标记为具有相同的Simhash号码吗？

编辑：在Simhashing之前，我大写并删除全部！[0-9A-Z]字符。应该匹配的事物的示例（拼写错误是故意的）：

---

• 约翰·史密斯（John Smith）
• 约翰尼·史密斯（Johnny Smith），123 Any Stret
• WONEWHOWENTOWENTEWNE ZIP ROBERT PARKER，442街442号

---

这里的1和2相似，3不。输出应为：1 + 2

Answer 1

在您尝试幻想和更改模拟哈希之前，您是否尝试过将特定于域知识应用于问题？

您是否有算法错过的列表？他们有什么共同点吗？

您是否尝试过诸如删除资本化，将昵称转换为全名，删除中间名，扩展N，E，S，W和North，South，South，East，West，扩展ST等街道等的事情？

Answer 2

（我将以下评论放在以下评论中，但还没有代表。）

您最终要做什么？查找所有重复项？您如何定义重复项？案例敏感性很重要吗？类似的措辞？

我对您的行为有些困惑 - 找到相似的记录并创建一个集合，但是后来o（n^2）检查我认为的完全平等。如果您要检查确切的平等，那么这似乎会打败找到类似记录的目的（除非您将其用作O（n^2）的过滤器来节省时间。

一些随机的想法：通过一种试图将每个记录转换为最通用形式的消毒剂（如果您在乎 / Tike Tiges），将每个记录运行。

如果您感兴趣的是确切的平等，而内存不是限制，但是您正在寻找速度，则可以为每个记录创建一个Java对象。为每个记录定义.equals（）（您可以始终自定义此操作以不做精确的平等）。然后，您需要为此对象定义一个hashCode（）。然后，您可以将每个记录贴在标签中。

所得的标签将没有重复（由您的.equals（） / .hashcode（）实现定义）。

或者，如果您想找到重复项，则在添加到标签之前，请检查是否首先包含记录，如果有记录 - 然后找到重复。

此实现将非常快，但是可能会使用大量内存，因为您将整个数据集存储在内存中。替代方案是为每个记录创建一个哈希，然后将其存储在标签中，并检查每个记录的均等范围。

为每个记录做哈希的缺点是开发具有良好分布的好哈希一代的挑战，然后当然还有哈斯，您必须担心与碰撞的误报。但是，如果您的哈希算法是牢固的，那么碰撞的机会应该很少，以至于您不应该真正担心。

关于哈希的一些想法，您可以做的是所有领域串联的MD5一样简单的事情。您可以进行检查。或者，您可以获取每个字段的哈希码的总和。我不是一个超级数学天才，所以我不能告诉你哪个具有最好的分销行为，因此导致碰撞的可能性最小。如果您决定走这条路线，可能值得研究。

Answer 3

Simhash不是为此目的的合适算法，因为它仅对 近乎检测 其中差异非常小，大量特征是相同的。查看我的教程 Simhash并解决锤距离问题.

更好的方法是 Minhash，可能与LSH一起. 。看起来您的Hashing On功能似乎最好是作为带状疱疹 人物 （约为4的长度），而不是 字.

鉴于如此短的文本字段，并且鉴于单词订单可能不太可能发生太大变化，您应该考虑终止带状疱疹：从文本字段的开始和结尾从包含比正常字符数少的文本字段的木瓦，再加上一个终止标记。这往往更容易在短期文本中拼写差异，例如“惠特莫尔”和“惠特莫尔”而不终止带状疱疹会产生

惠特，hitm，itmo，tmor，更多]和[惠特，hite，item，temo，emor，更多]，低jaccard相似性为2/9；

而包含终止的带状疱疹，这些都会产生

#W，＃WH，＃WHI，WHIT，HITM，ITMO，TMOR，MORE，ORE＃，RE＃，E＃]和[#W，＃WH，＃WHI，WHI，WHIT，HITE，HITE，hite，item，temo，temo，emor，更多，矿石＃，re＃，e＃]，较高的jaccard相似性为8/15;

Rob Neuhaus关于预分级的建议非常明智。我会将长格式的单词标准化为他们的缩写（例如，“圣詹姆斯街”将标准化为“圣詹姆斯圣”）。有时歧义的缩写（“ st” - >“ sethe”或“ saint”？）可能很困难，并且缩写形式会导致较少的带状疱疹，从而对整体相似性产生较小的影响，从而对整体相似性产生较小的影响很好，因为人们经常将“街道”等“道路”误认为，而且不会改变含义。