1
$\begingroup$

So I have a bunch of strings that represent routes in a HTTP web framework. Each string has a leading /, some /-separated path segments which can either be a string, a single-segment wildcard ?, or a trailing multi-segment wildcard *. (For this problem, we can assume that * can only be in a trailing position, but there may be more than one ?s)

e.g.

/foo
/bar
/qux/?
/?/baz/thingy
/xyz/*
/xyz/abc

I am trying to analyze this list of strings to figure out if any of the routes are potentially ambiguous. For example, in the above set,

  1. /?/baz/thingy and /xyz/* are ambiguous, because a path /xyz/baz/thingy would satisfy both routes
  2. /xyz/* and /xyz/abc are similarly ambiguous because a path /xyz/abc would satisfy both routes

Is there any standard/well-known/commonly-used algorithm for taking the list of inputs and identifying ambiguous subsets of them?

I think this problem can be converted without loss of generality to the problem of finding ambiguities among a set of UNIX-style globs, as below. But I also don't know what algorithm I could use to find ambiguities among a set of unix globs

a
b
c?
?dg
e*
ef

What exactly the algorithm should return is also a bit unknown to me. e.g. ambiguity between routes is not transitive, so

  1. /?/baz/thingy is ambiguous with /xyz/*,
  2. /xyz/* is ambiguous with /xyz/abc
  3. But /?/baz/thingy is not ambiguous with /xyz/abc

For my purposes I don't really care about the shape of the return value, as long as I can return something human-readable so the user of the framework can see the ambiguities and resolve them. I need it to list all the inputs which are ambiguous, and at least one other input with which it is ambiguous with, but I don't need to list out all the pairwise ambiguities.

EDIT: in fact, for my purposes, finding a single pairwise ambiguity if one exists, or reporting that no pairwise ambiguity exists, is sufficient

I know how to do this pair-wise, e.g. given two routes, it's easy to walk them both in lockstep and see if they are ambiguous or not in one pass. This can give an O(num_routes^2 * length_of_routes) algorithm for finding all routes which are ambiguous. Can we do better, especially if we just need to list all the ambiguous routes and not all the pairwise ambiguities? Or is quadeatic complexity the best we can get?

$\endgroup$
5
  • $\begingroup$ Can a route have more than one ?? $\endgroup$
    – D.W.
    Commented Jan 5 at 23:15
  • $\begingroup$ Yes a route can have more than one ? $\endgroup$
    – Li Haoyi
    Commented Jan 5 at 23:42
  • $\begingroup$ Why would you think that there is a better algorithm than quadratic? The worst case scenario is that all pairs are ambiguous, which means you have to output all pairs anyway and this is quadratic. $\endgroup$ Commented Jan 9 at 21:01
  • $\begingroup$ @KennethKho I've already stated in the question I do not need all pairs, just enough pairs to cover every ambiguous input line. But if quadratic is still the best that can be done, and someone can prove, I'd accept that answer as well $\endgroup$
    – Li Haoyi
    Commented Jan 10 at 22:39
  • $\begingroup$ I deleted my inefficient trie-based answer. A look on how that worked: Let $s_1$ = /a/b/?/c/d/?/e and $s_2$ = /a/?/x/c/?/y/?, we are done as it matches. But what if $s_2$ = /a/?/x/c/?/y/z? /a would have two children, /b/?/c/d/?/e and /?/x/c/?/y/z. Let $s_3$ = /a/b/x/?/d/y/z, we are done as it would go to /a, then both /b and /?, matching /? path. But what if $s_3$ = /a/b/c/?/d/y/w? /a/b would have two children, /c/?/d/y/w and /?/c/d/?/e. At this point, I thought $O(n^2)$ worst case & $O(n)$ avg case but /a/? would also have two children with $O(2^n)$ worst case. $\endgroup$ Commented Jan 13 at 16:41

1 Answer 1

1
$\begingroup$

Here is one approach. Suppose $n$ is the max length of any route, in segments. Build $2n$ indices, of the following form:

  • An index of all routes, where we include all segments (exact match).

  • An index of all routes, where we ignore the $i$th segment, for $i=1,\dots,n$ (match on all but the $i$th segment).

  • An index of of all routes, where we only pay attention to segments $1..i$ (i.e., we truncate each route after the $i$th route, so we match on only the first $i$ segments).

Each index can be built as a hashtable or a dict, so that given a route, you can look it up to see if there is any match in the set of all routes.

Of course, what constitutes a match depends on the index. For example, for the index where we ignore the 2nd segment, /a/b/c/d is considered to match /a/x/c/d and /a/?/c/d. This can be implemented by deleting the 2nd segment before inserting or looking up a route in the index; or by building a custom hash function that ignores the 2nd segment.

Insert all routes into these indices.

Now given a route with no wildcards (no ?, no *), you can test whether it matches any other route by looking it up in the first index (exact match on all segments).

Given a route with a trailing *, count how many segments precede the *, call it $i$, and look up in the index where you match on segments $1..i$ (i.e., on the prefix of length $i$).

Given a route with a single ?, let $i$ denote the index of the segment where the ? appears, and look up in the index where you match on all but the $i$th segment.

Given a route with multiple ?s, fall back to your approach, where you compare this route to all others, one at a time, using your pairwise algorithm. As an optimization, letting $i$ denote the index of the first ?, you can look up in the index that matches on segments $1..i-1$, enumerate all matches, and use pairwise testing on only those matches. This doesn't help for something like /?/a/b/?/c, but it helps a lot for /a/b/?/d/?/e.

If you have a lot of routes with multiple ?s, see String matching.

Related: Efficiently enumerating all "good" strings given the ability to say whether a partial specification can be good, String matching for wildcard-based records, Given a set of string patterns, find which ones match a particular string, https://cstheory.stackexchange.com/q/36913/5038.

$\endgroup$

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.