Determining regular expression match lengths

Details Determining regular expression match lengths Determining regular expression match lengths

2009-07-17

2011-11-01

Leroux, Etienne (Department: 2161)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

C707S758000, C711S101000, C711S103000

Reexamination Certificate

active

08051085

ABSTRACT:
A method and apparatus are disclosed for determining the lengths of one or more substrings of an input string that matches a regular expression (regex) The input string is searched for the regex using an non-deterministic finite automaton (NFA), and upon detecting a match state a selected portion of the input string is marked as a match string. The NFA is inverted to create a reverse NFA that embodies the inverse of the regex. For some embodiments, the reverse NFA is created by inverting the NFA such that the match state of the NFA becomes the initial state of the reverse NFA, the initial state of the NFA becomes the match state of the reverse NFA, and the goto transitions of the NFA are inverted to form corresponding goto transitions in the reverse NFA. The match string is reversed and searched for the inverted regex using the reverse NFA, and a counter is incremented for each character processed during the reverse search operation. The current value of the counter each time the match state in the reverse NFA is reached indicates the character length of a corresponding substring that matches the regex.

REFERENCES:
patent: 5995963 (1999-11-01), Nanba et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6980992 (2005-12-01), Hursey et al.
patent: 7058821 (2006-06-01), Parekh et al.
patent: 7139753 (2006-11-01), Bass et al.
patent: 7139837 (2006-11-01), Parekh et al.
patent: 7225188 (2007-05-01), Gai et al.
patent: 7353332 (2008-04-01), Vladan
patent: 7440304 (2008-10-01), Raj
patent: 7529746 (2009-05-01), Ichiriu et al.
patent: 7539031 (2009-05-01), Ninan et al.
patent: 7539032 (2009-05-01), Ichiriu et al.
patent: 7610269 (2009-10-01), Gupta
patent: 7624105 (2009-11-01), Ichiriu et al.
patent: 7643353 (2010-01-01), Srinivasan et al.
patent: 7644080 (2010-01-01), Mammen et al.
patent: 7656716 (2010-02-01), Srinivasan et al.
patent: 7660140 (2010-02-01), Joshi et al.
patent: 7831606 (2010-11-01), Pandya
patent: 7872890 (2011-01-01), Starovoytov
patent: 7876590 (2011-01-01), Joshi
patent: 7916510 (2011-03-01), Starovoitov et al.
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
patent: 2005/0050260 (2005-03-01), Schacham et al.
patent: 2008/0212581 (2008-09-01), Miller et al.
patent: 2010/0054013 (2010-03-01), Joshi et al.
“Efficient String Matching: An Aid to Bibliographic Search,” Aho, A. V. and Corasick, M. J., Communications of the Association of Computing Machinery (ACM) Jun. 1975, vol. 18, No. 6. pp. 333-340.
“Over 10Gbps String Matching Mechanism for Multi-stream Packet Scanning Systems,” Yutaka Sugawara, Mary Inaba, and Kei Hiraki, FPL 2004, LNCS 3203, pp. 484-493, 2004, J. Becker, M. Platzner, S. Vernalde, Editors.
“Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers”, document dated Nov. 21, 2003, 6 pages.
Alicherry et al., “High Speed Pattern Matching for Network IDS/IPS,” IEEE, pp. 187-196 (2006).
McAuley e al., “Fast Routing Table Lookup Using CAMs,” IEEE, p. 1382 (1993).
Yu et al., “Gigabit Rate Packet pattern-Matching Using TCAM,” Proceedings of the Network Protocols, 12th IEEE Int Conf on (ICNP'04), pp. 174-183 (2004).

Affiliated with

Also associated with

Rating

Determining regular expression match lengths does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4263701