Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the same length. These are standard UNIX wildcards; 10??1 matches 10011, 10111, etc -- a ? matches a 1 or a 0 in that position. If $v$ and $w$ are wildcard strings, then we write $v \leq w$ if every string matched by $v$ is also matched by $w$.
The problems: given a set $S$ of wildcard strings, and a query $v$ (also a wildcard string), does there exist a $w \in S$ such that $v \leq w$? And if not, can we add $v$ to $S$ efficiently?
Here's the obvious $O(\frac{k}{m}n)$ solution (where $k$ is the size of the strings, $m$ is the word size of RAM (usually 32 or 64)): go through each element of the list and test the condition (which can be done in 2 or 3 operations using bit-twiddling). Also test if $v \geq w$ holds for any item $w$ while we're scanning. If $v$ fails our test, then add $v$ to the set, and remove the $w$'s we marked.
But that's not fast enough. It'd be really cool if there was a $O(\log n)$ solution, or, in a perfect world, complexity similar to a radix tree ($O(k)$). It's also OK for the queries to be approximately correct: that is, if $v \leq w$, then return yes or no; but if the condition doesn't hold definitely return no.
Although this doesn't help the worst case complexity, you can assume that all elements in $S$ are bounded by a wildcard string; that is, there exists some $v$ such that for all $w \in S$, $v \geq w$.
Ideas I've tried
- Wildcard strings form a join-semilattice. We could have an n-ary tree that holds wildcard strings; the leaves would be wildcard strings, and the branches would represent the join of all of the children. If the query and the join are incomparable, then we don't have to waste time trying to compare with all of the children of that branch. Furthermore, if we make an update, and the update happens to be greater than a join, we can simply delete the whole branch. Unfortunately, this is still $O(n)$ in the worst case, and we don't always find the "best" joins to make when scanning through the tree to add elements.
- One could form a radix trie of $S$. We know that $S$ is bounded by some wildcard string; assume that it is ?0?0. Then all of the branches of the trie only have to be on the 1st and 3rd bits of the strings. If the current bit we are branching on of the query is a 1, we have to check the ? and the 1 branches; if it is 0, we check the ? and the 0 branches; if it is ?, we only check the ? branch. Because we have to potentially take multiple branches, this doesn't seem very good (it is hard to update the trie for the same reason). Since matching is a very very quick operation, it hurts in comparison to the naive strategy to do a lot of traversing in a tree (following a bunch of pointers is much more expensive than doing some ORs and ANDs).
Related work
In the networking community, this problem manifests as "packet classification", here is a good survey of the algorithms and data structures known. Unfortunately, the assumption is almost always made that the wildcard strings only match prefixes, and the query is a tuple of such strings. Of course, we can always convert a general wildcard string to meet these criteria: 1?00?1?? is (1, ?, 0, 0, ?, 1, ?, ?). This would not be efficient, though. The other assumption made is that these tuples are associated with a "color", and querying should return the color (not just that it matched). This makes the problem much harder, because we have to order the tuples (or else it is ambiguous which of (0, ?) and (?, 1) matches (0, 1)).
In the algorithms community I've found a lot of results related to finding substrings that match with "don't cares". This is a considerably harder problem, and I can't really make use of any of the techniques.
In conclusion
Thanks for any help!
