我熟悉SimHash和MinHash的LSH(Locality Sensitive Hashing)技术.SimHash使用余弦相似性而不是实值数据.MinHash计算二元向量的相似度.但我不能决定使用哪一个更好.
我正在为一个网站创建一个后端系统,以查找半结构化文本数据的近似副本.例如,每条记录都有标题,位置和简短的文字说明(<500字).
除了特定的语言实现,哪种算法最适合绿地生产系统？
是否有一个哈希函数，输入的微小变化会导致输出的微小变化？例如，类似：
hash("Foo") => 9e107d9d372bb6826bd81d3542a419d6
hash("Foo!") => 9e107d9d372bb6826bd81d3542a419d7 <- note small difference
我有两个名字和一个地址的"记录"(基本上是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]字符.应该匹配的事情的例子(拼写错误是有意的):
这里1和2是相似的,3不是.输出应为:1 + 2
我目前正在创建一个程序，该程序可以计算文本文档（+5000个文档）的语料库中的近似重复分数。我正在使用Simhash来生成文档的uniq足迹（由于这个github repo）
我的数据是：
data = {
1: u'Im testing simhash algorithm.',
2: u'test of simhash algorithm',
3: u'This is simhash test.',
}
这给了我3个哈希，像这样：
00100110101110100011111000100010010101011001000001110000111001011100110101001101111010100010001011001011000110000100110101101110
00001001110010000000011000001000110010001010000101010000001100000100100011100100110010100000010000000110001001010110000010000100
10001110101100000100101010000010010001011010001000000000101000101100001100100000110011000000011001000000000110000000100110000000
现在，如何比较这三个哈希值？我知道我必须将它们分成多个块，但是没有确切的方法吗？
我想要做的是输出所有重复的文档（> 70％）及其ID和重复文档的ID。
有人可以帮忙吗？