Speeding matching search of hierarchical name structures

A system comprising:

• a memory storing instructions, and
• a processor, coupled with the memory and to execute the instructions, the instructions when executed cause the processor to:
• search for a match to the regular expression in a first subtree defined by a first node name;
• record information about the first subtree if there is no match;
• determine whether a second subtree, defined by a second node name, is identical to the first node;
• and
• skip search of the second subtree if the second subtree is determined to be identical and prefix equivalent to the first subtree, wherein the second subtree is determined to be prefix equivalent to the first subtree when for any string s, a first prefix defined by a concatenation of the first node name and the string s results in a match if and only if a second prefix defined by a concatenation of the second node name and the string s results in match.

A non-transitory computer readable medium comprising stored instructions, which when executed by a processor, cause the processor to:

• search for a match to the regular expression in a first subtree defined by a first node name;
• record information about the first subtree if there is no match;
• determine whether a second subtree, defined by a second node name, is identical to the first node;
• skip search of the second subtree if the second subtree is determined to be identical and prefix equivalent, with respect to the regular expression, to the first subtree, wherein the second subtree is determined to be prefix equivalent to the first subtree when for any string s, a first prefix defined by a concatenation of the first node name and the string s results in a match if and only if a second prefix defined by a concatenation of the second node name and the string s results in match.