c++ - 查找与无符号 vector 的所有部分匹配

Question

对于我的一个 AI 项目，我需要将适用于其部分组件的所有规则应用于分解状态。这需要非常频繁地完成，所以我正在寻找一种尽可能快的方法。

我将用字符串描述我的问题，但真正的问题与无符号整数 vector 的处理方式相同。

我有一堆像这样的条目(长度为 N)，我需要以某种方式存储它们:

__a_b
c_e__
___de
abcd_
fffff
__a__

我的输入是单个条目 ciede，我必须尽快找到与之匹配的所有存储条目。例如，在这种情况下，匹配将是 c_e__ 和 ___de。应该支持删除和添加条目，但我不在乎它有多慢。我想尽可能快的是:

for ( const auto & entry : matchedEntries(input) )

正如我所说，我的问题是每个字母实际上是一个无符号整数，并且 vector 的长度未指定(但已知)。我对条目的存储方式或与条目相关联的元数据类型没有任何要求。匹配所有的朴素算法是 O(N)，是否可以做得更好？我需要存储的合理条目数是 <=100k。

我认为某种排序或一些看起来很奇怪的树结构可能会有所帮助，但我似乎无法找到解决此问题的好方法。它看起来也像是文字处理程序已经需要做的事情，所以有人可能会提供帮助。

Answer 1

最简单的解决方案是构建一个 trie包含您的条目。搜索 trie 时，您从根开始并递归地跟随与您输入的字符匹配的边。每个节点中最多有两条边，一条用于通配符 _，另一条用于实际字母。

在最坏的情况下，您必须沿着每个节点的两条边，这将增加 O(2^n) 复杂度，其中 n 是输入的长度，而空间复杂度是线性的。

另一种方法是预处理条目，以允许进行线性搜索。这基本上就是编译正则表达式所做的。对于您的示例，请考虑以下与您所需的输入匹配的正则表达式:

(..a.b|c.e..|...de|abcd.|fffff|..a..)

这个表达式可以实现为 nondeterministic finite state automaton ，初始状态具有 ε-移动到每个单个条目的确定性自动机。然后可以使用标准 powerset construction 将该 NFSA 转换为确定性 FSA .

虽然这种构造可以大大增加状态的数量，但可以在线性时间内搜索输入词，简单地模拟确定性自动机。

下面是条目 ab、a_、ba、_a 和 __< 的示例。首先从一个非确定性自动机开始，它在删除 ε-移动并加入等效状态后实际上是该集合的一个 trie。

然后将其变成确定性机器，其状态对应于 NFSA 的状态子集。从状态 0 开始，对于除 _ 之外的每条边，创建下一个状态作为原始机器中状态的并集，可以从任何状态到达当前集合。

例如，当 DFSA 处于状态 16 时，这意味着 NFSA 可能处于状态 1 或 6。在 a 上转换后，NFSA 可以进入状态 3(从 1)、7 或 8(来自 6)- 这将是您在 DFSA 中的下一个状态。

标准构造会保留 _ 边，但我们可以省略它们，只要输入不包含 _。

现在，如果您在输入中有一个单词 ab，您将模拟此自动机(即遍历其转换图)并最终进入状态 238，从中您可以轻松恢复原始条目。