1

我想找到一种算法来找到数组中具有最多公共设置位的位串对（在数组中的所有对中）。我知道可以通过比较数组中的所有位串对来做到这一点，但这是 O( n 2 )。有没有更高效的算法？理想情况下，我希望算法通过在每次迭代中处理一个传入的位串来增量工作。

例如，假设我们有这个位串数组（长度为 8）：

B1:01010001 
B2:01101010
B3:01101010
B4:11001010
B5:00110001

这里最好的对是B2and B3，它有四个共同的设置位。

我发现一篇似乎描述了这种算法的论文（S. Taylor & T. Drummond (2011)；“ Binary Histogrammed Intensity Patches for Efficient and Robust Matching ”；Int. J. Comput. Vis. 94:241–265），但我不明白第 252 页的描述：

这可以在每次迭代中增量更新，因为唯一需要重新计算的 [bitstring] 重叠是新父特征的重叠以及根中“最重叠特征”是选择组合的两个特征之一的任何其他 [bitstrings]。这避免了在每次迭代中进行 O(N 2 ) 重叠比较的需要，并允许在一秒钟内构建一个包含 700 个特征的典型大小的数据库的森林。

4

2 回答 2

1

据我所知，Taylor & Drummond (2011) 并没有声称要给出一个 O( n ) 算法来在具有最多公共设置位的数组中找到一对位串。他们草拟了一个论点，即在将新的位串添加到数组（并删除两个旧的位串）后，可以在 O( n ) 中更新最佳此类对的记录。

当然，第 252 页上对算法的解释不是很清楚，我认为他们关于记录可以在 O( n ) 中更新的草图论点充其量是不完整的，所以我明白你为什么感到困惑。

无论如何，这是我从论文中解释算法 1 的最佳尝试。

算法

该算法采用位串数组并构造查找树。查找树是一个二叉森林（二叉树的集合），其叶子是数组中的原始位串，其内部节点是新的位串，如果节点 A 是节点 B 的父节点，则 A & B = A（即即，A 中的所有设置位也都设置在 B) 中。

例如，如果输入是这个位串数组：

位串数组

然后输出是查找树：

查找树

论文中描述的算法如下：

  1. 令R为初始的位串集（根集）。

  2. 对于R中每个在R中没有伙伴的比特串f1，找到并记录它的伙伴（R 中的比特串f2 - {  f1 }与f1具有最大的集合比特数）并记录它们在其中的比特数常见的。

  3. 如果R中不存在具有任何公共设置位的位串对，则停止。

  4. 设f1和f2是R中具有最多公共设置位的位串对。

  5. 让p = f1 & f2成为f1和f2的父级。

  6. 从R中删除f1和f2；将p添加到R。

  7. 转到第 2 步。

分析

假设数组包含n个固定长度的位串。那么所描述的算法是 O( n 3 )，因为步骤 2 是 O( n 2 )，并且有 O( n ) 次迭代，因为在每次迭代中，我们从R中删除两个位串并添加一个。

该论文包含一个论点，即步骤 2 仅在第一次循环时为 Ω( n2 )，而在其他迭代中为 O( n )，因为我们只需要找到p " 的伙伴以及R中的任何其他位串其搭档是被选为组合的两个之一。” 然而，这个论点对我来说并不令人信服：不清楚是否只有 O(1) 其他这样的位串。（也许有更好的论点？）

我们可以通过存储每对位串之间的公共设置位的数量来将算法降低到 O( n 2 )。这需要 O( n 2 ) 额外空间。

参考

  • S. Taylor & T. Drummond (2011)。“用于高效和稳健匹配的二进制直方图强度补丁”。诠释。J.计算机。可见。94：241-265。
于 2012-08-26T20:37:39.320 回答
0

好吧，对于每个位位置，您可以保持两组，即打开该位置的一组和关闭该位置的一组。例如，这些集合可以放置在两个二叉树中。

然后你只需执行集合并集，首先是所有 8 位，然后是 7 的每个组合，依此类推，直到你找到两个元素的并集。

这里的复杂性在位大小上呈指数增长，但如果它很小且固定，这不是问题。

另一种方法可能是将 n k 位字符串视为 kD 空间中的 n 个点，您的任务是找到最接近的两个点。有许多几何算法可以做到这一点。

于 2012-08-26T21:43:47.580 回答