Synopsys, Inc.
Speeding matching search of hierarchical name structures

Abstract:

A search for a regular expression in a tree hierarchy, includes, in part, searching for a match to the regular expression in a first subtree defined by a first node name, recording information about the first subtree if there is no match, determining whether a second subtree defined by a second node name is identical to the first node, skipping 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. 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 a match.