Pattern-matching system

• US 7,734,091 B2
• Filed: 04/03/2008
• Issued: 06/08/2010
• Est. Priority Date: 12/10/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Van Lunteren, Jan
• Primary Examiner(s): Tabatabai; Abolfazl
• Application Number:
  US12/062,273
• Publication Number:
  US 20080263039A1
• Time in Patent Office: 796 Days
• Field of Search: 382/159, 382/165, 382/170, 382/181, 382/193, 382/194, 382/199, 382/209, 382/218, 704/221, 704/243, 707/2, 707/6, 717/143
• US Class Current: 382/181
• 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 of a document 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, the controller comprising;

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; and

means for parsing the document,

wherein the character processing unit further comprises means for providing feedback to the controller as to whether the characters from the input stream match the characters stored by the character processing unit, the feedback enabling the controller to parse the document.

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 controlling the output of the apparatus.

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

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

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

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

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

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

assessing characters in the received input character stream and then selectively controlling and using the character processing unit according to the assessing;

receiving feedback from the character processing unit as to whether the characters from the received input character stream match the characters stored by the character processing unit; and

parsing the document based on the feedback received.

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

11. The method of claim 9, further comprising combining stored characters into identifiable character strings.

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

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

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

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

16. The method of claim 15, 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.

17. The method of claim 15, 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.

18. The method of claim 15, 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.

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

receiving an input character stream of a document at a programmable state machine;

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

using the programmable state machine to assess the characters in the received input character stream and then selectively controlling and using the character processing unit according to the assessing;

using the programmable state machine to receive feedback from the character processing unit as to whether the characters from the received input character stream match the characters stored by the character processing unit; and

using the programmable state machine to parse the document based on the feedback received.

20. 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 of a plurality of characters in a character processing unit comprising means for storing characters;

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

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

assessing characters in the received input character stream and then selectively controlling and using the character processing unit according to the assessing;

receiving feedback from the character processing unit as to whether the characters from the received input character stream match the characters stored by the character processing unit; and

parsing the document based on the feedback received.