高效地find大集合中汉明距离较低的二进制string

问题：

给定一个大于（〜1亿）的无符号32位整数列表，一个无符号的32位整数input值和一个最大的汉明距离 ，返回在input值的指定汉明距离内的所有列表成员。

列举的实际数据结构是公开的，性能要求决定了内存中的解决scheme，构build数据结构的成本是次要的，查询数据结构的成本低是至关重要的。

例： 

For a maximum Hamming Distance of 1 (values typically will be quite small) And input: 00001000100000000000000001111101 The values: 01001000100000000000000001111101 00001000100000000010000001111101 should match because there is only 1 position in which the bits are different. 11001000100000000010000001111101 should not match because 3 bit positions are different.

我的想法到目前为止：

对于海明距离为0的退化情况，只要使用一个sorting列表并对特定的input值进行二进制search即可。

如果汉明距离只有1，我可以翻转原始input的每一位，重复上述32次。

如何有效地（不扫描整个列表）发现海明距离> 1的列表成员。

问题：我们对海明距离d（x，y）了解多less？

回答：

  1. 它是非负的：d（x，y）≥0
  2. 相同的input只有零：d（x，y）= 0⇔x = y
  3. 它是对称的：d（x，y）= d（y，x）
  4. 它服从三angular不等式 ，d（x，z）≤d（x，y）+ d（y，z）

问题：为什么我们在意？

答：因为这意味着汉明距离是度量空间的度量 。 有度量空间索引的algorithm。

  • 度量树 （Wikipedia）
  • BK树 （维基百科）
  • M-tree （维基百科）
  • VP-tree （维基百科）
  • 封面树 （维基百科）

一般来说，您也可以查找“空间索引”algorithm，知道您的空间不是欧几里得，但它是一个度量空间。 许多关于这个主题的书籍都使用诸如汉明距离之类的度量来覆盖string索引。

脚注：如果您比较固定宽度string的汉明距离，则可以使用assembly体或处理器内在函数获得显着的性能提升。 例如，使用GCC（ 手动 ），你可以这样做： 

 static inline int distance(unsigned x, unsigned y) { return __builtin_popcount(x^y); }

如果你通知GCC你正在编译一台装有SSE4a的计算机，那么我认为应该只减less到几个操作码。

编辑：根据一些来源，这有时/通常比通常的掩码/移位/添加代码更慢。 基准testing表明，在我的系统上，C版本的性能比GCC的__builtin_popcount高出约160％。

附录：我自己对这个问题很好奇，所以我介绍了三种实现：线性search，BK树和VP树。 请注意，VP和BK树非常相似。 BK树中的节点的孩子是树的“壳”，其包含与树中心相距固定距离的点。 VP树中的一个节点有两个孩子，一个孩子包含以节点中心为中心的球体内的所有点，另一个孩子包含所有外面的点。 所以你可以把VP节点想象成一个带有两个非常厚的“shell”而不是许多更精细的节点的BK节点。

结果被捕获在我的3.2 GHz PC上，algorithm不会尝试利用多个内核（这应该很容易）。 我select了100M伪随机整数的数据库大小。 结果是距离1..5的1000个查询的平均值，以及针对6..10的100个查询的平均值以及线性search。

  • 数据库：100M伪随机整数
  • testing次数：距离1..5为1000，距离为6..10为100，线性为100
  • 结果：平均查询命中次数（非常近似）
  • 速度：每秒查询次数
  • 覆盖率：每个查询检查的数据库的平均百分比 
                 -  BK树 -   -  VP树 -   - 线性 - 
 Dist结果Speed Cov Speed Cov Speed Cov
 1 0.90 3800 0.048％4200 0.048％
 2 11 300 0.68％330 0.65％
 3 130 56 3.8％63 3.4％
 4 970 18 12％22 10％
 5 5700 8.5 26％10 22％
 6 2.6e4 5.2 42％6.0 37％
 7 1.1e5 3.7 60％4.1 54％
 8 3.5e5 3.0 74％3.2 70％
 9 1.0e6 2.6 85％2.7 82％
 10 2.5e6 2.3 91％2.4 90％
任何2.2 100％

在你的评论中，你提到：

我认为BK树可以通过生成一堆带有不同根节点的BK树来扩展。

我认为这正是VP树比BK树更好的原因。 “更深”而不是“更浅”，它比较多点，而不是用较less的点进行更细致的比较。 我怀疑这种差异在高维空间中更为极端。

