1
$\begingroup$

From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to the regex. With regex compiled to DST it should have complexity class of O(n * m) where n is number of elements in map and m is the length of the longest key in the map. Assuming m is reasonably small, we can assume it is O(n).

Above solution to this problem, although it is reasonably good, makes me think every time - is it possible to construct a data structure that would be faster (at least in theory) in searching all the keys that match the given regex. Probably it would not be linearly dependent on the number of the keys in the data structure. Is it possible? If it is possible - what would be the main idea reducing complexity?

$\endgroup$
2
  • $\begingroup$ You may be re-inventing a (compressed/&enhanced) trie. $\endgroup$
    – greybeard
    Mar 3 at 17:00
  • $\begingroup$ What's a DST? Presumably the running time depends on the size of the regex, so I don't believe the O(nm) running time for the basic solution. $\endgroup$
    – D.W.
    Mar 3 at 19:51
1
$\begingroup$

One possible approach is to store the keys in a trie, convert the regex to a DFA (remove all useless states from it and optionally minimize it), and then use that to search the trie.

In particular, you can construct a recursive algorithm for traversing the trie. The root of the trie is associated with the start state of the DFA. For each edge out of the root, you look at the letter on that edge, advance the DFA to the appropriate state, and associate that state with the corresponding child. If it causes the DFA to reject, then you can prune exploration of that node in the trie. In this way, each node in the trie gets associated with a state of the DFA, you recursively explore the trie, pruning when you hit dead ends, and if you hit a leaf in the trie, if the DFA is in an accept state at that point, you have found a match.

However the running time to convert a regex to a DFA can take exponential time. Also this only works with language-theoretic regular expressions, not Perl- or POSIX-style regexps, which are more expressive and cannot be converted to a DFA. So, whether this will be attractive might depend on your application.

$\endgroup$

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.