如何在没有O ^ 2问题的Ruby中找到一串二进制二进制文件的最接近的对（汉明距离）？

我有一个包含大约100万个文档的MongoDB。 这些文档都有一个字符串，表示一个1位和0位的256位bin，如：

0110101010101010110101010101

理想情况下，我想查询近二进制匹配。 这意味着，如果两个文件具有以下数字。 是的，这是汉明距离。

Mongo目前不支持此function。 所以，我被迫在应用程序层中完成它。

因此，鉴于此，我试图找到一种方法来避免在文档之间进行单独的汉明距离比较。 这使得时间基本上不可能完成。

我有很多内存。 并且，在ruby中，似乎有一个伟大的gem（算法）可以创建许多树，我似乎没有任何工作（还）可以减少我需要做的查询数量。

理想情况下，我想制作100万个查询，找到接近重复的字符串，并能够更新它们以反映这一点。

任何人的想法将不胜感激。

Answer 1

我最终将所有文档检索到内存中..（带有id和字符串的子集）。

然后，我使用BK树来比较字符串。

Answer 2

汉明距离定义了度量空间 ，因此您可以使用O（n log n）算法找到最接近的点对 ，这是典型的分而治之的性质。

然后，您可以重复应用此选项，直到您拥有“足够”对。

编辑：我现在看到维基百科实际上没有给出算法，所以这里有一个描述 。

编辑2：如果距离小于n没有对，则可以修改算法以放弃。 对于汉明距离的情况：简单地计算你所处的递归水平。如果你没有在任何分支中找到n级的东西，那么放弃（换句话说，永远不要输入n + 1 ）。 如果您使用的是度量标准，其中一个维度上的拆分并不总是产生1的距离，则需要调整放弃的递归级别。

Answer 3

据我所知，你有一个输入字符串X ，你想查询数据库中包含字符串字段b的文档，使得X和document.b之间的汉明距离小于某个小数字d 。

您可以在线性时间内完成此操作 ，只需扫描所有N = 1M文档并计算距离（每个文档需要很少的固定时间）。 由于您只需要距离小于d文档，因此可以在d不匹配的字符后放弃比较; 你只需要比较所有256个字符，如果它们中的大多数匹配。

您可以尝试扫描少于N文档，也就是说， 要比线性时间更好 。

设ones(s)是字符串s的1的个数。 对于每个文档，将ones(document.b)存储为新的索引字段ones_count 。 然后你只能查询一些文件的数量足够接近ones(X) ，特别是ones(X) – d <= document.ones_count <= ones(X) + d 。 Mongo索引应该在这里开始。

如果你想在集合中找到所有足够接近的对，请参阅@ Philippe的答案。

Answer 4

这听起来像某种算法问题。 您可以尝试首先比较具有相似数量的1或0位的那些，然后从那里向下工作。 那些相同的东西当然会名列前茅。 我不认为有大量的RAM会有所帮助。

您也可以尝试使用较小的块。 您可以将其视为32位8位序列而不是处理256位序列吗？ 16个16位序列？ 此时，您可以计算查找表中的差异并将其用作一种索引。

根据您需要匹配的“不同”的方式，您可以只更改源二进制值的更改并执行键控搜索以查找匹配的其他值。