Number sequences detection systems and methods

• US 9,135,249 B2
• Filed: 05/29/2009
• Issued: 09/15/2015
• 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
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US12/474,500
• Publication Number:
  US 20100306260A1
• Time in Patent Office: 2,300 Days
• Field of Search: None
• US Class Current: 1/1
• 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 operating on a document comprising an ordered sequence of text units, the method including the operations of;

(i) extracting one or more numbered item token patterns from the document, each numbered item token pattern including an incremental portion defining at least one index and a fixed portion, each numbered item token pattern matching at least one text unit of the document wherein said matching includes matching the incremental portion of the numbered item token pattern with an index value for the text unit of the document defined by one or more tokens of the 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, each identified numbered sequence comprising an ordered sub-sequence of text units of the document wherein;

the identifying includes matching each text unit of the ordered sub-sequence of text units of the document with the matching numbered item token pattern including matching the incremental portion of the matching numbered item token pattern with an index value of the text unit of the document defined by one or more tokens of the text unit of the document, and

the index values of the ordered sub-sequence of text units of the document that comprise the numbered sequence have an incremental relationship.

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 the index values 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 the index values of the text units matching the incremental portion of the numbered item token pattern conform with an alphabetical or numerical sequence incremental relationship.

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 comprising a digital 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 operating on a document comprising an ordered sequence of text units, the method comprising:

extracting one or more numbered item token patterns from the document, each numbered item token pattern including an incremental portion and a fixed portion, each numbered item token pattern matching text units of an ordered sub-sequence of text units of the document wherein;

for each text unit of the ordered sub-sequence of text units said matching includes matching the incremental portion of the numbered item token pattern with an index value defined by one or more tokens of the text unit, and

wherein the index values of the text units of the ordered sub-sequence of text units conform with an expected incremental relationship for the incremental portion of the numbered item token pattern defined by (1) an incremental relationship encoding table or (2) an alphabetical or numerical sequence; and

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, each identified numbered sequence comprising an ordered sub-sequence of text units of the document that match the matching numbered item token pattern with portions of the text units matching the incremental portion of the matching numbered item token pattern defining index values having the expected incremental relationship;

wherein the extracting and the identifying are performed by a computer.

14. 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.

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

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.

16. The method of claim 13 further comprising:

using a computer, 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.

17. A non-transitory 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,

from amongst the identified numbered sequences of at least two different types, 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 non-transitory 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 non-transitory 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 non-transitory 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.