3

The problem: Given a list of globs, I need to find (and return) a glob from the list that a given string matches or definitively determine that none match in. Excluding setup time, performance must be better than a linear search of all the globs:

foreach glob in list:
  if glob.matches(string):
    return glob
return None

The question: Are there any available libraries (C++ preferred) for this?


Edit: After a bit more thought, I thinkin I can argue that this can be done. Given that globs are more or less regex with a different syntax, a runtime version of lex that uses glob syntax would fit the bill.

Given that the problem can be trivially reduced to a know problem, I'm only still interested in implemented solutions.

2
  • Is it even possible? Given 26 globs (*A*, *B*, *C*... *Z*) is it possible to not check all the 26 globs (so O(n))
    – xanatos
    Mar 25, 2011 at 15:04
  • xanatos: Given that set, you should expect to only needs to check a small number of globs before one matches. Or you could compress it to the regex .*[A-Z].* and run that.
    – BCS
    Mar 25, 2011 at 15:08

5 Answers 5

7

Convert your globs into regular expressions (a series of simple string manipulations can achieve this - * becomes .*, etc). Combine them into a single regular expression, using | and assigning the results to a different capture group for each glob so that you can determine which glob matched if there was a match. Rely on your favourite regex library to compile the regular expression into a DFA that is hopefully more optimal to process than a linear walk of the constituent parts, where this is possible - however, in the most general case, it will not be faster.

7
  • Wha? Given enough free startup time, any regex can be matched in lenght(input) time so it should be faster in any case with more than one glob. What am I missing?
    – BCS
    Mar 25, 2011 at 15:20
  • How do you find which capture group was filled in less than O(n)?
    – BCS
    Mar 25, 2011 at 15:25
  • 4
    @BCS: Any particular regex (which is really "regular"; some Perl "regex" syntaxes do not qualify) can be matched in O(length(input)) time, yes. But when the length of the regex is also a relevant variable, you need a different model of computational complexity.
    – aschepler
    Mar 25, 2011 at 15:27
  • @BCS Won't regexes need to backtrack if the greedy part grabs too much at first? Additionally I think what @moonshadow is saying is that the constant of the linear search with a regex may make it as slow or slower than a corresponding linear search of the globs.
    – Mark B
    Mar 25, 2011 at 15:27
  • 1
    Your regex library will, in reality, create an NFA and use backtracking to select between alternative possibilities. While it is possible to convert an NFA to an equivalent DFA, real-world engines frequently don't bother. See e.g. swtch.com/~rsc/regexp/regexp1.html
    – moonshadow
    Mar 25, 2011 at 15:30
6

Globs are a subset of regular expressions (with respect to expressive power, not exact syntax). Globs can therefore be converted into deterministic finite automata (DFA) and those can be combined to form a single DFA that recognizes the union of the single DFAs. DFAs have a complexity of O(n) with n being the length of the string. How much Globs the automaton is constructed from only influences the setup time (i.e. creating the automaton), not the run time.

1
  • I just noticed that an changed my answer.
    – Oswald
    Mar 25, 2011 at 15:15
0

Probably just in some particular cases. If you can predict somehow that some globs will not match your string.

0

I don't think it's possible to have better than linear time in the number of globs. In order to prove that a string doesn't match any of the globs, you have to check for a match against every one, or you'll never know whether one you skipped matched or not.

EDIT: In the general case this isn't possible using globs. As noted in a comment it's possible for some combinations of globs to be combined (At first guess a trie might be useful, where each node indicates the next letter to match and the globs you still need to check), causing a smaller amount of work searching.

It also might be possible in the general case to convert a set of globs into a corresponding regular expression.

Is performance of this matching really such an issue that you need to improve it? Have you considered if a more fundamental algorithmic rewrite might be better?

2
  • That assume that you can't combine some of the match efforts with some setup work: e.g. if /foo/bar/* doesn't match, for 5 places, /foo/baz/* need not be checked and if it fails after the second place, /pickle/* can be skipped.
    – BCS
    Mar 25, 2011 at 15:16
  • Technically you could try to create a "negative" expression, one of "don't match". It COULD be simpler, but I'm not sure... I was looking for two non-simplifiable and not-negatable expressions... While the union of the globs is clearly O(n), perhaps the intersection of the negative globs is a little less.
    – xanatos
    Mar 25, 2011 at 15:22
0

I would look to see if your application is a good fit for a shift-reduce parser like bison. They use lookup tables, which are a pain to set up or change and use more memory, but are very fast. Technically, it's not physically possible to do better than O(n) worst case, but depending on your globs, your strings, and your tokenizer, using a technique like this can make your average case much better than that, because it eliminates patterns that don't match without having to check each one each time.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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