发明名称 |
Impulse regular expression matching |
摘要 |
Disclosed is a method and apparatus for matching regular expressions. A buffer of symbols giving a number of the last occurrence positions of each symbol is maintained. When two constants match on either side of a regular expression operator, the buffer of symbols is queried to determine if a member of the complement of the regular expression operator occurred between the two constants. If so, then the operator was not satisfied. If not, then the operator was satisfied. |
申请公布号 |
US9177251(B2) |
申请公布日期 |
2015.11.03 |
申请号 |
US201414156648 |
申请日期 |
2014.01.16 |
申请人 |
Intel Corporation |
发明人 |
Podkolzin Alexander;Ivanovic Lav;Bolotov Anatoli;Grinchuk Mikhail;Afonin Sergey |
分类号 |
G06N5/02;G06N5/04;G06F7/02;G06F17/30 |
主分类号 |
G06N5/02 |
代理机构 |
Barnes & Thornburg LLP |
代理人 |
Barnes & Thornburg LLP |
主权项 |
1. A system that matches a string of symbols to a regular expression pattern, said regular expression pattern comprising a first constant, a second constant, and a first operator, said first operator occurring between said first constant and said second constant in said regular expression pattern, comprising:
a processor; a memory; a deterministic finite automaton (DFA) engine that matches said first constant to said regular expression pattern starting at a first position in said string of symbols, the first DFA engine matching said second constant to said regular expression pattern ending at a second position in said string of symbols; and a buffer of symbols that associates a plurality of positions of occurrences of a plurality of symbols in said string of symbols, said buffer of symbols producing an indicator that a position of a symbol from a complementary set of symbols is between said first position and said second position, said complementary set of symbols being based on a complement of said first operator, said indicator corresponding to whether the first operator is satisfied. |
地址 |
Santa Clara CA US |