Probabilistic learning method for XML annotation of documents

• US 20070022373A1
• Filed: 06/29/2005
• Published: 01/25/2007
• Est. Priority Date: 06/29/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris, Fuselier, Jerome
• Granted Patent: US 8,543,906 B2
• Time in Patent Office: Days
• US Class Current: 715/210
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes

Abstract

A document processor includes a parser that parses a document using a grammar having a set of terminal elements for labeling leaves, a set of non terminal elements for labeling nodes, and a set of transformation rules. The parsing generates a parsed document structure including terminal element labels for fragments of the document and a nodes tree linking the terminal element labels and conforming with the transformation rules. An annotator-annotates the document with structural information based on the parsed document structure.

Claims

1. a document processor comprising:

a classifier that classifies fragments of an input document respective to a set of terminal elements;

a probabilistic grammar defining transformation rules operating on elements selected from the set of terminal elements and a set of non-terminal elements; and

a parser that defines a parsed document structure associating the input document fragments with terminal elements connected by links of non-terminal elements conforming with the probabilistic grammar, the parsed document structure being used to organize the input document.

2. The document processor as set forth in claim 1, further comprising:

an HTML converter that converts a source document having a format other than HTML into the input document having an HTML format.

3. The document processor as set forth in claim 1, wherein the classifier comprises:

a probabilistic classifier that for each input document fragment assigns probability values corresponding to elements of the set of terminal elements.

4. The document processor as set forth in claim 3, wherein the parser comprises:

a joint probability optimizer that optimizes the parsed document structure respective to a joint probability of (i) the probability values of the associated terminal elements and (ii) probabilities of the connecting links of non-terminal elements derived from the probabilistic grammar.

5. The document processor as set forth in claim 4, wherein the probabilistic grammar is a probabilistic context-free grammar and the joint probability optimizer employs a modified inside/outside optimization.

6. The document processor as set forth in claim 3, further comprising:

a classifier trainer that trains the probabilistic classifier respective to a set of training documents having pre-classified fragments.

7. The document processor as set forth in claim 6, further comprising:

a grammar derivation module that derives the probabilistic grammar from the set of training documents, each training document having a pre-assigned parsed document structure associating fragments of the training document with terminal elements connected by links of non-terminal elements.

8. The document processor as set forth in claim 1, wherein the classifier assigns a selected terminal element to each fragment of the input document to define a sequence of terminal elements.

9. The document processor as set forth in claim 8, wherein the parser applies an inside/outside optimization to optimize the links of non-terminal elements respective to the sequence of terminal elements.

10. A document processing method comprising:

classifying fragments of an input document respective to a set of terminal elements;

parsing the classified fragments to determine a parsed document structure associating the fragments with terminal elements connected by links of non-terminal elements conforming with a probabilistic grammar; and

organizing the input document as an XML document with an XML structure conforming with the parsed document structure.

11. The document processing method as set forth in claim 10, wherein the parsing comprises:

determining a probability function for a selected parsed document structure, the probability function including at least a term indicative of a probability of the connecting links of non-terminal elements of the selected parsed document structure computed using the probabilistic grammar; and

optimizing the probability function respective to the selected parsed document structure to determine the parsed document structure.

12. The document processing method as set forth in claim 11, wherein the probability function further includes a term indicative of a probability of the terminal elements associations of the selected parsed document structure computed from the classifying of the fragments.

13. The document processing method as set forth in claim 10, wherein the classifying of the fragments generates probabilistic fragment classifications, and parsing comprises:

optimizing the parsed document structure respective to a joint probability of (i) probabilities of the connecting links of non-terminal elements computed using the probabilistic grammar and (ii) probabilities of terminal element assignments computed using the probabilistic fragment classifications.

14. The document processing method as set forth in claim 10, wherein the organizing of the input document as an XML document comprises:

constructing a document type definition (DTD) conforming with the probabilistic grammar.

15. A document processor comprising:

a parser that parses a document using a grammar having a set of terminal elements for labeling leaves, a set of non-terminal elements for labeling nodes, and a set of transformation rules, the parsing generating a parsed document structure including terminal element labels for fragments of the document and a nodes tree linking the terminal element labels and conforming with the transformation rules; and

an annotator that annotates the document with structural information based on the parsed document structure.

16. The document processor as set forth in claim 15, wherein the parser comprises:

a classifier associating the document fragments with terminal element labels.

17. The document processor as set forth in claim 16, wherein (i) the classifier is a probabilistic classifier that assigns probabilities for terminal element labels of fragments, (ii) the grammar is a probabilistic grammar that assigns probabilities for the transformation rules, and (iii) the parser selects a parsed document structure based on the probabilities of the terminal element labels of the parsed document structure and the probabilities of transformation rules applied in generating the nodes tree.

18. The document processor as set forth in claim 17, wherein the parser selects the parsed document structure to optimize a joint probability of (i) the probabilities of the terminal element labels of the parsed document structure and (ii) the probabilities of the transformation rules applied in generating the nodes tree.

19. The document processor as set forth in claim 15, wherein the annotator comprises:

an XML document converter that converts the document to an XML document having an XML structure generated in accordance with the parsed document structure.

20. The document processor as set forth in claim 19, wherein the XML document includes a DTD based on the probabilistic grammar.