PATTERN-MATCHING SYSTEM

• US 20080263039A1
• Filed: 04/03/2008
• Published: 10/23/2008
• Est. Priority Date: 12/10/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Van Lunteren, Jan
• Granted Patent: US 7,734,091 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An XML parsing system includes a pattern-matching system 1 that receives an input stream 2 of characters corresponding to the XML document to be parsed, and provides an output 3 for subsequent processing in software by a processor 4. The pattern matching system 1 includes two main components, a controller in the form of a programmable state machine 5, which is programmed with an appropriate state transition diagram 6, and a character processing unit 7 in the form of a token and character handler. The programmable state machine 5 controls the character processing unit 7 to, e.g., compare characters in the input character stream 2 with other received or stored characters. The character processing unit 7 then provides feedback to the programmable state machine controller 5, e.g., as to whether the compared characters match, so that the programmable state machine controller 5 can then parse the received document accordingly.

Claims

1. An apparatus for pattern-matching characters in a stream of received characters, the apparatus comprising:

a character processing unit comprising means for storing characters, and means for comparing a received input character with at least one stored character; and

a controller for controlling the character processing unit, the controller including means for receiving an input stream of characters to be pattern-matched and means for controlling the character processing unit to compare characters from the input stream with characters stored by the character processing unit.

2. The apparatus of claim 1, wherein the character processing unit stores at least one predetermined character or character string.

3. The apparatus of claim 1, wherein the character processing unit comprises means for combining characters into identifiable character strings.

4. The apparatus of claim 1, wherein the character processing unit comprises means for providing an output that can then be used by the controller to further control the received character stream processing operation.

5. The apparatus of claim 1, wherein the character processing unit comprises means for outputting strings of at least one character.

6. The apparatus of claim 1, wherein the controller comprises means for assessing characters in the received character stream and then selectively controlling and using the character processing unit on the basis of that assessment.

7. The apparatus of claim 1, wherein the controller comprises means for controlling the output of the apparatus.

8. The apparatus of claim 1, wherein the controller comprises means for pausing the processing and input of the received character stream.

9. The apparatus of claim 1, wherein the controller comprises a programmable state machine.

10. An apparatus for performing pattern matching of an input character stream, comprising:

a character processing unit that can store characters and compare characters provided to it with characters that it has stored; and

a programmable state machine for receiving the input character stream and for controlling the character processing unit to compare characters in the input character stream with characters stored by the character processing unit.

11. The apparatus of claim 10, wherein the programmable state machine uses state transition rules, and the state transition rules include a command field that can be used to indicate a required operation of the character processing unit.

12. The apparatus of claim 10, wherein there is a common set of state transitions that can be invoked from different locations within a state diagram of the programmable state machine.

13. The apparatus of claim 10, wherein the programmable state machine uses state transition rules to represent state transitions, and the state transition rules are of a plurality of different types, with different types of rules involving different test conditions.

14. A programmable state machine in which at least one state transition can cause the programmable state machine to send a command or instruction to a processing unit under the control of the programmable state machine.

15. A programmable state machine in which at least one state transition can cause the programmable state machine to pause the input of data to the programmable state machine.

16. A programmable state machine comprising means for invoking a single common set of state transitions from more than one location in the state diagram that the state machine is programmed to represent.

17. A programmable state machine in which state transitions are represented by state transition rules, wherein at least one of the state transition rules includes one set of test condition types, and at least one other state transition rule includes a different set of test condition types.

18. A programmable state machine which includes state transition rules that are specifically related to particular states and state transition rules that do not relate to any particular state.

19. A method of pattern-matching characters in a stream of received characters, the method comprising:

storing at least one characters in a character processing unit comprising means for storing characters;

selectively providing at least one characters from a received input character stream to the character processing unit; and

controlling the character processing unit to compare a received input character with at least one of the characters stored by the character processing unit.

20. The method of claim 19, further comprising storing at least one predetermined characters or character strings in the character processing unit.

21. The method of claim 19, further comprising combining stored characters into identifiable character strings.

22. The method of claim 19, further comprising the character processing unit providing an output that can then be used to further control the received character stream processing operation.

23. The method of claim 19, further comprising the character processing unit outputting characters and/or character strings.

24. The method of claim 19, further comprising assessing characters in the received character stream and then selectively controlling and using the character processing unit on the basis of that assessment.

25. The method of claim 19, further comprising pausing the processing and input of the received character stream.

26. The method of claim 19, further comprising controlling the character processing unit using a programmable state machine.

28. The method of claim 26, wherein the programmable state machine uses state transition rules, and the state transition rules include a command field that can be used to indicate a required operation of the character processing unit.

29. The method of claim 26, wherein there is a common set of state transitions that can be invoked from different locations within a state diagram of the programmable state machine.

30. The method of claim 26, wherein the programmable state machine uses state transition rules to represent state transitions, and the state transition rules are of a plurality of different types, with different types of rules involving different test conditions.

36. The use of the method of claim 19 for XML parsing.

27. A method of pattern-matching characters in a stream of received characters, the method comprising:

receiving the input character stream at a programmable state machine; and

the programmable state machine controlling a character processing unit that has stored at least one characters to compare characters in the received input character stream with a character or characters stored by the character processing unit.

31. A method of creating a data structure for a programmable state machine, comprising:

deriving and storing a set of state transitions for the state machine;

wherein at least one of the stored state transitions can cause the programmable state machine to send a command or instruction to a processing unit under the control of the programmable state machine.

32. A method of creating a data structure for a programmable state machine, comprising:

deriving and storing a set of state transitions for the state machine;

wherein at least one of the stored state transitions can cause the programmable state machine to pause the input of data to the programmable state machine.

33. A method of creating a data structure for a programmable state machine, comprising:

deriving and storing a set of state transitions for the state machine; and

deriving and storing a plurality of other state transitions that will invoke the stored set of state transitions.

34. A method of creating a data structure for a programmable state machine, comprising:

deriving and storing a set of state transitions for the state machine that include one set of test condition types; and

deriving and storing another set of state transitions for the state machine that include a different set of test condition types.

35. A method of creating a data structure for a programmable state machine comprising:

deriving state transition rules that are specifically related to particular states; and

deriving state transition rules that do not relate to any particular state.

37. A program storage device readable by a digital processing apparatus and having a program of instructions which are tangibly embodied on the storage device and which are executable by the processing apparatus to perform a method of transporting packets of data, wherein each packet is assigned a number of priorities, the method comprising:

storing at least one characters in a character processing unit comprising means for storing characters;

selectively providing at least one characters from a received input character stream to the character processing unit; and

controlling the character processing unit to compare a received input character with at least one of the characters stored by the character processing unit.