Re: WildCard Key
- From: "Igor Tandetnik" <itandetnik@xxxxxxxx>
- Date: Mon, 18 Dec 2006 16:48:22 -0500
Ben <benm5678@xxxxxxxxx> wrote:
I have a std::list that holds a list of disallowed filenames. So when
the client creates a file, the service checks if it's in this list and
if so, it deletes the file. Currently, it's fast and efficient, in a
second, I can check if the key (the filename) exists in the list and
act accordingly if so.
But I have a new need to support filenames based on wildcards. So the
list may contain notepad*.exe and is supposed to block anything that
matches.
Any ideas of an efficient way to do this ?
I'd use a prefix tree aka trie (http://en.wikipedia.org/wiki/Trie) both
for the original problem and for the one with wildcards. It's a little
bit trickier for the latter, as you need to simulate a non-deterministic
automaton, but not much.
So you build your graph as shown in the wiki article mentioned above. In
wildcard case, some edges will be labeled ? or *, in addition to edges
labeled with normal letters. No two edges coming out of the same vertex
have the same label (this is true for ? and *, too). Each pattern traces
a path through the graph (follow edges marked with successive letters of
the pattern): a vertex where such a path ends is called "terminal"
(marked with numbers in wiki article).
You now need to determine whether incoming string "matches" a root of
the tree, following these rules:
1. An empty string matches a terminal vertex
2. A non-empty string xA (that is, a string whose first character is x
and the rest is A) matches a vertex V if there is an edge labeled 'x'
going from V to W, and A matches W
3. A non-empty string xA matches vertex V if there is an edge labeled
'?' going from V to W and A matches W.
4. A string A matches vertex V if there is an edge labeled '*' going
from V to W and some suffix of A matches W.
The beauty of the prefix tree appoach is that the search time is
independent of the number of patterns. In the absence of wildcards, the
algorithm is trivial - you just use the incoming string to trace the
path through the tree by following labeled edges, until you arrive at a
terminal vertex (or not, in which case there's no match). In the
presence of wildcards, you would need to backtrack: first, at any given
vertex more than one rule may apply, and you may need to try them all;
second, labels with * are non-deterministic - just like in your WildCmp
function, you would need to start by assuming * consumes zero
characters, then retry with one, with two and so on. Just as with
WildCmp, you only need to retry the last * you encounter.
An easy optimization: if a pattern has a trailing *, mark the vertex
which the corresponding '*' edge comes out of as "superterminal". Any
string (empty or otherwise) matches a superterminal vertex. Another
optimization would be to collapse any sequence of question marks and
stars that contains at least one star, to a single star.
Igor Tandetnik
.
- References:
- WildCard Key
- From: Ben
- WildCard Key
- Prev by Date: Re: WildCard Key
- Next by Date: Re: WildCard Key
- Previous by thread: Re: WildCard Key
- Index(es):
Relevant Pages
|
