4
$\begingroup$

I'm thinking about a routing system. Imagine I have the two following regexes

  • pathpart1/pathpart2 => specific match that routes to controller1
  • .* => catch-all that routes to controller2

And I let them match on a URL, e.g. 'pathpart1/pathpart2'.

They both match, but I would want to give prevalence to the most specific regex, i.e. the regex where the cardinality of all possible matches of that regex is the lowest.

Is there a good way to calculate that the first regex has a low cardinality on its match-set (so I want to to go with that match) and the second has a very high cardinality on its match-set (i.e. it is completely not specific, so a match is basically a catch all last resort)...?

I do not know upfront which routes are registered with the router, so I can't loop over them in order of cardinality by hand (i.e. low cardinality first, and the catch-all last if all others don't match).

$\endgroup$
3
$\begingroup$

There are two angles I see to define "specifity" in this context.

  1. Specifity of a regular expression $r$ that matches input $w$ is the (inverse of the) number of words of length $|w|$ that also match $r$.
  2. Specifity of a regular expression $r$ that matches input $w$ is (the ratio of) the (maximum) number of symbols of $w$ that are matched by non-wildcard symbols in $r$ (and $|w|$).

The first option follows your idea: choose among all matches the regular expressions that matches the fewest others. Since there are in general infinitely many matching strings, we have to restrict ourselves to a certain length, or a finite set of lengths.

The second option follows another approach. If the input string is well described by a given expression, long parts of it should be (more or less) explicitly described in the regular expression. For example, $(aa|ab)+.^*bba$ is a more specific match for $aaababaababababba$ than $.^*$.

Option 1

In this case, we have to count all words in $\mathcal{L}(r)$ that have length $n$. Luckily, this is easy once we have an unambiguous, regular grammar¹ $G$ for $\mathcal{L}(r)$. See here how this can be done.

Option 2

Let's assume we have an unambiguous regular expression (for instance by specifying lazy wildcards). In that case, we can translate the regular expression into a DFA. Run the word through it and count how many non-wildcard transitions are taken.

If the expression is ambiguous, we can do the same with the corresponding NFA if we explore all possible paths.


  1. Convert $r$ to an $NFA$, determinise, convert to right-regular grammar. All conversions are standard and algorithmically feasible (if not necessarily efficient).
$\endgroup$
  • $\begingroup$ Thanks for the understandable and useful answer! I'm not an expert in math but let's see how far I get! :-) $\endgroup$ – Willem Mulder Mar 27 '13 at 21:48
2
$\begingroup$

I don't know if you would consider this a "good" way, but the naive approach would be to count the matches of each regex, and compare.

This is not too expensive: In order to find a match, you run a DFA for $r$ (where $r$ is the regex in question) starting at every index of the input. You then wait for an accepting run. Usually, we optimize this algorithm such that if the two runs of the DFA (from different indices) are in the same state at index $i$, then we "unify" them to a single run. The runtime is $O(n)$, where $n$ is the length of the word, assuming $r$ is fixed.

This can be modified to an algorithm that counts matches by simply counting the number of DFAs that are in the same state at each index. Then, whenever an accepting state is reached, you sum the number of runs to this state and add it to a running total. This still takes $O(n)$ time, and only adds counters for each state.

Note that this crucially uses a DFA and not an NFA. Indeed, if you start with an NFA for $r$, this is a problematic solution, since you will overestimate the number of matches.

$\endgroup$
1
$\begingroup$

The gist of the problem, I think, is to properly define a partial order on regexps. Since the language accepted by them is potentially infinite, using cardinality seems very difficult.

However, the problem can be broken down to comparing accepted input at each step of the processing of the input string. The comparison predicate for character sets can be built upon cardinality comparison.

Regexps may be (and usually are) encoded, as you know, as DFAs, which necessarily contain for every state the accepted input set. An efficient solution could then be, having access to the internal data of a regexp compiled down to a DFA, to compare these input sets at every step of the parsing of the input string. However, the suvcessive input set accepted by a regexp get scattered on different states, which render comparison difficult in general, as opposed to a discrete input string. The resulting partial order would be specific to the string (or to the class of strings following the same path in the DFA).

You can also establish a partial order on regular expressions by computing their derivatives against the input string, but this will be slower in practice than using the DFA data.

Here's a quick rundown of what it's all about. A regexp derivative $r'$ of a regexp $r$ is, given an input letter, the regular expression which will behave as $r$ after having received that input letter. This notion can easily be expanded to a full input set, by computing the union

Regular Expressions derivatives are defined in terms of the derivatives of their operators, which I will recall here:

  • concatenation (elided in practice, but noted $.$ here)

    for an expression $r = \alpha . e$ where $\alpha$ is a letter of the alphabet, the derivative with respect to $\alpha$ of $r$ is $e$, and the null match otherwise.

  • kleene star, noted $*$ (repetitions)

    An expression $r* = (\alpha . e)*$ has for derivative $r' = e | r*$ wrt. $\alpha$

  • the alternative operator, noted $|$

    The derivative of the expression $r = a l b$ is $r' = a' | b'$ with the input set being the union of the input set of $a'$ and $b'$.

  • ranged repetitions, noted $\{a,b\}$, where $a$ and $b$ are the lower and upper bounds

    For $r\{a,b\}$, the derivative will be (similarily to $*$) $r' | r\{a-1,b-1\}$

Other operators ($?$,$+$) can be easily defined from these operators.

The idea to compare the specificity of two regexps is to recursively compute the derivatives of both regexps on the input string, and compare their input sets (which have to be infered from the regexps, but this can be done, as demonstrated in this article, to actually construct the corresponding DFA).

$\endgroup$
  • $\begingroup$ This sounds quite inefficient because we have to compute lots of input sets. Is there a trick to keep complexity in check? $\endgroup$ – Raphael Mar 27 '13 at 7:45
  • $\begingroup$ My implementation of derivatives uses character ranges to reduce the difficulty in handling input set. In practice this seems fairly fast (not as fast as DFA though). There's this implementation which belongs to a larger project seemingly claiming to be very efficient (see this blog), but I stumbled upon it yesterday and couldn't yet check it out. Another possible path is memoization. $\endgroup$ – didierc Mar 27 '13 at 8:30
  • $\begingroup$ Sorry if all of this sounds a bit vague. I got interested in regexp derivatives a bit more than a year ago, so my recollection is a bit hazy. $\endgroup$ – didierc Mar 27 '13 at 8:35
  • $\begingroup$ thought about it a little more. $\endgroup$ – didierc Mar 27 '13 at 10:23
  • $\begingroup$ Thanks, certainly a lot of interesting links for me to go through. $\endgroup$ – Willem Mulder Mar 27 '13 at 21:48

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.