Document segmentation based on visual gaps

• US 7,676,745 B2
• Filed: 07/22/2008
• Issued: 03/09/2010
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Egnor, Daniel
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US12/177,587
• Publication Number:
  US 20080282151A1
• Time in Patent Office: 595 Days
• Field of Search: 715/234, 715/243, 715/246, 715/253, 715/273, 715/241, 715/255
• US Class Current: 715/243
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/163 Handling of whitespace

Abstract

A document may be segmented based on a visual model of the document. The visual model is determined according to an amount of visual white space or gaps that are in the document. In one implementation, the visual model is used to identify a hierarchical structure of the document, which may then be used to segment the document.

Claims

1. A method, performed by a computer system, the method comprising:

generating, by a processor associated with the computer system, a visual model of a document that includes a geographic signal;

identifying, by a processor associated with the computer system, a hierarchical structure of the document based on the visual model;

segmenting, by a processor associated with the computer system, the document based on the hierarchical structure and the visual model of the document; and

associating, by a processor associated with the computer system, a portion of the document as corresponding to the geographic signal, when the portion includes the geographic signal and when the portion is within a lowest level of the hierarchical structure that includes the geographic signal.

2. The method of claim 1, where generating the visual model of the document includes:

assigning values to elements, of the document, used to control the appearance of the document, the values quantifying an amount that the elements introduce visual gaps in a displayed version of the document.

3. The method of claim 2, where identifying the hierarchical structure of the document includes:

identifying higher levels of the hierarchical structure for the document as corresponding to assigned values that are larger than other assigned values.

4. The method of claim 2, where the elements of the document are hyper-text markup language (HTML) elements.

5. The method of claim 1, further comprising:

assigning values to elements, of the document, used to control the display of the document, the values quantifying an amount that the elements introduce visual gaps in a displayed version of the document; and

identifying the lowest level of the hierarchical structure based on a smallest value assigned to one of the elements, where the one of the elements surrounds the geographic signal.

6. The method of claim 1, where segmenting the document further includes:

associating sections of text surrounding the geographic signal with the geographic signal.

7. The method of claim 1, further comprising:

associating text in the document as text corresponding to the geographic signal when the text does not itself include the geographic signal and when the text is at a higher hierarchical level in the hierarchical structure than the geographic signal.

8. A computer-readable memory device containing programming instructions for execution by a processor, the computer-readable memory device comprising:

programming instructions to generate a visual model of a document that includes at least one geographic signal;

programming instructions to identify a hierarchical structure of the document based on the visual model; and

programming instructions for associating the at least one geographic signal with portions of the document based on the identified hierarchical structure of the document, the associating including associating text in the document as text corresponding to the at least one geographic signal when the text includes the geographic signal and when the text is within a lowest level of the hierarchical structure that includes the at least one geographic signal.

9. The computer-readable memory device of claim 8, further comprising:

programming instructions to assign values to elements of the document used to control a display of the document, the values quantifying an amount that the elements introduce visual gaps in a displayed version of the document; and

programming instructions to identify the lowest level of the hierarchical structure based on a minimum value of an element that surrounds the geographic signal.

10. The computer-readable memory device of claim 9, further comprising:

programming instructions to assign values to elements of the document used to control an appearance of the document, the values quantifying an amount that the elements introduce visual gaps in a displayed version of the document.

11. The computer-readable memory device of claim 9, further comprising:

programming instructions for associating additional text in the document as text corresponding to the geographic signal when the additional text does not itself include the geographic signal and when the text is at a higher hierarchical level in the hierarchical structure than the geographic signal.

12. A device, comprising:

a processor; and

a memory coupled to the processor and containing instructions that when executed by the processor cause the processor to;

identify a document that includes geographic signals,

segment the document into a plurality of sections that correspond to different ones of the identified geographic signals based on a visual layout of the document, and

index text in the plurality of sections of the document as corresponding to the geographic signals, the indexing including associating text in the document as text corresponding to one of the geographic signals when the text includes the one of the geographic signals and when the text is within a lowest level of the hierarchical structure that includes the one of the geographic signals.

13. The device of claim 12, where the text is indexed to correspond to business listings associated with the geographic signals.

14. The device of claim 12, where the instructions further cause the processor to:

associate text, that is at a higher hierarchical level than a level containing one of the geographic signals and does not itself include a geographic signal, with the geographic signal as header text.

15. The device of claim 12, when segmenting the document into a plurality of sections, the instructions further cause the processor to:

segment the document based on an amount of white space between elements in a displayed version of the document.

16. The device of claim 15, where the instructions further cause the processor to:

assign values to the elements of the documents, the values quantifying an amount of the white space between the elements; and

identifying higher hierarchical levels of the document as corresponding to assigned values that are larger than other assigned values.

17. A method, performed by a computer system, the method comprising:

identifying, by a processor of the computer system, a document that includes information associated with a location;

generating, by a processor of the computer system, a visual model of the document based on gaps between elements in the document;

assigning, by a processor of the computer system, weights to the elements based on a size of the gaps;

identifying, by a processor of the computer system, a hierarchical structure of the document, where levels of the hierarchical structure are based on the weights of the elements;

identifying, by a processor of the computer system, text surrounding the information associated with the location; and

associating by a processor of the computer system, a lowest one of the levels, that includes the text, with the information associated with the geographic location.

18. The method of claim 17, where the elements of the document include hyper-text markup language (HTML) elements.

19. The method of claim 17, where identifying the hierarchical structure of the document includes:

identifying higher hierarchical levels for the document as corresponding to larger weights.

20. The method of claim 17, where the information associated with the geographic location includes an address of a business.