最后的提示：树中的叶节点应该是用于线性扫描的整数平面arrays。 对于小组（可能小于或等于1000分），这将更快，更高效地存储内存。

我写了一个解决scheme，我用2 32位的位集表示input数字，所以我可以检查O（1）是否在input中有一定的数字。 然后，对于查询的数字和最大距离，我recursion地生成所有的数字在这个距离，并检查他们对比特。

例如，对于最大距离5，这是242825个数字（ 总和d = 0到5 {32selectd} ）。 为了比较，Dietrich Epp的VP-tree解决scheme例如通过了1亿个数字中的22％，即通过2200万个数字。

我用Dietrich的代码/解决scheme作为基础来添加我的解决scheme，并与他的比较。 这里是速度，每秒查询，最大距离可达10： 

 Dist BK Tree VP Tree Bitset Linear 1 10,133.83 15,773.69 1,905,202.76 4.73 2 677.78 1,006.95 218,624.08 4.70 3 113.14 173.15 27,022.32 4.76 4 34.06 54.13 4,239.28 4.75 5 15.21 23.81 932.18 4.79 6 8.96 13.23 236.09 4.78 7 6.52 8.37 69.18 4.77 8 5.11 6.15 23.76 4.68 9 4.39 4.83 9.01 4.47 10 3.69 3.94 2.82 4.13 Prepare 4.1s 21.0s 1.52s 0.13s times (for building the data structure before the queries)

对于小距离来说，bitset解决scheme是迄今为止最快的。 问题作者Eric在下面评论说，最大的距离可能是4-5。 自然地，我的比特解决scheme对于更大的距离变得更慢，甚至比线性search更慢（对于距离32，它将经过2 32个数字）。 但是对于距离9，它仍然很容易导致。

我也修改了迪特里希的testing。 上述每一个结果都是为了让algorithm解决至less三个查询和尽可能多的查询，因为它可以在大约15秒（我做了1,2,4,8,16等查询，直到至less10秒钟总共通过）。 这是相当稳定的，我甚至得到类似的数字只有1秒。

我的CPU是一个i7-6700。 我的代码（基于Dietrich的）在这里 （至less忽略文件，至less现在不知道该怎么办，但tree.c包含所有的代码，我的test.bat显示了如何编译和运行（我用来自Dietrich的Makefile的标志））。 我的解决scheme的捷径 。

一个警告：我的查询结果只包含一次数字，所以如果input列表包含重复的数字，可能或可能不需要。 有问题的作者Eric的情况下，没有重复（见下面的评论）。 在任何情况下，这个解决scheme对于那些在input中没有重复或者不想在查询结果中或者不需要重复的人来说可能是好的（我认为纯粹的查询结果可能只是一个结束的手段，一些其他的代码将数字转换成其他的东西，例如映射一个数字到一个散列是那个数字的文件列表的映射。

如何sorting列表，然后在这个sorting列表中进行二进制search，以查看您的海明距离中的不同可能值？

您可以在指定的汉明距离内预先计算原始列表的所有可能变化，并将其存储在布隆filter中。 这给你一个快速的“不”，但不一定是关于“是”的明确答案。

对于YES，将与bloom中每个位置相关联的所有原始值的列表存储，并一次一个地通过它们。 优化布隆filter的速度/内存折衷的大小。

不知道它是否全部工作正常，但如果你有运行内存的刻录，并愿意花费很长时间进行预计算，似乎是一个很好的方法。

解决这个问题的一种可能的方法是使用不相交集数据结构 。 这个想法是在同一个集合中汉明距离<= k的合并列表成员。 这是algorithm的大纲：

  • 对于每个列表成员计算海明距离<= k的每个可能的值 。 对于k = 1，有32个值（对于32位值）。 对于k = 2,32 + 32 * 31/2的值。

    • 对于每个计算的值 ，testing它是否在原始input中。 您可以使用大小为2 ^ 32的数组或哈希映射来执行此检查。

    • 如果该值在原始input中，则使用列表成员执行“联合”操作。

    • 保持在一个variables中执行的联合操作的数量。

您使用N个不相交的集合（其中N是input中元素的数量）开始algorithm。 每次执行联合操作时，都会减less1个不相交组的数量。 当algorithm终止时，不相交集数据结构将具有所有具有海明距离<= k的值分组在不相交集合中。 这种不相交集数据结构可以在几乎线性时间内计算。

Interesting Posts