Efficient string pattern matching for large pattern sets
US8407245B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 24, 2010 |
| Grant date | Mar 26, 2013 |
| Priority date | — |
| Expiry date | Apr 9, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/90344
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A string matching system is described herein that provides for very fast and efficient pattern matching against large sets of certain types of pattern strings. If a set of pattern strings is comprised of strings that can be logically divided into segments, these pattern strings can be stored efficiently in a tree-like data structure, segment by segment, storing pattern-match syntax segments separately from literal string segments. After segmentation, individual match candidate strings are compared, segment by segment, against elements in the tree. The system uses a data structure that is conceptually a combination of a tree and a hash table. Using a hash table to implement the branching elements at each level in the tree contributes to quick matching speed at each level. By consistently separating strings into segments, the system can also share storage locations for like elements in the data structure.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.