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:
Sep. 23, 2014
Filed:
Dec. 21, 2009
Mikkel Thorup, Florence, MA (US);
Philip Bille, Albertslund, DK;
Mikkel Thorup, Florence, MA (US);
Philip Bille, Albertslund, DK;
AT&T Intellectual Property I, L.P., Atlanta, GA (US);
Abstract
Improved matching of a regular expression in an input string. A system first identifies a number of substrings (k) in a regular expression of length (m). The system receives a stream of start states for each of the substrings generated according to a regular expression matching process and receives a stream of end occurrences generated according to a multi-string matching process. The system identifies all instances where an end occurrence of a particular substring matches a positive start state of the particular substring, and enters the instances as positive substring accept states in the regular expression matching process on the input string. In one aspect, the system is much more efficient when (k) is much less than (m). The system can match the regular expression based on a bit offset between the first and second stream.