Document division method and system

• US 9,390,077 B2
• Filed: 02/10/2012
• Issued: 07/12/2016
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Smith, Benjamin J
• Application Number:
  US13/370,981
• Publication Number:
  US 20150193407A1
• Time in Patent Office: 1,614 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting

Abstract

Computer-readable media stores instructions that perform operations including receiving a first electronic document; determining a first information gain value associated with a first line that divides the first electronic document into a first portion and a second portion; determining a second information gain value associated with a second line that divides the first electronic document into a third portion and a fourth portion; and determining which of the first information gain value and second information gain value is greater. Information gain values are determined by calculating a difference between an entropy value associated with a line and an entropy value associated with an electronic document. Entropy values associated lines or electronic documents are determined based at least in part on document objects in the portions created by a line or an electronic document.

Claims

1. One or more tangible non-transitory computer-readable media storing instructions that, when executed by a processor, perform operations comprising:

receiving a first electronic document;

determining an entropy value for the first electronic document;

determining a first information gain value associated with a first line that divides the first electronic document into a first portion and a second portion, comprising;

a) determining an entropy value for the first portion of the first electronic document and an entropy value for the second portion of the first electronic document,

b) based on the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document, determining an entropy value associated with the first line, and

c) determining the first information gain value by determining a difference between i) the entropy value for the first electronic document and ii) the entropy value associated with the first line;

determining a second information gain value associated with a second line that divides the first electronic document into a third portion and a fourth portion, comprising;

a) determining an entropy value for the third portion of the first electronic document and an entropy value for the fourth portion of the first electronic document,

b) based on the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document, determining an entropy value associated with the second line, and

c) determining the second information gain value by determining a difference between i) the entropy value for the first electronic document and ii) the entropy value associated with the second line;

determining which of the first information gain value and second information gain value is greater;

in response to determining that the first information gain value is greater, generating a second electronic document that includes at least a portion defined by the first line and using the first information gain value to recursively divide the portions defined by the first line;

in response to determining that the second information gain value is greater, generating a third electronic document that includes at least a portion defined by the second line and using the second information gain value to recursively divide the portions defined by the second line,

wherein the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the first line intersects in the first electronic document, and the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the second line intersects in the first electronic document.

2. The tangible non-transitory computer-readable media of claim 1, wherein the entropy values for each portion of the first electronic document are each based at least on a number of document objects within the respective portion of the first electronic document.

3. The tangible non-transitory computer-readable media of claim 1, wherein determining the first information gain value is further based on an area of the first portion of the first electronic document and an area of the second portion of the first electronic document, and wherein determining the second information gain value is further based on an area of the third portion of the first electronic document and an area of the fourth portion of the first electronic document.

4. The tangible non-transitory computer-readable media of claim 1, wherein the entropy values for each portion of the first electronic document are each based at least on an area of document objects within the respective portion of the first electronic document.

5. The tangible non-transitory computer-readable media of claim 2, further comprising:

defining a document object model tree based at least in part on parsing the document objects; and

determining a depth of document objects for particular pixels intersected by each of the first line and the second line.

6. One or more tangible non-transitory computer-readable media storing instructions that, when executed by a processor, perform operations comprising:

receiving a first electronic document;

dividing the first electronic document along a first line into a first portion and a second portion;

dividing the first electronic document along a second line into a third portion and a fourth portion;

determining a first information gain value based on the first division, comprising;

a) determining an entropy value for the first portion of the first electronic document and an entropy value for the second portion of the first electronic document,

b) based on the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document, determining an entropy value associated with the first line, and

c) determining the first information gain value by determining a difference between i) an entropy value for the first electronic document and ii) the entropy value associated with the first line;

determining a second information gain value based on the second division, comprising;

a) determining an entropy value for the third portion of the first electronic document and an entropy value for the fourth portion of the first electronic document,

b) based on the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document, determining an entropy value associated with the second line, and

c) determining the second information gain value by determining a difference between i) the entropy value for the first electronic document and ii) the entropy value associated with the second line;

selecting the division that produces the higher information gain value;

generating a second electronic document comprising the portions created by the selected division; and

using the highest information gain value to recursively divide the first electronic document into portions,

wherein the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the first line intersects in the first electronic document, and the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the second line intersects in the first electronic document.

7. The tangible non-transitory computer-readable media of claim 6, wherein the entropy values for each portion of the first electronic document are each based at least on a number of document objects within the respective portion of the first electronic document.

8. The tangible non-transitory computer-readable media of claim 6, wherein determining the first information gain value is further based on an area of the first portion of the first electronic document and an area of the second portion of the first electronic document, and wherein determining the second information gain value is further based on an area of the third portion of the first electronic document and an area of the fourth portion of the first electronic document.

9. The tangible non-transitory computer-readable media of claim 6, wherein the entropy values for each portion of the first electronic document are each based at least on an area of document objects within the respective portion of the first electronic document.

10. The tangible non-transitory computer-readable media of claim 7, further comprising:

defining a document object model tree based at least in part on parsing the document objects; and

determining a depth of document objects for particular pixels intersected by each of the first line and the second line.

11. A system comprising:

one or more computer processors; and

one or more non-transitory computer readable devices that include instructions that, when executed by the one or more computer processors, causes the processors to perform operations, the operations comprising;

receiving a first electronic document;

determining an entropy value for the first electronic document;

determining a first information gain value associated with a first line that divides the first electronic document into a first portion and a second portion, comprising;

a) determining an entropy value for the first portion of the first electronic document and an entropy value for the second portion of the first electronic document,

b) based on the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document, determining an entropy value associated with the first line, and

c) determining the first information gain value by determining a difference between i) the entropy value for the first electronic document and ii) the entropy value associated with the first line;

determining a second information gain value associated with a second line that divides the first electronic document into a third portion and a fourth portion, comprising;

a) determining an entropy value for the third portion of the first electronic document and an entropy value for the fourth portion of the first electronic document,

b) based on the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document, determining an entropy value associated with the second line, and

c) determining the second information gain value by determining a difference between i) the entropy value for the first electronic document and ii) the entropy value associated with the second line, wherein each of the entropy values is based at least in part on document objects in the respective portions of the first electronic document;

determining which of the first information gain value and second information gain value is greater;

in response to determining that the first information gain value is greater, generating a second electronic document that includes at least a portion defined by the first line and using the first information gain value to recursively divide the portions defined by the first line;

in response to determining that the second information gain value is greater, generating a third electronic document that includes at least a portion defined by the second line and using the second information gain value to recursively divide the portions defined by the second line,

wherein the entropy value for the first portion of the first electronic document and the entropy value for the second portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the first line intersects in the first electronic document, and the entropy value for the third portion of the first electronic document and the entropy value for the fourth portion of the first electronic document are based at least on a variation in pixel intensity for pixels that the second line intersects in the first electronic document.

12. The system of claim 11, wherein the entropy values for each portion of the first electronic document are each based at least on a number of document objects within the respective portion of the first electronic document.

13. The system of claim 11, wherein determining the first information gain value is further based on an area of the first portion of the first electronic document and an area of the second portion of the first electronic document, and wherein determining the second information gain value is further based on an area of the third portion of the first electronic document and an area of the fourth portion of the first electronic document.

14. The system of claim 11, wherein the entropy values for each portion of the first electronic document are each based at least on an area of document objects within the respective portion of the first electronic document.

15. The system of claim 12, wherein the operations further comprise:

defining a document object model tree based at least in part on parsing the document objects; and

determining a depth of document objects for particular pixels intersected by each of the first line and the second line.