10

我有一个 MongoDB，里面有大约 100 万个文档。这些文档都有一个字符串，表示 1 和 0 的 256 位二进制文​​件，例如：

0110101010101010110101010101

理想情况下，我想查询接近二元匹配。这意味着，如果两个文档具有以下编号。是的，这就是汉明距离。

Mongo 目前不支持此功能。所以，我被迫在应用层做这件事。

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

我有很多内存。而且，在 ruby​​ 中，似乎有一个很棒的宝石（算法）可以创建许多树，但我似乎都无法完成（但）这会减少我需要进行的查询数量。

理想情况下，我想进行 100 万次查询，找到几乎重复的字符串，并能够更新它们以反映这一点。

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

4

4 回答 4

6

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

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

于 2012-01-05T19:13:33.350 回答
4

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

然后，您可以重复应用它，直到您有“足够”的对。

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

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

于 2012-01-04T21:18:11.430 回答
2

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

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

您可以尝试扫描少于N文档，即比线性时间更好。

设为stringones(s)中 s 的数量。对于每个文档，存储为一个新的索引字段。然后，您只能查询数量足够接近 的文档，特别是- <= <= + 。Mongo 索引应该在这里启动。1sones(document.b)ones_countones(X)ones(X)ddocument.ones_countones(X)d

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

于 2012-01-04T22:27:48.383 回答
1

这听起来像是某种算法问题。您可以先尝试比较具有相似数量的 1 或 0 位的那些，然后从那里向下处理列表。当然，那些相同的人会脱颖而出。我认为拥有大量 RAM 在这里不会有帮助。

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

根据您希望匹配的“不同”程度，您可以对源二进制值进行置换并进行键控搜索以找到匹配的其他值。

于 2012-01-04T21:20:28.223 回答