java - 表示字符串模式的数据结构

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 模式。

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

我从使用前缀树开始，但被模式字符 *、? 困住了。

Answer 1

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

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

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

当你匹配子字符串JBo时，你需要一个数据结构来保存状态JBo和JB*和* 因为此时您有三个分支。当 x 进来时，您可以丢弃 JBo 路由，因为它是死胡同，并使用 JB* 和 *。简单的实现是在任何给定时间都有一组可能的匹配状态，并在每个状态上尝试下一个字符。您还需要一种方法来解决多个匹配项(如本例)——也许像最长的匹配项一样简单？

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