Improved pattern matching

Patent metadata

Field	Value
Publication number	US-2017278001-A1
Application number	US-201515512319-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 whether a verification is to be performed of the satisfaction of one or more mapping conditions mapping a first state in a first pattern matching automaton to a second state in the first automaton, the verification being based on patterns matched by a second pattern matching automaton having states corresponding to wildcard symbols in the first automaton, the method comprising: associating, with the first state, a minimum number of patterns required to be matched by the second automaton to satisfy a mapping condition of the state; providing a pattern match counter in association with the second automaton, the counter being arranged to count a number of patterns matched by the second automaton; providing a verifier in association with the first automaton, the verifier being arranged to perform the verification, the verifier being responsive to the counter.

First claim

1 . A computer implemented method to determine whether a verification is to be performed of the satisfaction of one or more mapping conditions mapping a first state in a first pattern matching automaton to a second state in the first automaton, the verification being based on patterns matched by a second pattern matching automaton having states corresponding to wildcard symbols in the first automaton, the method comprising:
associating, with the first state, a minimum number of patterns required to be matched by the second automaton to satisfy a mapping condition of the state; providing a pattern match counter in association with the second automaton, the counter being arranged to count a number of patterns matched by the second automaton; and providing a verifier in association with the first automaton, the verifier being arranged to perform the verification, the verifier being responsive to the counter.

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 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; generate a verifier arranged to verify the satisfaction of the one or more mapping conditions; associate, with the first state, a minimum number of patterns required to be matched by the second automaton to satisfy a mapping condition of the state; and provide a pattern match counter in association with the second automaton, the counter being arranged to count a number of patterns matched by the second automaton, wherein the verifier is responsive to the counter.

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

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title

• G06F16/90344 Primary

  by using string matching techniques · CPC title