NUMBER SEQUENCES DETECTION SYSTEMS AND METHODS

• US 20100306260A1
• Filed: 05/29/2009
• Published: 12/02/2010
• Est. Priority Date: 05/29/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dejean, Herve
• Granted Patent: US 9,135,249 B2
• Time in Patent Office: Days
• US Class Current: 707/776
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering
• CPC Class Codes: G06V 30/416 Extracting the logical structure, e.g. chapters, sections or page numbers; Identifying elements of the document, e.g. authors

Abstract

Numbered sequences detection includes (i) extracting one or more numbered item token patterns from a document comprising an ordered sequence of text units, each numbered item token pattern including an incremental portion and a fixed portion that matches at least one text unit of the document and (ii) identifying at least one numbered sequence in the document conforming with a matching numbered item token pattern of the extracted one or more numbered item token patterns. The identified at least one numbered sequence comprises an ordered sub-sequence of text units of the document that match the matching numbered item token pattern. The detection may further comprise determining that a second type of numbered sequence nests in the document between consecutive text units belonging to a numbered sequence of a first type, and optimizing one or more numbered sequences of the second type based on information provided by the determining.

Claims

1. A numbered sequences detector comprising:

a digital processor configured to perform a method including the operations of (i) extracting one or more numbered item token patterns from a document comprising an ordered sequence of text units, each numbered item token pattern including an incremental portion and a fixed portion that matches at least one text unit of the document and (ii) identifying at least one numbered sequence in the document conforming with a matching numbered item token pattern of the extracted one or more numbered item token patterns, the identified at least one numbered sequence comprising an ordered sub-sequence of text units of the document that match the matching numbered item token pattern.

2. The numbered sequences detector as set forth in claim 1, wherein the ordered sequence of text units is selected from a group consisting of:

an ordered sequence of grammatical sentences, and

an ordered sequence of lines of text.

3. The numbered sequences detector as set forth in claim 1, wherein the extracting operation (i) includes extracting a numbered item token pattern that matches text units of an ordered sub-sequence of text units of the document wherein portions of the text units matching the incremental portion of the numbered item token pattern conform with an encoding table defining an incremental relationship.

4. The numbered sequences detector as set forth in claim 1, wherein the extracting operation (i) includes extracting a numbered item token pattern that matches text units of an ordered sub-sequence of text units of the document wherein portions of the text units matching the incremental portion of the numbered item token pattern conform with an alphabetical or numerical sequence.

5. The numbered sequences detector as set forth in claim 1, wherein the identifying operation (ii) includes identifying numbered items comprising text units of the document that match at least one of the extracted one or more numbered item token patterns and dividing the numbered items into at least one numbered sequence.

6. The numbered sequences detector as set forth in claim 1, wherein the digital processor is further configured to perform the method which conditional upon the identifying operation (ii) identifying a plurality of numbered sequences in the document further includes:

(iii) identifying an optimization context for a second type of numbered sequence as a first type of numbered sequence different from the second type of numbered sequence; and

(iv) optimizing at least one numbered sequence of the second type under the constraints that;

(I) a numbered sequence of the second type does not contain any text unit belonging to a numbered sequence of the first type and

(II) no more than one numbered sequence of the second type is disposed between any two consecutive text units of an ordered sub-sequence of text units comprising a numbered sequence of the first type.

7. The numbered sequences detector as set forth in claim 6, wherein the optimization context identifying operation (iii) includes (iii)(a) quantifying compliance with criterion (I) and criterion (II) of numbered sequences of the first and second types identified in the identification operation (ii) and (iii)(b) identifying the optimization context based on the quantified compliance satisfying a selection criterion.

8. The numbered sequences detector as set forth in claim 7, wherein the quantifying operation (iii)(a) counts occurrences of numbered sequences of the second type between consecutive text units of numbered sequences of the first type and the selection criterion of operation (iii)(b) is that a majority of consecutive text units of numbered sequences of the first type have counts of one or zero for operation (iii)(a).

9. The numbered sequences detector as set forth in claim 6, wherein the optimizing operation (iv) includes (iv)(a) assigning weights to text units of one or more numbered sequences of the second type based on similarity with a model of said text units of said one or more numbered sequences of the second type and (iv)(b) optimizing said one or more numbered sequences of the second type based on the assigned weights.

