找到无符号向量的所有部分匹配

Question

对于我的AI项目,我需要将适用于其部分组件的所有规则应用于因式状态.这需要经常进行,所以我正在寻找一种尽可能快的方法.

我将用字符串描述我的问题,但真正的问题与无符号整数向量的工作方式相同.

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

__a_b
c_e__
___de
abcd_
fffff
__a__

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

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

正如我所说,我的问题是每个字母实际上是无符号整数,并且向量具有未指定(但已知)的长度.我没有要求如何存储条目,或者要将哪种类型的元数据与它们相关联.匹配所有的天真算法是O(N),是否可以做得更好？我需要存储的合理条目数<= 100k.

我在想某种排序可能会有所帮助,或者看起来有些奇怪的树状结构,但我似乎无法找到解决这个问题的好方法.它看起来像处理器已经需要做的事情,所以有人可能会提供帮助.

Answer 1

将数据存储在树中，第一层代表第一个元素（字符或整数），依此类推。这意味着在您的示例中，树的深度恒定为 5（不包括根）。此时不要关心通配符（“_”）。只需像其他元素一样存储它们即可。

搜索匹配项时，通过广度优先搜索来遍历树并动态构建结果集。每当遇到通配符时，请为该层的所有其他不匹配的节点添加另一个元素到结果集中。如果没有子节点匹配，请从结果集中删除该条目。

在构建树时，您还应该跳过冗余条目：在您的示例中，__a_b是冗余的，因为每当它匹配时，它__a__也会匹配。