我有两个名字和一个地址的“记录”(基本上是CSV字符串)。我需要查找彼此相似的记录:基本上，名称和地址部分看上去都“相似”，好像它们是由人解释的一样。
我使用了这篇出色的博客文章中的想法:http://knol.google.com/k/simple-simhashing#编写了一个简单的SimHash。如果两个或多个字符串的SimHash结果相同，则将该子集的所有记录传递给O(n ^ 2)的细粒度匹配程序，该程序将集合的每个记录与其他每个记录进行比较。
对于SimHash部分，我有一些参数可以定义数据报的大小(基本上是字符串上大小为n的滑动窗口)以及用于确定SimHash计算需要使用的(随机)哈希值的迭代次数。 。到目前为止，数据报大小为4，并使用4个散列来计算SimHash。我尝试了多种其他组合，但是到目前为止，这种组合产生了最佳效果。
我遇到的问题是该方法在我拥有的数据集中发现了大约80％的重复项。我知道这一点是因为我已经针对上述令人痛苦的缓慢O(n ^ 2)完全匹配验证了整个数据集。 O(n ^ 2)匹配器对于小于10 ^ 4的数据集是可以的，但是由于我需要运行大小为10 ^ 8的集合，因此很快变得不可行。
关于如何提高SimHash准确性的任何想法，建议或想法，以便更多的“相似”记录都用相同的SimHash编号标记？
编辑:
在SimHashing之前，我将所有![0-9A-Z]字符大写并删除。
应该匹配的示例(拼写错误是故意的):
这里1和2是相似的，3不是。输出应为:1 + 2
最佳答案
在尝试花哨并更改sim哈希之前，您是否尝试过将特定于域的知识应用于问题？
您是否有算法遗漏对的列表？他们有什么共同点吗？
您是否尝试过删除大写字母，将昵称转换为全名，删除中间名，扩展N，E，S，W以及北，南，东，西，将st扩展到街道等操作？