10. The numbered sequences detector as set forth in claim 9, wherein the optimizing (iv)(b) employs a Viterbi optimization algorithm.

11. The numbered sequences detector as set forth in claim 6, wherein the digital processor is further configured to perform the method which further includes (v) assigning hierarchy information to the numbered sequences including at least assigning numbered sequences of the first type a relatively higher hierarchical level and assigning numbered sequences of the second type a relatively lower hierarchical level.

12. A document processing system comprising:

a numbered sequences detector as set forth in claim 1; and

a document structuring processor that is the same as or different from the digital processor of the numbered sequences detector and that is configured to generate a structured document that (1) corresponds to a document comprising an ordered sequence of text units and (2) includes structuring based on one or more numbered sequences identified in the document by the numbered sequences detector.

13. A method comprising:

extracting one or more numbered item token patterns from a document comprising an ordered sequence of text units, each numbered item token pattern including an incremental portion and a fixed portion that matches at least one text unit of the document;

identifying at least one numbered sequence in the document conforming with a matching numbered item token pattern of the extracted one or more numbered item token patterns, the identified at least one numbered sequence comprising an ordered sub-sequence of text units of the document that match the matching numbered item token pattern; and

generating a structured document based on the document comprising an ordered sequence of text units and structured in accordance with the identified at least one numbered sequence.

14. The method as set forth in claim 13, wherein the extracting comprises:

extracting a numbered item token pattern that matches text units of an ordered sub-sequence of text units of the document wherein portions of the text units matching the incremental portion of the numbered item token pattern conform with an encoding table defining an incremental relationship or with an alphabetical or numerical sequence.

15. The method as set forth in claim 13, wherein the identifying identifies a plurality of numbered sequences in the document and the method further comprises:

determining that a second type of numbered sequence nests in the document between consecutive text units belonging to a numbered sequence of a first type; and

optimizing one or more numbered sequences of the second type based on information provided by the determining.

16. The method as set forth in claim 13, wherein the identifying identifies a plurality of numbered sequences in the document and the method further comprises:

determining that a second type of numbered sequence nests in the document between consecutive text units belonging to a numbered sequence of a first type; and

assigning hierarchy information to the numbered sequences including at least assigning numbered sequences of the first type a relatively higher hierarchical level and assigning numbered sequences of the second type a relatively lower hierarchical level.

17. A storage medium storing instructions executable by a digital processor to perform a method including identifying numbered sequences of at least two different sequence types in a document comprising an ordered sequence of text units wherein each numbered sequence comprises an ordered sub-sequence of text units of the document in which the text units of the numbered sequence have an incremental portion indicative of the sequence type, identifying a numbered sequence of a first type having consecutive text units bounding a nested numbered sequence of a second type different from the first type, and adjusting at least one numbered sequence of the second type based on the constraint that it must be bounded by consecutive text units of a numbered sequence of the first type.

18. The storage medium as set forth in claim 17, wherein the stored instructions are further executable by a digital processor to perform a method including extracting a plurality of different numbered item token patterns from the document, each numbered item token pattern including an incremental portion and a fixed portion that matches at least one text unit of the document, the numbered sequences identification utilizing the plurality of different numbered item token patterns for identifying the numbered sequences in the document.

19. The storage medium as set forth in claim 17, wherein the adjusting at least one numbered sequence of the second type based on the constraint that it must be bounded by consecutive text units of a numbered sequence of the first type includes optimizing the numbered sequence of the second type under the constraints that:

(I) the numbered sequence of the second type does not contain any text unit belonging to a numbered sequence of the first type and

(II) no more than one numbered sequence of the second type is disposed between any two consecutive text units of an ordered sub-sequence of text units comprising a numbered sequence of the first type.

20. The storage medium as set forth in claim 17, wherein the stored instructions are further executable by a digital processor to assign hierarchy information to the numbered sequences including at least assigning numbered sequences of the first type a relatively higher hierarchical level and assigning numbered sequences of the second type a relatively lower hierarchical level.