Granted Patent B2

US 8,719,702 · App. 12/719,982 · Granted May 6, 2014

Inventor: Jean-Luc Meunier (St. Nazaire les Eymes, FR)

Assignee: Xerox Corporation

Abstract

Claims (52)

1. A method operating on a document comprising an ordered sequence of pages, each page having a physical page number indicating its location in the ordered sequence of pages, the method comprising:

(0) identifying logical page numbers comprising tokens in pages of the document based on at least one of commonality of a single marginal location of the identified logical page numbers in the pages of the document and conformance of the identified logical page numbers with one or more predefined numbering patterns;

(i) generating a mapping that maps each identified logical page number to one or more physical page numbers indicating pages of the document marked by the logical page number;

(ii) identifying a sequence of logical page number references comprising tokens in the document sequenced in the document in accordance with a reading order for the document;

(iii) selecting a sub-sequence of the sequence of logical page number references that maps to a nondecreasing sequence of physical page numbers according to the mapping, the selecting being biased toward selecting a long sub-sequence and being biased toward selecting a dense sub-sequence; and

(iv) structuring the document based on the selected sub-sequence of the sequence of logical page number references, the structuring including associating the logical page number references of the selected sub-sequence with the corresponding physical page numbers of the mapped nondecreasing sequence of physical page numbers;

wherein the operations (0), (i), (ii), (iii), and (iv) are performed by a digital processor.

2. The method as set forth in claim 1 , wherein the selecting comprises:

biasing the selecting toward a dense sub-sequence by limiting the selecting to selecting a sub-sequence of the sequence of logical page number references that spans no more than a predefined fraction or number of pages of the document.

3. The method as set forth in claim 1 , wherein the selecting further comprises:

filtering the selecting to exclude any sub-sequence that maps to a nondecreasing sequence of physical page numbers whose fraction of incremental physical page number steps is greater than F where F is greater than or equal to 0.5.

4. The method as set forth in claim 1 , wherein the selecting further comprises:

filtering the selecting to exclude any sub-sequence that maps to a nondecreasing sequence of physical page numbers whose fraction of incremental physical page number steps is greater than F where F is greater than or equal to 0.7.

5. The method as set forth in claim 1 , wherein the selecting comprises:

generating a sequence of physical page number sets corresponding to the sequence of logical page number references by mapping each logical page number reference to a mapped set of one or more physical page numbers; and

optimizing selections of single physical page numbers from the physical page number sets respective to a figure of merit that biases toward selecting a long sub-sequence and biases toward selecting a dense sub-sequence, the optimized selections defining the nondecreasing sequence of physical page numbers.

6. The method as set forth in claim 1 , wherein the identifying a sequence of logical page number references in the document comprises:

identifying the logical page number references as tokens in the document that match with the identified logical page numbers.

7. The method as set forth in claim 1 , wherein the associating of the logical page number references with the corresponding physical page numbers comprises:

generating hyperlinks linking the logical page number references of the selected sub-sequence with ordered pages of the document indicated by the physical page numbers of the mapped nondecreasing sequence of physical page numbers.

8. An apparatus comprising:

a digital processing device configured to perform a method operating on a document comprising an ordered sequence of pages, each page having a physical page number indicating its location in the ordered sequence of pages, the method comprising:

identifying logical page numbers comprising tokens in pages of the document based on at least one of commonality of a single marginal location of the identified logical page numbers in the pages of the document and conformance of the identified logical page numbers with one or more predefined numbering patterns;

generating a mapping that maps each identified logical page number to one or more physical page numbers indicating pages of the document marked by the logical page number;

identifying a sequence of logical page number references comprising tokens in the document sequenced in the document in accordance with a reading order for the document;

selecting a sub-sequence of the sequence of logical page number references that maps to a nondecreasing sequence of physical page numbers according to the mapping, the selecting being biased toward selecting a long sub-sequence and being biased toward selecting a dense sub-sequence; and

associating the logical page number references of the selected sub-sequence with the corresponding physical page numbers of the mapped nondecreasinq sequence of physical page numbers.

9. The apparatus as set forth in claim 8 , wherein the selecting comprises:

biasing the selecting toward selecting a dense sub-sequence respective to distribution of the logical page number references in the document by limiting the selecting to selecting at least one of:

(i) a sub-sequence of the sequence of logical page number references that spans no more than a predefined fraction of pages of the document,

(ii) a sub-sequence of the sequence of logical page number references that spans no more than a predefined number of pages of the document, and

(iii) a sub-sequence of the sequence of logical page number references for which the average distance within the document between logical page number references of the sub-sequence is no larger than a maximum average distance.

10. The apparatus as set forth in claim 8 , wherein the selecting comprises:

biasing the selecting toward selecting a long sub-sequence by selecting the longest sub-sequence of the sequence of logical page number references that maps to a nondecreasing sequence of physical page numbers according to the mapping while also satisfying a sequence density criterion.

11. The apparatus as set forth in claim 8 , wherein the selecting comprises:

identifying a logical page number reference for which the corresponding logical page number is degenerate and occurs on two or more different pages, and

resolving the degeneracy to associate the logical page number reference with a single page of the document.

12. The apparatus as set forth in claim 11 , wherein the resolving comprises:

selecting one of the two or more different pages on which the degenerate logical page number occurs in order to optimize a figure of merit biasing toward selecting a long sub-sequence and biasing toward selecting a dense sub-sequence respective to distribution of the logical page number references in the document.

13. The apparatus as set forth in claim 8 , wherein the identifying logical page numbers of the document comprises:

identifying logical page numbers in the document based on both:

commonality of a single marginal location of the identified logical page numbers in the pages of the document, and

conformance of the identified page numbers with one or more predefined numbering patterns.

14. A non-transitory storage medium storing instructions executable on a digital processing device to perform a method operating on a document having a reading order and being paginated into an ordered sequence of pages with each page having a physical page number indicating its location in the ordered sequence of pages, the method including:

identifying logical page numbers comprising tokens in pages of the document based on at least one of commonality of a single marginal location of the identified logical page numbers in the pages of the document and conformance of the identified logical page numbers with one or more predefined numbering patterns;

generating a mapping that maps each identified logical page number to one or more physical page numbers indicating pages of the document marked by the logical page number;

identifying a sequence of logical page number references comprising tokens in the document sequenced in the document in accordance with a reading order for the document;

selecting a sub-sequence of the sequence of logical page number references that maps to a nondecreasing sequence of physical page numbers according to the mapping, the selecting being biased toward selecting a long sub-sequence and being biased toward selecting a dense sub-sequence; and

associating the logical page number references of the selected sub-sequence with the corresponding physical page numbers of the mapped nondecreasing sequence of physical page numbers.

15. The non-transitory storage medium as set forth in claim 14 , wherein the identifying comprises identifying zero or one logical page number for each page of the document.

16. The non-transitory storage medium as set forth in claim 14 , wherein the selecting a sub-sequence of the sequence of the logical page number references includes resolving one or more references to one or more degenerate logical page numbers in the sequence of logical page number references.

17. The method as set forth in claim 1 , wherein the identifying operation (ii) omits from consideration as logical page number references those tokens comprising the logical page numbers.

Assignments (9)

Continuity (1)