寻找一组比特串基础的算法?

我在想一个不相交的集合数据结构,比如 union find 打开它的头(我们不是合并节点,而是拆分它们)。

算法:

创建阵列 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 = 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[i] += max of main from previous iteration

具有

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

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

你可以以空间为代价将愚蠢算法的通过组合起来。

生成一个名为 violations 那就是 (k - 1) k / 2 位长(因此,496表示 k = 32 .)对字符集进行一次遍历。对于每一个和每一对字母,查找违规情况(即。 XOR 那些字母的比特, OR 将结果放入中的相应位置 违规行为 )做完后,否定并读出剩下的内容。

你可以给予 Principal Component Analysis 尝试一下。PCA有一些设计用于 binary 或更一般地 categorical 数据

由于有人将其显示为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行代码来解决:)并提出更令人信服的证据。对我来说似乎非常可行。