9
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ how large are the strings allowed to be? And why are you not accounting for their length in the complexity? Obviously you need the strings to be $\Omega(log n)$ otherwise you just wouldn't have $n$ distinct strings to work with. It also seems intuitive that if you allow $O(n)$-length strings, then you will have to look at all your strings in your data structure in the worst case... are there any bounds on the string length? Poly-logarithmic? $o(n)$? $\endgroup$ – Artem Kaznatcheev Apr 11 '11 at 5:35
  • $\begingroup$ Sorry if I wasn't clear. The strings have $O(1)$ size; for all intents and purposes, you can think of them as being 32 characters long. "String" was just a convenient abstraction for framing the problem -- they are actually represented as (integer, bitmask) tuples, so that I can calculate the join and $v \leq w$ in only a few machine operations. (Of course, the problem can be naturally extended to larger constant size strings by increasing the number of integer and bitmask fields). $\endgroup$ – Christopher Monsanto Apr 11 '11 at 5:52
  • $\begingroup$ My above comment probably isn't helpful for a complexity argument :(. There isn't really any relation between the size of the strings and the size of the set, if you allow the size of the strings to vary as well. If that is true about being $O(n)$ worst case that is unfortunate, but, I am much more interested in the average-case (or approximations) anyway. $\endgroup$ – Christopher Monsanto Apr 11 '11 at 6:02
3
$\begingroup$

How about using a finite-state automaton? The language $S$ is finite and therefore regular. Even after the transformations below it will still be regular. So after the usual steps to convert the regular expression into a deterministic finite-state automaton, you will have a recognizer for what you want that operates in $O(k)$ time. Hopefully this idea will still be workable if there are bugs in what is proposed below.

The wrinkle is how to deal with the wildcard operator: ?. A wildcard in a wildcard string matches a 0 or 1 in a test string. But since we're trying to recognize wildcard strings, a wildcard in a wildcard string matches 0, 1, or ? in another wildcard string. This set is still regular, so we transform every occurrence of ? to the regular expression (0|1|?) where the vertical bar is the usual alternation operator. So if your whole set $S$ is {10??1, 0?1?0}, the resulting regular expression will be (10(0|1|?)(0|1|?)1 | 0(0|1|?)1(0|1|?)0)

As for adding strings to the machine, there's some recent work on changing a finite-state automaton incrementally. See this paper by Daciuk et al: "Incremental Construction of Minimal Acyclic Finite-State Automata".

Does this help?

$\endgroup$
  • $\begingroup$ I had considered automata, yeah (what I was doing with the trie was similar to how one would accept a string with an automata). I hadn't, however, found such work on incrementally constructing said automata. I'll check that out, thanks for the pointer ShyPerson. $\endgroup$ – Christopher Monsanto Apr 13 '11 at 17:45
  • $\begingroup$ I cited the Daciuk, et al paper because it seemed closest to what you're trying to achieve. But I think it's worth mentioning that the problem has been solved more recently for arbitrary finite-state automata by Carrasco and Forcada in their paper "Incremental Construction and Maintenance of Minimal Finite-State Automata": mitpressjournals.org/doi/abs/10.1162/… $\endgroup$ – ShyPerson Apr 14 '11 at 15:40
  • $\begingroup$ OK, I don't think I'll get much else out of this topic, so I am accepting your answer. Thanks! $\endgroup$ – Christopher Monsanto Apr 15 '11 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.