0
$\begingroup$

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find longest prefix (lets call it P) of QUERY which is a member of RULES for which F(P,QUERY) returns true?

That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type T is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type T.

An example:

Types are {A,B,C}.

Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1

View is defined by those rules: {/; C=>true, A=>true}, {/A1/B1; C=>true}, {/A1; C=>false}, {/A2; B=>true,C=>true}

Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1

Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.

$\endgroup$
0
$\begingroup$

I'll answer your generic question. Store the RULES in a trie. Then, you can generate each prefix of the QUERY, traversing the trie as you go. This will let you enumerate all prefixes P of QUERY that are a member of RULES. For each such prefix P, you can then evaluate F(P,QUERY). The running time is $O(n)$ where $n$ is the length of QUERY, plus the time to do at most $n$ invocations of F. If you want, you can check the longest prefixes of QUERY first, in order of decreasing length, so that once you find a single prefix P where F(P,QUERY) returns true, you can stop immediately.

I don't believe it is possible to do better, without knowing something about F. Obviously, any algorithm must take at least $\Omega(n)$ time (since you must read each character of QUERY), and must invoke F potentially on each prefix that is a member of RULES.

$\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.