Methods and apparatus for regular expression matching

Details Methods and apparatus for regular expression matching Methods and apparatus for regular expression matching

2007-12-11

2007-12-11

Rodriguez, Paul (Department: 2123)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

10340392

ABSTRACT:
Methods and apparatus are disclosed for regular expression matching, especially for, but not limited to high-speed applications such as in a packet switching system (e.g., a router). One implementation includes a matching mechanism for processing each character of a plurality of input characters to progressively generate keyword indications of matched keywords as matched keywords are identified, and for generating one or more matching indications of matched base expressions and non-keyword expressions. These indications are received by a matched regular expression detection mechanism which generates one or more matched regular expression indications based on said one or more keyword indications and said one or more matching indications. In one implementation, the matched regular expression detection mechanism maintains a keyword data structure, which is updated as matched keyword indications are received to ensure they are matched in a proper order. One implementation uses a bitmap to track the matched keywords and AND-SHIFT-OR operations to efficiently update the bitmap.

REFERENCES:
patent: 4241402 (1980-12-01), Mayper et al.
patent: 6263333 (2001-07-01), Houchin et al.
patent: 6571243 (2003-05-01), Gupta et al.
patent: 6892237 (2005-05-01), Gai et al.
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
Ken Thompson, “Programming Techniques”, ACM, vol. 11, No. 6, Jun. 1968, pp. 419-422.
Sun Wu, Udi Manber, Eugene Myers, “A sub-Quadratic Algorithm for Approximate Regular Expression Matching”, Journal of Algorithms, vol. 19, Issue 3, 1995, pp. 1-14.
M. Barrio, P. de la Fuente, and J. Vegas,A Recursive Version of the Shift Or Algorithm, Proceedings of 14th Iasted, Iasted Acta Press, 1996, páginas 15-18.
R. Baeza-Yates and G. Gonnet,A New Approach To Text Searching, Communications of the ACM, 35(10), pp. 74-82, 1992.
R.Boyer and J.Moore,A Fast String Searching Algorithm. Communications of the ACM, 20(10), pp. 761-772, 1977.
Merrill E. Isenman and Dennis E. Shasha,Performance and Architectural Issues for String Matching, IEEE Transactions on Computers, vol. 39, No. 2, Feb. 1990, pp. 238-250.
Josue Kuri and Gonzalo Navarro,Fast Multipattern Search Algorithms for Intrusion Detection, Proceedings of the Seventh International Symposium on String Proceedings and Information Retrieval (SPIRE '00), IEEE, 2000, 12 pages.
C. Jason Coit, Stuart Staniford, and Joseph McAlerney,Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort, Proceedings of the DARPA Information Survivability Conference and Exposition (DISCEXII '01), IEEE, 2001, 7 pages.
Peter C. Wayner,Using Content-Addressable Search Engines to Encrypt and Break DES, Computer Science Department, Cornell University, 1991, 11 pages.

Affiliated with

Also associated with

Rating

Methods and apparatus for regular expression matching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for regular expression matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for regular expression matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3844928