Structuring document based on table of contents

• US 20060248070A1
• Filed: 04/27/2005
• Published: 11/02/2006
• Est. Priority Date: 04/27/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Meunier, Jean-Luc, Dejean, Herve
• Granted Patent: US 8,302,002 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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;

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.

2. The method as set forth in claim 1, 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.

3. The method as set forth in claim 1, 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.

4. The method as set forth in claim 1, 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.

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

validating the assigned levels of the nodes; and

taking a remedial action responsive to a validation failure.

6. The method as set forth in claim 5, 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.

7. The method as set forth in claim 1, 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.

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

clustering nodes associated with a table of contents into a plurality of clusters based on a similarity criterion;

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

validating the assigned levels of the nodes; and

taking a remedial action responsive to a validation failure.

9. The method as set forth in claim 8, 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.

10. The method as set forth in claim 8, 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.

11. The method as set forth in claim 8, 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.

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

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

13. An apparatus for structuring a document, the apparatus comprising:

a nodes clustering module for clustering nodes of the document associated with a table of contents into a plurality of clusters based on a similarity criterion;

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

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

an iterator for iteratively applying the terminal level cluster identifier and the assignor 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.

14. The apparatus as set forth in claim 13, 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.

15. The apparatus as set forth in claim 13, wherein the terminal level cluster identifier comprises:

an adjacency ratio processor that for each cluster computes 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

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

16. The apparatus as set forth in claim 13, further comprising:

a clusters validator that re-applies the nodes clustering module using a revised similarity criterion conditional upon one or more of the clusters containing only a single node.

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

a document converter that converts a source document into the document organized as the plurality of nodes.

18. The apparatus as set forth in claim 17, wherein the source document is in a portable document format (pdf) and the document converter converts the source pdf document into an extensible markup language (XML) document.

19. The apparatus as set forth in claim 17, further comprising:

a table of contents detector that associates nodes of the document with a table of contents of the document.

20. The apparatus as set forth in claim 13, further comprising:

a high level document structuring processor that structures the document based at least in part on the levels assigned to the table of contents nodes.