Speeding matching search of hierarchical name structures
US11106663B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 22, 2019 |
| Grant date | Aug 31, 2021 |
| Priority date | — |
| Expiry date | Apr 28, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2246
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.