Method and apparatus for processing markup language information

• US 20060236224A1
• Filed: 07/01/2004
• Published: 10/19/2006
• Est. Priority Date: 01/13/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Willis, Steven R., Achilles, Heather D., Kuznetsov, Eugene
• Granted Patent: US 7,287,217 B2
• Time in Patent Office: Days
• US Class Current: 715/235
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets

Abstract

Information represented in text-based markup languages, such as XML, is often a large, highly nested structure corresponding to complex patterns of metadata and/or data. Parsing such data streams via conventional software mechanisms rapidly exhibits degrading performance as the size, or volume, of data increases. Further, such do not perform dynamic modification to the output in response to feedback based on the data being parsed. An adaptive XML processing hardware apparatus processes an XML document in a manner suited to the invoking application, and processes the incoming XML into an optimal structure based on the type of data and a set of rules relating the type of the data to the output format. It also dynamically augments the output information stream based on the data, at the option of the invoking system. The generated output may take a tree form, adaptable for efficient traversal of the hierarchical structure represented by the input XML, or may involve an attribute approach, in which the XML takes the from of a stream of fixed length cells containing optimized representations of input data, or may take a combination of the two approaches, based on configuration and XML input stream.

Claims

1. A method for processing a markup document comprising:

scanning an input stream indicative of the markup document to identify parseable tokens having boundaries;

checking the parseable tokens in the input stream to be well-formed by verifying conformance to a predetermined set of syntax rules,

formatting a stream of encoded items corresponding to the input stream, the encoded items indicative of at least one parseable token;

computing, based on a set of rules, an output format, the set of rules dynamically responsive to the stream of encoded items, the computing resulting in an output format determiner indicative of an optimal type of output;

receiving the encoded item stream by at least one generator operable to generate an output stream, the output stream having an output format, the generator corresponding to the computed output format; and

producing an output structure according to the computed output format from the output stream, the output structure indicative of the structure and content of the markup document.

2. The method of claim 1 wherein the markup document is defined by a syntax including XML elements, attributes and tokens.

3. The method of claim 2 wherein formatting the encoded items further comprises identifying a type, a length, and a value of a markup language semantic element.

4. The method of claim 1 further comprising performing markup processing operations on the stream of encoded items, the rules further dynamically responsive to the markup processing operations, the markup processing operations operable to compute an output format determiner indicative of an optimal type of output.

5. The method of claim 4 further comprising:

compiling the markup processing operations in a compiler operable for accepting markup processing definitions;

generating instructions for execution by the markup post processing engine; and

uploading the instructions to the markup post processing generator for generating an output stream.

6. The method of claim 5 wherein the markup processing operations are selected from the group consisting of qname code token lookup, XPath evaluation, XML schema validation, building of tree fragments, excision of unwanted x-codes from the incoming stream.

7. The method of claim 6 wherein the markup processing operations are dependent on parameters selected from the group consisting of global apparatus configuration, particular xml processing sessions, results of previously performed XML processing operations, incoming XML data and command blocks received from the markup device.

8. The method of claim 1 further comprising:

buffering at least one of the input stream, parseable tokens, encoded items, output stream and output structure; and

maintaining the context of the buffering, the context corresponding to the corresponding markup document.

9. The method of claim 8 further comprising buffering, in at least one random access memory, data selected from the group consisting of incoming XML, parsed tokens, encoded items, XML processing instructions, Xpath instructions, session state and output encoded items in the output stream.

10. The method of claim 9 further comprising transmitting the output structure over a bus interface unit providing access between general purpose computing capability and the markup device.

11. The method of claim 10 wherein the bus interface is operable to transport between a markup hardware processing subsystem and a host application via means of DMA (Direct Memory Access) transfers over a PCI-X bus.

12. The method of claim 11 further comprising:

delivering XML input sequences to the bus interface unit; and

accepting sequences comprising the output stream over the bus interface for subsequent processing including at least one of filtering, XML transformation, XML encryption and XML routing.

13. A markup device for markup document processing comprising:

at least one character processor operable to process an incoming markup data stream, the character processor further operable to;

scan the incoming markup data stream to determine boundaries of markup elements, attributes and tokens;

check the incoming markup data stream to verify well-formed markup according to a syntax of the markup; and

produce a stream of encoded items corresponding to the incoming markup data stream; and

at least one output generator responsive to the character processor, the output generator operable to;

receive the encoded items from the character processor;

perform markup processing operations on the encoded items; and

generate an output stream having an output format, the output stream indicative of the structure and content of the input data stream and the output format dynamically selectable depending on the received encoded items.

