在序列中查找元素包的算法

Question

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

我的直觉告诉我这是某种动态规划，但也许它只是我无法发现的一个众所周知的算法的一个实例。

关于 approach/solution 的任何提示？

Answer 1

采用所有有趣的组合并构建一棵树，这样有趣的组合会产生叶子，而无趣的组合不会。首先排序，使对应于较早符号的边更接近根。
读取前五个元素并根据每个元素出现的次数增加频率计数器。
根据频率计数器遍历树，检查最多五个值的子集。如果到达叶子，则发出当前匹配项。
滑动window，将当前最左边的兴趣符号相关的计数器递减，向右滑动后吸取的兴趣符号的计数器递增。

示例 #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
        |
       (+)

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

Answer 2

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

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

一种选择是在大小为 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 个选项。

So for section summary, S, [s₁, s₂,..,s_n]，以及单个感兴趣的组 G，[g₁，g₂，...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因为最坏情况的阶乘计算）

Space复杂度：O(m + g*n)（每个section我们可以边走边计算，所以不需要同时存储多个section）

然后我们可以通过意识到每个连续的 "section" 仅通过考虑离开的 "tail" 元素和进入的 "head" 元素来改进这一点，所以我们应该只计算如何当我们迭代到下一节时，这两个更改 "option count" 。为此，我们将保持之前的 "option count" 计算，以及 NF（数量失败），即区域中对于搜索组来说太少的元素数量。诀窍是保持正数 "option count" 仅当 NF 为 0 时才将其添加到总计中。这将为您提供每个 G 在迭代主数组大小时的恒定时间结果m.

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

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

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

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

如果你不知道我在说什么只考虑头部和尾部的恒定时间迭代，请告诉我，我会用一个例子来解释。

在序列中查找元素包的算法

Algorithm for finding bags of elements in a sequence

algorithm

string-algorithm