Data Structure for representing patterns in strings

Question

I'm looking for a good data structure to represent strings of the form:

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

• Each "Domain" can contain the following pattern characters - *, ? (* - 0 or more characters, ? - 0 or 1 character)

• Each "Key" can contain the following pattern characters - *, ? (* - 0 or more characters, ? - 0 or 1 character)

• Each "Value" can contain the following pattern characters - *, ? (* - 0 or more characters, ? - 0 or 1 character)

Examples:

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

If you are familiar with JMX ObjectName's then essentially this is the ObjectName pattern.

I'm looking for ways to easily store a rule corresponding to each pattern and be able to quickly delete,update and add new rules.

I started out by using a Prefix Trie, but got stuck with the pattern characters *, ?.

Answer 1

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

Answer 2

I think the easiest way to do it would be to build an NFA like trie, one which allows transitions to multiple states. This, of course, adds the complexity of having another data structure which maps to multiple states given a set of characters to match. For instance, with your example:

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

Lets say you try to match JBoxx:name=*

When you match the substring JBo, you would need a data structure to hold the states JBo and JB* and * since you have three branches at this point. When the x comes in, you can discard the JBo route since its a dead end and use JB* and *. The easy implementation is to have a set of possible match states at any given time and try the next character on each of them. You would also need a way to resolve multiple matches (as in this case) - perhaps something as simple as a longest match?

It all seems to make sense when you think of the trie as an NFA instead of the well-accepted DFA format. Hope that helps.

Answer 3

I believe you want to use a rope