14. The device of claim 13 further comprising a markup post processing engine responsive to the markup processing operations and operable to dynamically select and modify the output format of the generators in response to the markup processing operations on the incoming markup data stream.

15. The device of claim 14 wherein markup processing operations are transforms selected from the group consisting of qname code lookup, XPath evaluation, XML schema validation, building of tree fragments, excision of unwanted tokens from the incoming stream.

16. The device of claim 15 wherein the markup post processing engine is responsive to at least one of a global apparatus configuration, a particular markup processing session, results of previously performed markup processing operations, the incoming markup data stream and command blocks.

17. The device of claim 14 further comprising a compiler operable to:

accept the processing definition languages;

generate instructions for execution by the markup post processing engine; and

upload the generated instructions to the markup post processing engine.

18. The device of claim 17 further comprising at least one random access memory for buffering at least one of incoming XML, parsed tokens, encoded items, XML processing instructions, Xpath instructions, session state, the output stream and the output structure.

19. The device of claim 18 further comprising a bus interface unit operable to provide access between a markup hardware processing subsystem and a host application via DMA (Direct Memory Access) transfers over a PCI-X bus.

20. The device of claim 13 wherein the markup processing operations are XML processing operations and the markup language is XML, the markup processing operations conforming to processing definition languages selected from the group consisting of XML Schema, XPath, XSLT and Xquery.

21. The device of claim 20 wherein the markup device is an XML processing engine operable to:

deliver XML input sequences to the bus interface unit; and

accept sequences comprising the output stream over the bus interface for subsequent processing including at least one of filtering, XML transformation, XML encryption and XML routing, the sequences corresponding to the encoded items in the computed output format.

22. The device of claim 13 wherein the character processor further comprises a plurality of ASIC-based (FPGA??_) hardware character processors operable in parallel.

23. A method for processing an information stream of a syntactical based representation of information comprising:

parsing the information stream according to a predetermined set of syntactical rules, the syntactical rules operable to indicate a hierarchical structure of the information;

extracting tokens from the information stream, the tokens corresponding to data items and having a particular type; and

processing the tokens to generate an output representation of the data items included in the information stream, the output representation determinable according to the particular type of the data items and a set of policy rules, and operable to preserve the hierarchical structure for further processing by a recipient application, the policy rules dynamically responsive to the parsed information stream and operable to modify the output representation in response thereto.

24. The method of claim 23 further comprising selectively determining the output representation based on the processing capabilities of the recipient application.

25. The method of claim 24 further comprising selectively determining the output representation according to the particular type of the data items.

26. The method of claim 25 wherein generating the output representation includes generating the representation of the data items in a discontiguous manner with the corresponding tokens in the hierarchical structure.

27. The method of claim 24 wherein determining the output representation further comprises:

computing an initial configuration indicative of a particular output representation;

comparing tokens in the information stream to a set of predetermined rules, the predetermined rules indicative of a policy for selecting the output representation; and

dynamically applying the rules to augment the output representation according to the policy.

28. The method of claim 27 wherein the output representation further comprises an enumeration of the type of data item corresponding to a token, and an indication of the location of data item corresponding of the token.

29. The method of claim 28 wherein the information stream further comprises a sequence of discontiguous portions, the discontiguous portions apportioned according to an external protocol, further comprising concatenating the discontiguous portions into a continuous input stream.

30. The method of claim 29 further comprising:

identifying fragments of a token corresponding to a plurality of discontiguous portions; and

marking the input stream with an indication of a forthcoming portion of data corresponding to the token.

31. The method of claim 30 further comprising:

receiving a plurality of information streams, each of the information streams represented by a sequence of discontiguous portions; and

identifying, for each discontiguous portion, a corresponding input stream; and

identifying the discontiguous portions for each of the input streams, the identification independent of the order of receipt of the discontiguous portions.

32. A method for processing a document comprising:

parsing tokens via an input stream from the document, the document arranged according to a predetermined format;

determining an output format indicative of a particular representation, the particular representation depending on an invoking application and a corresponding manner of processing;

identifying relations between the parsed tokens, the relations derived from the predetermined format;

processing each of the parsed tokens according to the determined output format, the processing transforming the tokens into the output format;

maintaining the relations and content corresponding to the parsed tokens during the processing; and

returning the parsed tokens and corresponding values to the invoking application in the determined optimal format.

33. The method of claim 32 wherein the particular representation corresponds to an expected organization of the parsed tokens, the organization corresponding to an expected manner of processing the output tokens.

34. The method of claim 33 wherein the expected manner of processing corresponds to an optimal format based on the processing requirements of the invoking application.

35. The method of claim 34 further comprising identifying associations between the tokens, the associations determined by the hierarchical nesting and sequence of tokens in the documents.

