Efficient conditional state mapping in a pattern matching automaton

Patent metadata

Field	Value
Publication number	US-2017277811-A1
Application number	US-201515512353-A
Country	US
Kind code	A1
Filing date	Sep 22, 2015
Priority date	Sep 26, 2014
Publication date	Sep 28, 2017
Grant date	—

Abstract

A computer implemented method to determine the satisfaction of one or more mapping conditions conditionally mapping a first state in a first pattern matching automaton to a second state in the first automaton, each of the conditions being based on symbol patterns matched by a second pattern matching automaton having states corresponding to wildcard symbols in the first automaton, the method comprising: encoding the conditions in a condition tree data structure associated with the first state, the condition tree modeling sequences of symbol patterns for matching by the second automaton and corresponding to each of the conditions, wherein a node in the condition tree corresponding to a complete set of symbol patterns for a condition has associated an output symbol sequence to identify a pattern match by the first automaton.

First claim

1 . A computer implemented method to determine the satisfaction of one or more mapping conditions conditionally mapping a first state in a first pattern matching automaton to a second state in the first automaton, each of the conditions being based on symbol patterns matched by a second pattern matching automaton having states corresponding to wildcard symbols in the first automaton, the method comprising:
encoding the conditions in a condition tree data structure associated with the first state, the condition tree modeling sequences of symbol patterns for matching by the second automaton and corresponding to each of the conditions, wherein a node in the condition tree corresponding to a complete set of symbol patterns for a condition has associated an output symbol sequence to identify a pattern match by the first automaton.

2 . The method of claim 1 wherein the first automaton has states and directed transitions between states, the directed transitions corresponding to symbols in a plurality of symbol patterns.

3 . The method of claim 1 wherein the mapping conditions define when the first automaton should generate an output associated with a mapped state without transitioning to the mapped state.

4 . The method of claim 1 wherein the mapping conditions define one or more failure states when the first automaton fails to transition via a directed transition based on an input symbol received by the first automaton.

5 . The method of claim 1 wherein the first state represents a sequence of symbols including one or more wildcard symbols and the second state represents a proper suffix of the sequence of symbols of the first state, wherein the conditional mappings include conditions based on input symbols to be received, by the first automaton in use, to constitute the wildcard symbols.

6 . The method of claim 1 wherein, in execution, the first and second automata are jointly associated with a session identifier to identify a pattern matching session, the session identifier being changed whenever the first automaton transitions states by way of a mapping between states.

7 . A pattern matching machine generator arranged to generate a first pattern matching automaton having one or more mapping conditions conditionally mapping a first state in a first automaton to a second state in the first automaton, the generator being further arranged to:
generate a second pattern matching automaton having states corresponding to wildcard symbols in the first automaton, wherein each of the conditions is based on symbol patterns matched by the second automaton; and encode the conditions in a condition tree data structure associated with the first state, the condition tree modeling sequences of symbol patterns for matching by the second automaton and corresponding to each of the conditions, wherein a node in the condition tree corresponding to a complete set of symbol patterns for a condition has associated an output symbol sequence to identify a pattern match by the first automaton.

8 . The pattern matching machine generator of claim 7 wherein the first automaton has states and directed transitions between states, the directed transitions corresponding to symbols in a plurality of symbol patterns.

9 . The pattern matching machine generator of claim 7 wherein the mapping conditions define when the first automaton should generate an output associated with a mapped state without transitioning to the mapped state.

10 . The pattern matching machine generator of claim 7 wherein the mapping conditions define one or more failure states when the first automaton fails to transition via a directed transition based on an input symbol received by the first automaton.

11 . The pattern matching machine generator of claim 7 wherein the first state represents a sequence of symbols including one or more wildcard symbols and the second state represents a proper suffix of the sequence of symbols of the first state, wherein the conditional mappings include conditions based on input symbols to be received, by the first automaton in use, to constitute the wildcard symbols.

12 . The pattern matching machine generator of claim 7 wherein, in execution, the first and second automata are jointly associated with a session identifier to identify a pattern matching session, the session identifier being changed whenever the first automaton transitions states by way of a mapping between states.

13 . A non-transitory computer-readable storage medium storing a computer program element comprising computer program code which, when loaded into a computer system and executed thereon, causes the computer to perform the method as claimed in claim 1 .

Assignees

• British Telecomm

Inventors

• Mistry James

Classifications

• G06F17/30985 Primary

  Physics · mapped topic

• G06F17/30961

  Physics · mapped topic

• G06F16/9027

  Trees · CPC title

• G06F16/90344 Primary

  by using string matching techniques · CPC title