用于查找一组位字符串的基的算法

Question

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

我有一个n字符集的列表{"a"、"abc"、"abcde"、"bcd"、"de"}（取自k=5个不同字母的字母表）。我需要一种方法来观察整个列表可以通过字符集{"a"，"bc"，"d"，"e"}的析取来构建。也就是说，"b"one_answers"c"是线性相关的，并且每隔一对字母是独立的。

在比特旋转版本中，上面的字符集表示为{100001110011101000011}，我需要一种方法来观察它们都可以通过将来自较小集合{100000110001000001}的比特串进行"或"运算来构建。

换句话说，我相信我正在寻找{0,1}^k中一组n不同比特向量的"离散基"。本文认为一般问题是NP完全问题。。。但幸运的是，我只是在寻找小案例的解决方案（k<32）。

我能想出非常愚蠢的算法来生成基础。例如：对于k²对字母中的每一个，尝试证明（通过O（n）搜索）它们是依赖的。但我真的觉得有一种高效的比特处理算法，我只是还没有偶然发现。有人知道吗？

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

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

Answer 2

您可以以空间为代价组合愚蠢算法的通过。

制作一个名为violations的位向量，其长度为(k - 1) k / 2位（因此，k = 32为496位）。对字符集进行一次遍历。对于每一个和每一对字母，查找冲突（即XOR是这些字母的位，OR是violations中相应位置的结果。）完成后，取反并读出剩余的值。

Answer 3

您可以尝试主成分分析。有一些PCA是为二进制设计的，或者更一般地为分类数据设计的。

Answer 4

由于有人将其显示为NP完全，对于大型人声，我怀疑你会比对整个可能性O（（2^k-1）*n）进行强力搜索（可能进行各种修剪）做得更好。至少在最坏的情况下，在许多情况下，一些启发式方法可能会有所帮助，正如你链接的论文中所概述的那样。这是你的"愚蠢"方法，推广到所有可能的基字符串，而不仅仅是长度为2的基。

然而，对于小型人声，我认为这样的方法会做得更好：

1. 你的话不连贯吗？如果是这样的话，你就完成了（像"abc"one_answers"def"这样独立单词的简单情况）

2. 对每对可能的单词执行逐位和。这将为您提供一组初始的候选基字符串。

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

之后，你还需要包括任何不是最终接受的候选人子集的个人信件。也许还有其他一些小的预订，比如未使用的字母（使用比特或所有可能的单词）。

考虑您的简单示例：

第一次通过给你一个，abc，bc，bcd，de，d

第二个通行证给你一个，bc，d

记账给你一个，bc，d，e

我没有证据证明这是正确的，但我认为直觉上这至少是朝着正确的方向发展的。优点在于使用单词，而不是暴力使用可能的候选者。如果有足够大的单词集，这种方法会变得很糟糕，但对于几百甚至几千个的词汇来说，我敢打赌它会很快。好的事情是，即使k的巨大价值，它仍然可以工作。

如果你喜欢这个答案，我很乐意尝试用20行代码来解决：），并提出更令人信服的证据。对我来说似乎非常可行。