ruby - 如何在没有 O^2 问题的情况下找到 Ruby 中一串二进制 bin 的最接近对(汉明距离)？

Question

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

0110101010101010110101010101

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

Mongo 当前不支持此功能。所以，我不得不在应用层做。

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

我有很多内存。而且，在 ruby​​ 中，似乎有一个很棒的 gem(算法)可以创建许多树，但我似乎(还)没有一个可以减少我需要进行的查询数量。

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

任何人的想法都会受到赞赏。

Answer 1

我最终将所有文档检索到内存中……(包含 id 和字符串的子集)。

然后，我使用了 BK Tree比较字符串。