The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Mar. 26, 2013
Filed:
Nov. 24, 2010
Matthew V Ryan, Spanish Fork, UT (US);
Andrew Hodgkinson, Pleasant Grove, UT (US);
Russell Young, Pleasant Grove, UT (US);
Matthew V Ryan, Spanish Fork, UT (US);
Andrew Hodgkinson, Pleasant Grove, UT (US);
Russell Young, Pleasant Grove, UT (US);
Microsoft Corporation, Redmond, WA (US);
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.