问题标签 [simhash]

是否存在散列函数，其中输入的微小变化会导致输出的微小变化？例如，类似：

有没有人遇到过用Java 实现的simhash函数？

我已经搜索过了，但找不到任何东西。

问题是：我有一组文本文档，我想选择与输入文件最相似的一个。输入的文本文档可以完全匹配或部分修改。该算法必须非常快。

目前，我发现 simhash 从收集文件中获取指纹。有没有其他算法可以做同样的事情？

我有两个名称和一个地址的“记录”（基本上是 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] 字符大写并删除。应该匹配的例子（拼写错误是故意的）：

• JOHN SMITH, 123 ANY STREET Sometown ZIP
• 约翰尼·史密斯，123 岁
• SOMETOWNE ZIP ROBERT PARKER, 442 ANY STREET SOMETOWN ZIP

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

我在使用哈希函数时遇到问题。我必须为文档中的每个单词分配一些数字（128 位或 64 位）。因此，“相似度”的哈希值必须与“相似度”相近。这意味着，如果相似度的值=>10022（比如说），那么相似度=>10025。这应该与相似的词接近。不同名称的哈希值也应该相似。这意味着，“john”的哈希值也应该接近“michel”或“sita”......等等。如果任何人对此有任何想法。

先谢谢了。:)

我想构建一个成对距离矩阵，其中“距离”是两个字符串之间的相似度得分，如此处实现的。我正在考虑使用 sci-kit learn 的成对距离方法来执行此操作，因为我之前已将其用于其他计算，并且易于并行化非常好。

这是相关的代码：

strings看起来像['foo', 'bar', 'baz']。

当我尝试这个时，它会抛出错误ValueError: could not convert string to float。这可能是一件非常愚蠢的事情，但我不确定为什么需要在此处进行转换，以及为什么会抛出该错误：匿名函数 inmetric可以接受字符串并返回浮点数；为什么输入需要是浮点数，如何根据 simhash“距离”创建这个成对距离矩阵？

我对检测相似文档的技术有一个合理的理解，该技术首先计算它们的 minhash 签名（从它们的 shingles 或 n-gram），然后使用基于 LSH 的算法来有效地对它们进行聚类（即避免二次复杂度，这将需要一个简单的成对穷举搜索）。

我正在尝试做的是桥接三种不同的算法，我认为这些算法都与这个 minhash + LSH 框架有关，但以非显而易见的方式：

（1） Mining of Massive Datasets（Rajaraman and Ullman）一书第3章第3.4.3节勾勒的算法，似乎是minhashing的规范描述

(2) Ryan Moulton 的Simple Simhashing文章

（3）Charikar所谓的SimHash算法，本文介绍

我觉得这很令人困惑，因为我假设虽然 (2) 使用术语“simhashing”，但它实际上是以类似于 (1) 的方式进行 minhashing，但关键区别在于集群只能由单个签名表示（甚至可能涉及复杂的多个哈希函数），而两个文档有更多与（1）相似的机会，因为签名可以在多个“带”中发生冲突。(3) 似乎完全不同，因为签名是根据它们的汉明距离进行比较的，而 LSH 技术意味着对签名进行多次排序，而不是对它们进行捆绑。我还看到（在其他地方）最后一种技术可以包含加权的概念，它可以用来更加强调某些文档部分，而这似乎在 (1) 和 (2) 中缺乏。

所以最后，我的两个问题：

(a) 是否有一种（令人满意的）方法可以连接这三种算法？

(b) 有没有办法将权重概念从 (3) 导入到 (1)？

I have the same setup and code on mac for running simhash, it works.

But when I run it on Ubuntu, it complaints the implementation of simhash itself has the bug.

Have you encountered such problem?

objs = [(str(k), Simhash(v)) for k, v in index_data.items()] File "/usr/local/lib/python2.7/dist-packages/simhash-1.1.2-py2.7.egg/simhash/init.py", line 30, in init self.build_by_text(unicode(value)) UnicodeDecodeError: 'ascii' codec can't decode byte 0xf6 in position 34: ordinal not in range(128)

我有这样的数据框：

我想计算字符串距离，例如 apple -> aple 等。我的最终结果在这里：

目前这是我正在使用的代码（但对于大数据来说非常慢）：

谁能帮我有效地计算距离？

我熟悉 SimHash 和 MinHash 的 LSH（Locality Sensitive Hashing）技术。SimHash 在实值数据上使用余弦相似度。MinHash 计算二进制向量的相似度。但我无法决定使用哪个更好。

我正在为网站创建一个后端系统，以查找几乎重复的半结构化文本数据。例如，每条记录都有标题、位置和简短的文本描述（<500 字）。

除了特定的语言实现之外，哪种算法最适合新建生产系统？