36. The method of claim 32 further comprising augmenting the output format according to feedback, the feedback determined by comparison of the tokens parsed from the incoming stream with rules indicative of a data policy.

37. The method of claim 36 wherein the predetermined format is a nested syntax adapted to indicate tokens and corresponding values arranged in a hierarchical order.

38. The method of claim 32 further comprising switching between output formats, switching further comprising demarcating a transition in the parsed tokens between processed tokens corresponding to dissimilar output formats.

39. The method of claim 38 values are attributes indicative of a discontiguous data value, the data value accessible via indirect address computation.

40. The method of claim 39 wherein indirect address computation includes computing an index value to a portion of memory including the corresponding value.

41. The method of claim 40 further comprising traversing the indexed portion to identify the corresponding value from among values corresponding to other tokens.

42. A content sensitive document processor comprising:

a parser operable to parse the information stream according to a predetermined set of syntactical rules, the syntactical rules operable to indicate a hierarchical structure of the information, the parser further operable to extract tokens from the information stream, the tokens corresponding to data items and having a particular type; and

a generator receptive to the parser and operable to process the tokens to generate an output representation of the data items included in the information stream, the output representation determinable according to the particular type of the data items, and operable to preserve the hierarchical structure for further processing by a recipient application.

43. The document processor of claim 42 further comprising a dynamic output selector operable to selectively determine the output representation based on a markup processing definition and the processing capabilities of the recipient application, the processing capabilities according to a configuration specification.

44. The document processor of claim 43 wherein the generator is operable to selectively determine the output representation according to the particular type of the data items.

45. The document processor of claim 44 further comprising a tree builder operable to generating the output representation including generating the representation of the data items discontiguous with the corresponding tokens in the hierarchical structure.

46. The document processor of claim 43 wherein the generator is further operable to:

compute an initial configuration indicative of a particular output representation;

compare tokens in the information stream to a set of predetermined rules, the predetermined rules indicative of a policy for selecting the output representation; and

dynamically apply the rules to augment the output representation according to the policy.

47. The document processor of claim 46 wherein the output representation further comprises an enumeration of the type of data item corresponding to a token, and an indication of the location of data item corresponding of the token.

48. The document processor of claim 47 wherein the information stream further comprises a sequence of discontiguous portions, the discontiguous portions apportioned according to an external protocol, the parser further operable to concatenate the discontiguous portions into a continuous input stream.

49. The document processor of claim 48 wherein the parser is farther operable to:

identify fragments of a token corresponding to a plurality of discontiguous portions; and

mark the input stream with an indication of a forthcoming portion of data corresponding to the token.

50. The document processor of claim 49 wherein the generator is further operable to:

receive a plurality of information streams, each of the information streams represented by a sequence of discontiguous portions; and

identify, for each discontiguous portion, a corresponding input stream; and

reassemble the discontiguous portions for each of the input streams, the reassembling independent of the order of receipt of the discontiguous portions.

51. A computer program product having a computer readable medium operable to store computer program logic embodied in computer program code encoded thereon for processing an information stream of a syntactical based representation of information comprising:

computer program code for parsing the information stream according to a predetermined syntax, the syntax operable to indicate a hierarchical structure of the information;

computer program code for extracting tokens from the information stream, the tokens corresponding to data items and having a particular type; and

computer program code for processing the tokens to generate an output representation of the data items included in the information stream, the output representation determinable according to the particular type of the data items and a set of rules, and operable to preserve the hierarchical structure for further processing by a recipient application the rules dynamically responsive to the parsed information stream and operable to modify the output representation in response thereto.

52. A computer data signal having program code for processing an information stream of a syntactical based representation of information comprising:

program code for parsing the information stream according to a predetermined syntax, the syntax operable to indicate a hierarchical structure of the information;

program code for extracting tokens from the information stream, the tokens corresponding to data items and having a particular type; and

program code for processing the tokens to generate an output representation of the data items included in the information stream, the output representation determinable according to the particular type of the data items and a set of rules, and operable to preserve the hierarchical structure for further processing by a recipient application, the rules dynamically responsive to the parsed information stream and operable to modify the output representation in response thereto.

53. A content sensitive document processor for processing an information stream of a syntactical based representation of information comprising:

means for parsing the information stream according to a predetermined syntax, the syntax operable to indicate a hierarchical structure of the information;

means for extracting tokens from the information stream, the tokens corresponding to data items and having a particular type; and

means for processing the tokens to generate an output representation of the data items included in the information stream, the output representation determinable according to the particular type of the data items and a set of rules, and operable to preserve the hierarchical structure for further processing by a recipient application.