Structuring document based on table of contents

• US 8,302,002 B2
• Filed: 04/27/2005
• Issued: 10/30/2012
• Est. Priority Date: 04/27/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dejean, Herve, Meunier, Jean-Luc
• Primary Examiner(s): Hutton, Jr., Doug
• Application Number:
  US11/116,100
• Publication Number:
  US 20060248070A1
• Time in Patent Office: 2,743 Days
• Field of Search: 715234-236, 715/239, 715/256
• US Class Current: 715/256
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines

Abstract

A document is organized as a plurality of nodes associated with a table of contents. The nodes are clustered into a plurality of clusters based on a similarity criterion. One of the clusters is identified as corresponding to a highest or lowest level of the table of contents based on a selection criterion. The highest or lowest level is assigned to the nodes belonging to the identified cluster. The identifying and assigning are repeated to assign levels to the nodes belonging to each next highest or lowest level of the table of contents. The repeated identifying is based on the selection criteria applied disregarding nodes that have already been assigned a level. The document is structured based at least in part on the levels assigned to the table of contents nodes.

Claims

1. A method for reconstructing a table of contents hierarchy, the method comprising:

clustering nodes associated with a table of contents into a plurality of flat clusters that are not arranged hierarchically based on a similarity criterion;

assigning the nodes of each flat cluster to a level of the table of contents corresponding to that flat cluster;

validating the assigned levels of the nodes; and

taking a remedial action responsive to a validation failure;

wherein at least the clustering, assigning, and validating are performed by a processor.

2. The method as set forth in claim 1, wherein the assigning of the nodes of each cluster to a level of the table of contents corresponding to that cluster comprises:

identifying one of the clusters as corresponding to a highest or lowest level of the table of contents based on a selection criterion;

assigning the highest or lowest level to the nodes belonging to the identified cluster;

repeating the identifying and assigning to assign levels to the nodes belonging to each next highest or lowest level of the table of contents, the repeated identifying being based on the selection criteria applied disregarding nodes that have already been assigned a level.

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

determining whether any immediately succeeding node has an assigned level more than one level lower than the assigned level of the previous node, a validation failure being indicated by any succeeding node having an assigned level more than one level lower than the assigned level of the previous node.

4. The method as set forth in claim 1, further comprising:

repeating the clustering based on a revised similarity criterion conditional upon the plurality of clusters including a cluster containing only a single node.

5. The method as set forth in claim 1, further comprising:

conditional upon successful validation, structuring the document based at least in part on the levels assigned to the table of contents nodes.

6. A method for structuring a document, the method comprising:

clustering nodes of the document associated with a table of contents into a plurality of clusters based on a similarity criterion, the plurality of clusters not being arranged hierarchically;

identifying one of the clusters as corresponding to a highest or lowest level of the table of contents based on a selection criterion;

assigning the highest or lowest level to the nodes belonging to the identified cluster;

iteratively applying the identifying and assigning to assign levels to the nodes belonging to each next highest or lowest level of the table of contents, the iterating being based on the selection criteria applied disregarding nodes that have already been assigned a level; and

structuring the document based at least in part on the levels assigned to the table of contents nodes;

wherein the clustering, identifying, assigning, iterating, and structuring are performed by an apparatus including a processor.

7. The method as set forth in claim 6, wherein the similarity criterion is defined by a combination of one or more criteria operating on at least one of (i) the nodes, and (ii) corresponding entries of the table of contents.

8. The method as set forth in claim 6, wherein the identity comprises:

computing for each cluster an adjacency ratio of (i) a number of nodes of the cluster having a neighboring node belonging to the same cluster and (ii) a total number of nodes in the cluster; and

identifying the cluster corresponding to the lowest level of the table of contents as that cluster having the highest adjacency ratio.

9. The method as set forth in claim 6, further comprising:

repeating the nodes clustering using a revised similarity criterion conditional upon one or more of the clusters containing only a single node.

10. The method as set forth in claim 6, further comprising:

converting a source document into the document organized as the plurality of nodes.

11. The method as set forth in claim 10, wherein the source document is in a portable document format (pdf) and the converting converts the source pdf document into an extensible markup language (XML) document.

12. The method as set forth in claim 10, further comprising:

associating nodes of the document with a table of contents of the document.

13. A method for structuring a document organized as a plurality of nodes associated with a table of contents, the method comprising:

clustering the nodes into a plurality of clusters based on a similarity criterion, the clustering producing flat clusters that are not arranged hierarchically;

identifying one of the clusters as corresponding to a highest or lowest level of the table of contents based on a selection criterion;

assigning the highest or lowest level to the nodes belonging to the identified cluster;

repeating the identifying and assigning to assign levels to the nodes belonging to each next highest or lowest level of the table of contents, the repeated identifying being based on the selection criteria applied disregarding nodes that have already been assigned a level; and

structuring the document based at least in part on the levels assigned to the table of contents nodes;

wherein the clustering, identifying, assigning, repeating, and structuring are performed by a processor.

14. The method as set forth in claim 13, wherein the similarity criterion is defined by a combination of one or more criteria selected from a group consisting of:

font characteristics of corresponding table of contents entries,

font characteristics of headings of the nodes,

indentation of corresponding table of contents entries,

indentation of headings of the nodes,

level-indicative symbols included in corresponding table of contents entries,

level-indicative symbols included in headings of the nodes,

lexical or semantic analysis of corresponding table of contents entries, and

lexical or semantic analysis of the nodes.

15. The method as set forth in claim 13, wherein the identifying comprises:

for each cluster, computing an adjacency ratio of (i) a number of nodes of the cluster having a neighboring node belonging to the same cluster and (ii) a total number of nodes in the cluster; and

identifying the cluster corresponding to the lowest level of the table of contents as that cluster having the highest adjacency ratio.

16. The method as set forth in claim 13, wherein the identifying comprises:

for each cluster, computing an adjacency ratio of (i) a number of nodes of the cluster having a neighboring node belonging to the same cluster and (ii) a total number of nodes in the cluster; and

identifying the cluster corresponding to the highest level of the table of contents as that cluster having the lowest adjacency ratio.

17. The method as set forth in claim 13, further comprising:

validating the assigned levels of the nodes; and

taking a remedial action responsive to a validation failure;

wherein at least the validating is performed by a processor.

18. The method as set forth in claim 17, wherein the validating comprises:

determining whether any immediately succeeding node has an assigned level more than one level lower than the assigned level of the previous node, a validation failure being indicated by any succeeding node having an assigned level more than one level lower than the assigned level of the previous node.

19. The method as set forth in claim 13, wherein the structuring of the document based at least in part on the levels assigned to the table of contents nodes comprises:

generating a tree-based structuring of the document based on the levels assigned to the table of contents nodes.