专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US07240040B2 Method of generating of DFA state machine that groups transitions into classes in order to conserve memory 有权
标题翻译：生成DFA状态机的方法，将转换分组到类中以节省内存
公开(公告)号：US07240040B2
公开(公告)日：2007-07-03
申请号：US10217592
申请日：2002-08-08
申请人： Daniel Wyschogrod , Alain Arnaud , David Eric Berman Lees , Leonid Leibman
发明人： Daniel Wyschogrod , Alain Arnaud , David Eric Berman Lees , Leonid Leibman
IPC分类号： G06F17/00 , G06F7/06
CPC分类号： H04L45/742 , G06F17/30985 , H04L29/06 , H04L67/1002 , H04L67/327 , H04L69/03 , H04L69/22 , H04L69/327 , H04L2029/06054
摘要： A method for generating look-up tables for a high speed multi-bit Real-time Deterministic Finite state Automaton (hereinafter RDFA). The method begins with a DFA generated in accordance with the prior art. For each state in the DFA, and for each of the bytes recognized in parallel the following occurs. First an n-closure list is generated. An n-closure list is a list of states reachable in n-transitions from the current state. Next an alphabet transition list is generated for each state. An “alphabet transition list” is a list of the transitions out of a particular state for each of the characters in an alphabet. Finally, the transitions are grouped into classes. That is, the transitions that go to the same state are grouped into the same class. Each class is used to identify the next state. The result is a state machine that has less states than the original DFA.
摘要翻译：一种用于产生高速多位实时有限状态自动机（以下称为RDFA）的查询表的方法。该方法以根据现有技术生成的DFA开始。对于DFA中的每个状态，并且对于并行识别的每个字节，将发生以下情况。首先生成一个n关闭列表。 n关闭列表是从当前状态进行n次转换可达到的状态列表。接下来，为每个状态生成字母转换列表。 “字母转换列表”是字母表中的每个字符的特定状态之间的转换的列表。最后，转换被分组成类。也就是说，进入同一状态的转换被分组到同一个类中。每个类用于标识下一个状态。结果是状态机的状态比原始的DFA少。

2. 发明授权

US07461370B2 Fast hardware processing of regular expressions containing sub-expressions 有权
标题翻译：包含子表达式的正则表达式的快速硬件处理
公开(公告)号：US07461370B2
公开(公告)日：2008-12-02
申请号：US10359839
申请日：2003-02-07
申请人： Daniel Wyschogrod , Leonid Leibman
发明人： Daniel Wyschogrod , Leonid Leibman
IPC分类号： G06F9/45
CPC分类号： G06F8/427
摘要： A system for processing regular expressions containing one or more sub-expressions. Information regarding one or more regular expressions, each containing one or more sub-expressions, is stored. Data is compared to the stored information regarding expressions in only a single pass through the data. From the comparison, for any stored expression, the location within the data of the beginning and end of each sub-expression, and the end of the regular expression, are determined. From such determination, the presence within the data of any one or more stored regular expressions containing one or more sub-expressions is identified.
摘要翻译：用于处理包含一个或多个子表达式的正则表达式的系统。存储关于一个或多个正则表达式的信息，每个正则表达式包含一个或多个子表达式。将数据与仅在通过数据的单次传递中的关于表达式的存储的信息进行比较。从比较中，对于任何存储的表达式，确定每个子表达式的开始和结束的数据内的位置以及正则表达式的结束。从这样的确定，识别包含一个或多个子表达式的任何一个或多个存储的正则表达式的数据内的存在。

3. 发明授权

US06856981B2 High speed data stream pattern recognition 有权
标题翻译：高速数据流模式识别
公开(公告)号：US06856981B2
公开(公告)日：2005-02-15
申请号：US10005462
申请日：2001-12-03
申请人： Daniel Wyschogrod , Alain Arnaud , David Eric Berman Lees , Leonid Leibman
发明人： Daniel Wyschogrod , Alain Arnaud , David Eric Berman Lees , Leonid Leibman
IPC分类号： G06F17/30 , H04L29/06 , G06F17/00
CPC分类号： G06F17/30985 , H04L45/742 , H04L69/03 , H04L69/22
摘要： A system and method in accordance with the present invention determines in real-time the portions of a set of characters from a data or character stream which satisfies one or more predetermined regular expressions. A Real-time Deterministic Finite state Automaton (RDFA) ensures that the set of characters is processed at high speeds with relatively small memory requirements. An optimized state machine models the regular expression(s) and state related alphabet lookup and next state tables are generated. Characters from the data stream are processed in parallel using the alphabet lookup and next state tables, to determine whether to transition to a next state or a terminal state, until the regular expression is satisfied or processing is terminated. Additional means may be implemented to determine a next action from satisfaction of the regular expression.
摘要翻译：根据本发明的系统和方法实时地确定来自满足一个或多个预定正则表达式的数据或字符流的一组字符的部分。实时确定性有限状态自动机（RDFA）可确保以较小的内存要求高速处理字符集。优化的状态机对正则表达式和状态相关的字母查找进行建模，并生成下一个状态表。使用字母查找和下一状态表并行地处理来自数据流的字符，以确定是否转换到下一状态或终端状态，直到正则表达式被满足或处理终止。可以实现额外的手段来确定满足正则表达式的下一个动作。

