寻找一组比特串的基的算法？

Question

这是我在编写C++的一个差异工具中的内容。

我有一个由n个字符集{"a", "abc", "abcde", "bcd", "de"}（从k = 5个不同字母的字母表中取出）组成的列表。我需要一种方法来观察整个列表可以通过字符集{"a", "bc", "d", "e"}的析取构建。也就是说，"b"和"c"是线性相关的，每对其他字母都是独立的。

在位操作版本中，上述字符集表示为{10000、11100、11111、01110、00011}，我需要一种方法来观察它们都可以通过OR运算从较小的集合{10000、01100、00010、00001}的位串构建而来。

换句话说，我认为我正在寻找{0,1}^k中n个不同位向量的“离散基础”。这篇论文声称一般问题是NP完全的……但幸运的是，我只需要解决小规模的情况（k <32）。

我可以想到一些非常愚蠢的算法来生成基础。例如：对于k²个字母对中的每一个，尝试通过O（n）搜索证明它们是相关的。但我真的觉得有一种高效的位操作算法，只是我还没有偶然发现它。有人知道吗？

编辑：最终我并不真正需要解决这个问题。但我仍然想知道是否有一个简单的位操作解决方案。

- Quuxplusone

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的评论进行编辑

- Bernhard Barker

---

我喜欢它！虽然我实际上没有看到与并查集的联系，我习惯于最初将每个“顶点”分配给其自己的不同“组件”，而不是全部分配到同一组。此外，我认为避免在main []中使用0不仅仅是为了减少混淆：如果所有main []值都是0，那么它们将保持为0直到结束。最后，更清晰的说法应该是“main [i] + =前一次迭代中的主要最大值”。 - j_random_hacker

Answer 2

你可以在牺牲空间的代价下，将愚蠢算法的步骤合并。

创建一个名为 violations 的比特向量，长度为 (k - 1) k / 2 比特（例如，k = 32 时长度为 496）。对字符集进行单次遍历。对于每一对字母，查找违规情况（即对这些字母的位进行异或运算，将结果与 violations 中相应位置的值进行或运算）。完成之后，取反并读出剩余内容。

- phs

Answer 3

您可以尝试使用主成分分析。有一些PCA的变种是专门为二进制或更一般地为分类数据设计的。

- mitchus

---

谢谢您的建议，但我不需要繁琐的理论；我已经知道如何在大约20行代码和嵌套的for循环中找到答案。我的问题只是是否有更聪明、更简短、不那么嵌套的方法来解决它。 - Quuxplusone

Answer 4

由于有人将其显示为NP完全问题，对于大词汇表，我怀疑你不会比整个可能性集合O((2^k-1) * n)的暴力搜索（可以进行各种修剪）更好。至少在最坏情况下，可能一些启发式方法会像你链接的论文中概述的那样在许多情况下有所帮助。这是将您的“愚蠢”方法推广到所有可能的基础字符串而不仅仅是长度为2的基础的方法。

然而，对于小词汇表，我认为这样的方法会更好：

1. 你的单词是否不相交？如果是，那么你就完成了（像“abc”和“def”这样的独立单词的简单情况）

2. 对每对可能的单词执行按位与操作。这给您一个初始的候选基础字符串集合。

3. 转到步骤1，但是不使用原始单词，而是使用当前的基础候选字符串

之后，您还需要包括任何不是最终接受的候选项子集的单个字母。也许还有其他一些次要的簿记工作，例如未使用的字母（使用所有可能的单词进行按位或运算）。

考虑您的简单示例：

第一次遍历会给你a、abc、bc、bcd、de、d

第二次遍历会给你a、bc、d

记账会给你a、bc、d、e

我没有证明这是正确的，但我认为直觉上至少是朝着正确的方向。优势在于使用单词而不是暴力方法使用可能的候选项。对于足够大的单词集，这种方法会变得很糟糕，但对于词汇量多达几百甚至几千的词汇表，我敢打赌它会非常快速。好处是即使k的值非常大，它仍然有效。

如果您喜欢这个答案并且愿意奖励它，我很乐意尝试用20行代码解决它 :) 并提出更有说服力的证明。我认为这很容易做到。

- davec

---

重新评论一下，这个算法可能不完全正确，因为它无法区分 {"ab", "a", "f", "g"} 和 {"ab", "a", "fg"}。在这两种情况下，第一次遍历都会得到 a；记录会给出 a,b,f,g；但是第二种情况的正确答案实际上是 a,b,fg。 - Quuxplusone

我认为像修改簿记这样的东西，将“包括原始单词的任何子字符串，这些子字符串不是最终接受候选项的子集”或类似的内容可能会起作用。就像我说的，我真的不想花时间来完善它并在没有赏金的情况下证明它 :) 无论如何，Dukeling的方法要好得多。好问题。 - davec