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

Question

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

7

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

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

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

我最初使用前缀Trie，但在处理模式字符*和?时遇到了困难。

- Raj

你如何解决匹配规则冲突，是否像最长前缀匹配一样？例如，如果有两个规则：JBoss:* 和 *:*，JBoss:key=value将匹配这两个规则。您会选择最长的匹配规则吗？ - kyun

嗨 Kyun，你是对的，我会选择最长的匹配。 - Raj

3个回答

0

我相信你想要使用一个绳子

- Woot4Moo

0

你可以看一下这个帖子：高效的数据结构用于通配符单词查找

或者这个网站：通配符查询

第二个网站以“因此，我们可以使用两个B树处理包含单个*符号的通配符查询，即普通B树和反向B树。”结束。

这可能对你来说有些过于复杂，但是阅读一下可能是值得的。

祝你好运

- alexbt

您也可以使用其他库，例如Lucene来存储和索引这些值。 - alexbt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kyun · Accepted Answer

我认为最简单的方法是构建一个类似于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格式时，所有这些似乎都是有道理的。希望这有所帮助。