7

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

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

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

  • 每个“Key”可以包含以下模式字符 - *, ?( *- 0 或多个字符, ?- 0 或 1 个字符)

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

例子：

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

如果您熟悉 JMX ObjectName，那么本质上这就是 ObjectName 模式。

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

*我开始使用 Prefix Trie，但被模式字符,卡住了?。

4

3 回答 3

1

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

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

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

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

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

于 2011-06-17T01:10:04.350 回答
0

You can take a look at this other thread: Efficient data structure for word lookup with wildcards

Or this site: Wildcard queries

The second site ends with "We can thus handle wildcard queries that contain a single * symbol using two B-trees, the normal B-tree and a reverse B-tree.".

This may be over the top for you, but it may be worth the read.

Good luck

于 2011-06-17T12:16:50.423 回答
0

我相信你想用绳子

于 2011-06-17T01:23:36.840 回答