c# - 是否有任何算法可以根据某些模式对数组进行分类？

Question

对于数组长度为 5 的简单问题(实际上数组长度可能是 20..)

我有一组预定义模式，例如AAAAB、AAABA、BAABC、BCAAA...。 每个模式与输入数组的长度相同。我需要一个函数，它将任何整数数组作为输入，并返回它匹配的所有模式。 (一个数组可能匹配几个模式)尽可能快。

“A”表示在模式中 A 位置的所有数字都相等。例如。 AAAAA 仅表示所有数字都相等，{1, 1, 1, 1, 1} 匹配 AAAAA。

“B”表示B位置的数字不等于A位置的数字。(即不是A的数字的通配符)代表的数字B 不必相等。例如。 ABBAA 表示第 1、4、5 个数字等于 x，而第 2、3 个数字不等于 x。 {2, 3, 4, 2, 2} 匹配 ABBAA。

“C”表示这个位置可以是任何数字(即数字的通配符)。 {1, 2, 3, 5, 1} 匹配 ACBBA，{1, 1, 3, 5, 1} 也匹配 ACBBA

我正在寻找一种高效的(就比较次数而言)算法。它不一定是最优的，但不应该离最优太差。我觉得它有点像决策树......

一种非常直接但效率低下的方法如下:

• 尝试将每个模式与输入匹配。说 AABCA 反对 {a, b, c, d, e}。它检查是否 (a=b=e && a!=c)。

• 如果模式的数量是n，模式/数组的长度是m，那么复杂度大约是O(n* m)

更新:

请随时为问题提出更好的措辞，因为我不知道如何使问题简单易懂而不会造成混淆。

理想的算法需要某种准备，例如将模式集转换为决策树。这样对于一些特殊的模式集，预处理之后的复杂度可以达到类似 O(log n * log m) 的程度。(只是一个猜测)

一些可能有用的数字:预定义模式集的大小大约为 30。要匹配的输入数组的数量约为 1000 万。

比如说，如果 AAAAA 和 AAAAC 都在预定义的模式集中。然后，如果 AAAAA 匹配，则 AAAAC 也匹配。我正在寻找一种可以识别这一点的算法。

更新2

@Gareth Rees 的回答给出了 O(n) 的解决方案，但假设没有很多“C”。 (否则存储量很大，很多不必要的比较)

我也欢迎任何关于如何处理有很多“C”的情况的想法，例如，对于长度为 20 的输入数组，至少有 10 个“C” “针对每个预定义模式。

Answer 1

这是一个将 O(ⁿ) 准备和存储换成 O(n) 运行时的想法。如果您的数组不超过机器的字长(您暗示 20 将是​​一个典型的大小)，或者如果模式中 C 的出现次数不多，这个想法可能对您有用. (如果这两个条件都不满足，请避免!)

1. (准备步骤，完成一次。)创建字典d 将数字映射到模式集。对于每个模式 p，以及该模式中 C 出现的每个子集 S，令 n 为具有对应于模式中每个 A 以及 S 中每次出现的 C 的设置位的数字。将 p 添加到模式集 d[n]。

2. (每次需要将新数组与模式进行匹配时完成剩余步骤。)创建字典e 将数字映射到数字。

3. 让 j 遍历数组的索引，对于每个 j:

   1. 设 i 为数组中的第 j 个整数。

   2. 如果 i 不在字典 e 中，则设置 e[i] = 0 .

   3. 设置 e[i] = e[i] + 2^{ℓ − j − 1} 其中 ℓ 是数组的长度。

4. 现在 e 的键是数组中的不同数字 i ，值 e[i ] 有一个设置位对应于数组中 i 的每次出现。对于在字典 d 中找到的每个值 e[i]，集合 d 中的所有模式[e[i]]匹配数组。

(注意:在实践中，您将以相反的方式构建位集，并在步骤 3.3 中使用 2^j 而不是 2^{ℓ - j − 1}，但为了说明清楚，我已经用这种方式描述了算法。)

这是一个例子。假设我们有模式 AABBA 和 ACBBA。在预处理步骤中，AABBA转化为数字25(二进制为11001)，ACBBA转化为数字25(二进制为11001)和17(二进制为10001)，对于模式中 C 出现的两个可能子集。所以字典 d 看起来像这样:

• 17 → {ACBBA}
• 25 → {AABBA, ACBBA}

处理数组 {1, 2, 3, 5, 1} 后，我们有 e = {1 → 17, 2 → 8, 3 → 4, 5 → 2}。在 d 中找到值 e[1] = 17，因此此输入与模式 ACBBA 匹配。

处理数组 {1, 1, 2, 3, 1} 后，我们有 e = {1 → 25, 2 → 4, 3 → 2}。在 d 中找到值 e[1] = 25，因此此输入匹配模式 AABBA 和 ACBBA .