7

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

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

在 bit-twiddling 版本中，上面的字符集表示为 {10000, 11100, 11111, 01110, 00011}，我需要一种方法来观察它们都可以通过将较小集合 {10000 , 01100, 00010, 00001}。

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

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

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

4

4 回答 4

2

我在想一个不相交的集合数据结构，比如联合查找打开了它的头（而不是组合节点，我们拆分它们）。

算法：

创建一个数组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 的评论进行编辑

于 2013-01-06T13:49:27.340 回答
1

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

violations制作一个称为位长的位向量(k - 1) k / 2（因此，496 表示k = 32.）对字符集进行一次遍历。对于每个字母，以及每对字母，查找违规（即XOR这些字母的位，OR将结果放入 中的相应位置violations。）当你完成后，否定并读出剩下的内容。

于 2012-07-18T03:25:05.293 回答
0

你可以试试主成分分析。有一些 PCA 风格是为二进制数据或更普遍地为分类数据设计的。

于 2012-08-30T20:05:25.093 回答
0

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

于 2012-11-26T18:57:32.727 回答