4. 发明授权

US09043272B2 System and method for determining the start of a match of a regular expression 有权
标题翻译：用于确定正则表达式匹配的开始的系统和方法
公开(公告)号：US09043272B2
公开(公告)日：2015-05-26
申请号：US11901515
申请日：2007-09-18
申请人： Daniel Wyschogrod , Leonid Leibman
发明人： Daniel Wyschogrod , Leonid Leibman
IPC分类号： G06F17/30
CPC分类号： G06F17/30985 , Y10S707/99936
摘要： A system for determining the start of a match of a regular expression has a special state table which contains start state entries and terminal state entries; a plurality of start state registers for storing offset information indicative of the start of a match of the regular expression; a deterministic finite state automaton (DFA) next state table which, given the current state and an input character, returns the next state. The DFA next state table includes a settable indicator for any next state table entry which indicates whether to perform a lookup into the special state table. A compiler loads values into the special state table based on the regular expression.
摘要翻译：用于确定正则表达式的匹配的开始的系统具有包含起始状态条目和终端状态条目的特殊状态表; 多个开始状态寄存器，用于存储指示正则表达式的匹配开始的偏移信息; 给定当前状态和输入字符的确定性有限状态自动机（DFA）下一状态表返回下一状态。 DFA下一状态表包括任何下一状态表条目的可设置指示符，指示是否对特殊状态表执行查找。编译器根据正则表达式将值加载到特殊状态表中。

5. 发明申请

US20080077587A1 System and method for determining the start of a match of a regular expression 有权
标题翻译：用于确定正则表达式匹配的开始的系统和方法
公开(公告)号：US20080077587A1
公开(公告)日：2008-03-27
申请号：US11901515
申请日：2007-09-18
申请人： Daniel Wyschogrod , Leonid Leibman
发明人： Daniel Wyschogrod , Leonid Leibman
IPC分类号： G06F7/06 , G06F17/30
CPC分类号： G06F17/30985 , Y10S707/99936
摘要： A system for determining the start of a match of a regular expression has a special state table which contains start state entries and terminal state entries; a plurality of start state registers for storing offset information indicative of the start of a match of the regular expression; a deterministic finite state automaton (DFA) next state table which, given the current state and an input character, returns the next state. The DFA next state table includes a settable indicator for any next state table entry which indicates whether to perform a lookup into the special state table. A compiler loads values into the special state table based on the regular expression.
摘要翻译：用于确定正则表达式的匹配的开始的系统具有包含起始状态条目和终端状态条目的特殊状态表; 多个开始状态寄存器，用于存储指示正则表达式的匹配开始的偏移信息; 给定当前状态和输入字符的确定性有限状态自动机（DFA）下一状态表返回下一状态。 DFA下一状态表包括任何下一状态表条目的可设置指示符，指示是否对特殊状态表执行查找。编译器根据正则表达式将值加载到特殊状态表中。

6. 发明授权

US07305391B2 System and method for determining the start of a match of a regular expression 有权
标题翻译：用于确定正则表达式匹配的开始的系统和方法
公开(公告)号：US07305391B2
公开(公告)日：2007-12-04
申请号：US10773595
申请日：2004-02-06
申请人： Daniel Wyschogrod , Leonid Leibman
发明人： Daniel Wyschogrod , Leonid Leibman
IPC分类号： G06F7/00
CPC分类号： G06F17/30985 , Y10S707/99936
摘要： A method for determining the start of a match of a regular expression using the special state table, the set of start state registers and the DFA next state table, includes the step of determining from the regular expression each start-of-match start state and each end-of-match terminal state. For each start state, a start state entry is loaded into the special state table. For each terminal state, a terminal state entry is loaded into each special state table. The next state table is used to return the next state from the current state and an input character. When a start state is encountered, the current offset from the beginning of the input character string is loaded into the start state register. When a terminal state is encountered, the terminal state entry is retrieved from the special state table, and the value of the start state register corresponding to the rule number of the terminal entry in the special state table is further retrieved. The value of the start state register which is retrieved indicates the location in the character string where the start-of-match occurred for a particular rule.
摘要翻译：使用特殊状态表，开始状态寄存器组和DFA下一状态表来确定正则表达式的匹配开始的方法包括从正则表达式确定每个开始匹配开始状态和每个端对端终端状态。对于每个启动状态，将启动状态条目加载到特殊状态表中。对于每个终端状态，终端状态条目被加载到每个特殊状态表中。下一个状态表用于从当前状态和输入字符返回下一个状态。当遇到启动状态时，从输入字符串开头的当前偏移量被加载到启动状态寄存器中。当遇到终端状态时，从特殊状态表中检索终端状态条目，并进一步检索与特殊状态表中的终端条目的规则号对应的起始状态寄存器的值。检索到的起始状态寄存器的值表示特定规则发生匹配开始的字符串中的位置。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式