我想找到一个算法，在一个数组中找到一对位串，这对位串具有最大数量的公共设置位（在数组中的所有对中）。我知道通过比较数组中的所有对位字符串可以做到这一点，但这是o（n2）。有没有更有效的算法？理想情况下，我希望算法通过在每次迭代中处理一个传入的位字符串来递增地工作。
例如，假设我们有这个位字符串数组（长度为8）：
B1:01010001
B2:01101010
B3:01101010
B4:11001010
B5:00110001
这里最好的一对是
B2和B3，它们有四个公共设置位。我发现了一篇描述这种算法的论文（S.Taylor&T.Drummond（2011）；“Binary Histogrammed Intensity Patches for Efficient and Robust Matching”；Int.J.Comput维斯。94:241-265），但我不理解252页的描述：
这可以在每次迭代中递增地更新，因为需要重新计算的唯一[bitstring]重叠是新父特征的重叠，以及根中“最重叠特征”是两个选择用于组合的特征之一的任何其他[bitstring]这避免了在每次迭代中进行o（n2）重叠比较的需要，并允许在一秒钟内为一个通常大小的700个特性的数据库构建一个林。
最佳答案
据我所知，taylor&drummond（2011）并没有给出一个o（n）算法来寻找一个数组中具有最多公共集位的一对位串。它们勾画了一个参数，即在向数组中添加新的位字符串（并删除两个旧的位字符串）之后，可以在O（n）中更新此类最佳对的记录。
当然，第252页对算法的解释不是很清楚，我认为他们关于记录可以在o（n）中更新的粗略论证充其量是不完整的，所以我可以理解你为什么感到困惑。
不管怎样，这是我从论文中解释算法1的最好尝试。
算法
该算法采用一个位字符串数组并构造一个查找树。查找树是一个二进制林（一组二进制树），其叶子是数组中的原始位串，其内部节点是新位串，如果节点A是节点B的父节点，则A&B=A（即A中的所有设置位也都在B中设置）。
例如，如果输入是这个位字符串数组：
然后输出是查找树：
本文所描述的算法如下：
设R为位字符串的初始集（根集）。
对于r中没有伙伴的每个位串f1，查找并记录它的伙伴（r中的位串f2具有与f1相同的最大设置位数），并记录它们具有的共同位数。
如果r中没有一对具有任何公共设置位的位字符串，请停止。
设f1和f2是r中具有最大公共设置位的一对位串。
设p=f1&f2为f1和f2的父代。
将f1和f2从R中移除；将p添加到R中。
转到步骤2。
分析
假设数组包含n个固定长度的位字符串然后所描述的算法是o（n3），因为步骤2是o（n2），并且有o（n）个迭代，因为在每次迭代中，我们从r中移除两个位字符串并添加一个位字符串。
本文中的一个论点是，步骤2仅在循环的第一次中是Ω（n2），而在其他迭代中是o（n），因为我们只需要在r中找到p“的伙伴以及r中的任何其他比特串，其伙伴是为组合而选择的两个比特串中的一个。”O（1）其他此类比特串（也许有更好的论据？）
我们可以通过存储每对位串之间的公共集位数，将算法降到o（n2）。这需要O（N2）额外空间。
参考
S.Taylor和T.Drummond（2011年）。”用于有效和稳健匹配的二元历史编程强度贴片”。内景J.计算。维斯。94:241-265。
关于algorithm - 查找具有最大公共(public)置位位数的一对位串，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12122416/