4

假设我有一系列感兴趣的元素，其中A, B, C...散布着无关符号x。我想从预定义距离内发生的一组预定义有趣组合中识别元素包。符号跨度之间可能存在重叠。例如，在字符串中，如果最大距离为 5 C x x A A x x C，算法将检测到两倍的模式。A A C

例如说我的一组有趣的组合是：

A A C
A B C

我有一个序列：

B A x x C x x x A A x x x C

并且最大跨度为5。

我的算法应该输出：

B A x x C -> A B C

并且将无法识别模式A A C，因为感兴趣的元素之间的跨度大于 5。

我的直觉说这是某种动态编程，但也许它只是我无法发现的知名算法的一个实例。

关于方法/解决方案的任何提示？

4

2 回答 2

2

让我们指定一些名称来描述问题：

m= 数组序列的长度（在您的示例中为 14）
n= 数组序列中唯一元素的总数（在示例中为 3）
k= 每个搜索区域的长度（在示例中为 5）
g= 您正在寻找的组数（2例如）

一种选择是在每个 size 的搜索区域中汇总您的数据k。在您的示例中，如下所示：

{B A x x C}
{A x x C x}
...

我们n为每个部分制作大小向量，第一个元素表示第一种元素的外观，比如A

B A x x C --> [1,1,1] (one appearance of each)
A x x C x --> [1,0,1]

等等。

我们可以为我们正在搜索的组做同样的事情：

{A A C} --> [2,0,1]  
{A B C} --> [1,1,1]

现在问题变得很明显了。假设我们考虑搜索区域的摘要 [3,2,5] 和我们正在搜索的组的摘要 [0,1,2]，我们可以通过认识到我们有第二个元素有 2 个选项，第三个元素有 (5x4)/(1x2) 个选项，所以总共有 20 个选项。

因此对于部分摘要 S，[s 1 , s 2 ,..,s n ] 和单个感兴趣的组 G, [g 1 , g 2 ,...g n ]，我们可以计算总和我们可以从 S 中提取 G 的方法（c++ 样式代码，除了“！”表示阶乘）：

int total_options = 1; // total ways to select G from S
for (int i = 0; i < n; ++i)
{
    if(g[i] == 0)
        continue; // this is an element that doesn't appear in G, so it shouldn't effect our count

    if(s[i] < g[i])
        return 0; // not enough elements in S for G

    for (int d = 1, f = s[i]; f > max(g[i], s[i] - g[i]); --f, ++d)
        total_options = total_options / d * f; // f, d are effectively factorials

    // the previous loop is a more efficient version of:
    // total_options *= (s[i]!) /(g[i]! * (s[i] - g[i])!);
}

return  total_options;

您将为每个部分以及您正在搜索的每个组执行此操作。

时间复杂度：O( · g*m*(k + n))（我们必须k在这里包括，因为最坏情况的阶乘计算）

空间复杂度：O( m + g*n)（我们可以计算每个部分，因此不需要同时存储多个部分）

然后我们可以通过意识到每个连续的“部分”仅通过考虑离开的“尾”元素和进入的“头”元素来改进这一点，所以我们应该计算这两个在我们迭代时如何改变“选项计数”到下一节。我们将通过保持之前的“选项计数”计算来做到这一点，以及 NF（失败次数），即该区域中对于搜索组来说太少的元素数量。诀窍是保持一个正的“选项计数”，仅当 NF 为 0 时才会添加到总数中。这将为您G在迭代 size 的主数组时为每个提供恒定时间的结果m。

时间复杂度：O( g*m + g*n)
空间复杂度：O( g*n + m)

当主数组中的每个元素都是唯一的并且这些元素中的每一个在某些搜索中至少出现一次时，该算法的性能最差（否则我们可以将任何没有出现在任何搜索中的元素都处理相同，例如您的示例中的“x”）。因此，最坏情况的复杂性可以简化为：

时间复杂度：O( g*m)
空间复杂度：O( g*m)

我看不出如何获得更好的时间复杂度，但我很想知道是否有聪明人能想出一种空间复杂度更低的方法。

如果您在仅考虑头部和尾部的恒定时间迭代方面不知道我在说什么，请告诉我，我将用一个示例进行解释。

于 2020-02-10T14:52:34.367 回答
1

  1. 拿出你所有有趣的组合并构建一棵树，这样有趣的组合会产生叶子，而无趣的组合则不会。首先排序，以便与较早符号对应的边更靠近根。

  2. 阅读前五个元素并根据每个元素的出现次数增加频率计数器。

  3. 通过根据频率计数器遍历树来检查最多五个值的子集。如果到达叶子，则发出当前匹配。

  4. 要滑动窗口，请减少与当前最左边的有趣符号关联的计数器，并增加向右滑动后吸入的有趣符号的计数器。

示例 #1：

AAC, ABC => (-)        [B A x x C] x x x A A x x x C
             |         f[A] = 1, f[B] = 1, f[C] = 1
             A         A->B->C, emit ABC
             |
            (-)        B [A x x C x] x x A A x x x C
            / \        f[B]--; A->x; continue
           A   B       
           |   |       B A x x [C x x x A] A x x x C
          (-) (-)      f[A]--; f[A]++; A->x; continue
           |   | 
           C   C       B A x x C x x x [A A x x x] C
           |   |       f[C]--; f[A]++; A->A->x; continue
          (+) (+)

                       B A x x C x x x A [A x x x C]
                       f[A]--; f[C]++; A->x; done

示例 #2：

AAC => (-)             [C x x A A] x x C
        |              f[A]=2, f[B]=0, f[C]=1
        A              A->A->C, emit AAC; continue
        |
       (-)             C x x [A A x x C]
        |              f[C]--; f[C]++; A->A->C; emit AAC; done
        A
        |
       (-)
        |
        C
        |
       (+)

无论窗口大小如何，此解决方案都应该有效，您甚至可以通过将内部节点标记为匹配（不仅仅是叶子）来允许不同大小的有趣组合。这将是输入流中元素数量的线性时间和空间，尽管在有趣组合的数量和窗口大小方面需要一些额外的内存。确切的时间/空间分析留作练习。

于 2020-02-10T14:52:26.630 回答