用于表示字符串中模式的数据结构

Question

我正在寻找一个好的数据结构来表示形式的字符串:

Domain:Key1=Value1,Key2=Value2...

• 每个"域"可以包含以下模式字符 - *,?(*- 0个或更多字符,?- 0或1个字符)

• 每个"键"可以包含以下模式字符 - *,?(*- 0个或更多字符,?- 0或1个字符)

• 每个"值"可以包含以下模式字符 - *,?(*- 0个或更多字符,?- 0或1个字符)

例子:

JBoss:*
*:*
JBoss:type=ThreadPool,*
JBoss:type=Thread*,*
JB*:name=http1,type=ConnectionPool

如果您熟悉JMX ObjectName,那么本质上就是ObjectName模式.

我正在寻找方法来轻松存储与每个模式相对应的规则,并能够快速删除,更新和添加新规则.

我开始使用Prefix Trie,但是我遇到了模式字符*,?.

Answer 1

我认为最简单的方法是构建一个类似 trie 的NFA，它允许转换到多个状态。当然，这增加了拥有另一个数据结构的复杂性，该数据结构在给定一组要匹配的字符的情况下映射到多个状态。例如，以你的例子：

JBoss:*
*:*
JBoss:type=ThreadPool,*
JBoss:type=Thread*,*
JB*:name=http1,type=ConnectionPool

假设你尝试匹配JBoxx:name=*

当您匹配 substring 时JBo，您将需要一个数据结构来保存状态JBo和JB*，*因为此时您有三个分支。当x进入时，您可以放弃该JBo路线，因为它是一条死胡同并使用JB*和*。简单的实现是在任何给定时间都有一组可能的匹配状态，并在每个状态上尝试下一个字符。您还需要一种方法来解决多个匹配（如本例所示） - 也许像最长匹配一样简单？

当您将 trie 视为 NFA 而不是广为接受的 DFA 格式时，这一切似乎都有意义。希望有帮助。