找到一组位串的基础的算法？

Question

这是我用C++ 编写的diff实用程序.

我有一个n个字符集列表{"a","abc","abcde","bcd","de"}(取自k = 5个不同字母的字母表).我需要一种方法来观察整个列表可以通过字符集{"a","bc","d","e"}的分离来构造.也就是说,"b"和"c"是线性相关的,并且每隔一对字母是独立的.

在bit-twiddling版本中,上面的字符集表示为{10000,11100,11111,01110,00011},我需要一种方法来观察它们都可以通过从较小的集合中对位串进行ORing来构造{10000 ,01100,00010,00001}.

换句话说,我相信我正在寻找{0,1} ^k中一组n个不同位向量的"离散基础" .本文声称一般问题是NP完全...但幸运的是我只是寻找小案例的解决方案(k <32).

我可以想到用于生成基础的非常愚蠢的算法.例如:对于k ²对字母中的每一对,尝试(通过O(n)搜索)证明它们是依赖的.但我真的觉得这是一个有效的比特纠缠算法,我还没有偶然发现.有谁知道吗？

编辑:毕竟我最终不需要解决这个问题.但我还是想知道,如果有是一个简单位变换的解决方案.

Answer 1

我正在考虑一个不相交的集合数据结构，就像打开它的头部的联合查找（我们不是组合节点，而是拆分它们）。

算法：

创建一个数组main，将所有位置分配给同一组，然后：

for each bitstring curr
  for each position i
    if (curr[i] == 1)
      // max of main can be stored for constant time access
      main[i] += max of main from previous iteration

然后，所有不同的数字main都是不同的集合（可能使用实际的并查找算法）。

例子：

所以，main = 22222。（我不会使用1组来减少可能的混乱，就像curr使用位串一样）。

curr = 10000
main = 42222 // first bit (=2) += max (=2)

curr = 11100
main = 86622 // first 3 bits (=422) += max (=4)

curr = 11111
main = 16-14-14-10-10

curr = 01110
main = 16-30-30-26-10

curr = 00011
main = 16-30-30-56-40

然后按不同的数字分割：

{10000, 01100, 00010, 00001}

改进：

为了降低增加的速度main，我们可以替换

main[i] += max of main from previous iteration

和

main[i] += 1 + (max - min) of main from previous iteration

编辑：根据 j_random_hacker 的评论进行编辑