METHODS FOR EFFICIENT CLUSTER ANALYSIS

• US 20100174977A1
• Filed: 06/07/2009
• Published: 07/08/2010
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Levy, Michael Robert, Mansfield, Philip Andrew
• Granted Patent: US 8,261,186 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/10 Text processing natural language analysis G06F40/20; semantic analysis G06F40/30; processing or translation of natural language G06F40/40
• 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/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/126 Character encoding
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/163 Handling of whitespace
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Some embodiments provide a method for defining structure for an unstructured document that includes a number of primitive elements that are defined in terms of their position in the document. The method identifies a pairwise grouping of nearest primitive elements. The method sorts the pairwise primitive elements based on an order from the closest to the furthest pairs. The method stores a single value that identifies which of the pairwise primitive elements are sufficiently far apart to form a partition. The method uses the stored value to identify and analyze the partitions in order to define structural elements for the document.

Claims

1. A computer readable medium storing a computer program which when executed by at least one processor defines structure for a document comprising a plurality of primitive elements that are defined in terms of their position in the document, the computer program comprising sets of instructions for:

identifying, for a particular set of primitive elements, a pairwise grouping of nearest primitive elements in the set;

sorting the pairwise groupings of primitive elements based on an order from the closest to the furthest pairs;

storing a single value that identifies which of the pairwise groupings of primitive elements are sufficiently far apart to form a partition; and

using the stored single value to identify and analyze the partition in order to define structural elements for the document.

2. The computer readable medium of claim 1, wherein the computer readable medium is firmware of a handheld device.

3. The computer readable medium of claim 2, wherein the device is a cell phone.

4. The computer readable medium of claim 2, wherein the device is a media player.

5. The computer readable medium of claim 1, wherein the computer program further comprises a set of instructions for defining a structured document that comprises the structural elements and the primitive elements.

6. The computer readable medium of claim 1, wherein:

the document comprises a plurality of glyphs;

the computer program further comprises a set of instructions for associating sets of glyphs as words;

the particular set of primitive elements are leftmost glyphs of words; and

the set of instructions for using the stored single value to identify and analyze the partition in order to define structural elements comprises a set of instructions for defining left alignment guides for sets of aligned words.

7. The computer readable medium of claim 1, wherein:

the document comprises a plurality of glyphs;

the computer program further comprises a set of instructions for associating sets of glyphs as words;

the particular set of primitive elements are rightmost glyphs of words; and

the set of instructions for using the stored single value to identify and analyze the partition in order to define structural elements comprises a set of instructions for defining right alignment guides for sets of aligned words.

8. The computer readable medium of claim 1, wherein the particular set of primitive elements are primitive graphic elements and the set of instructions for using the stored single value to identify and analyze the partition in order to define structural elements comprises a set of instructions for associating nearby primitive graphic elements as structural graphic elements.

9. The computer readable medium of claim 1, wherein the primitive elements are glyphs, and the set of instructions for defining structural elements comprises a set of instructions for associating sets of nearby glyphs as words.

10. The computer readable medium of claim 9, wherein the set of instructions for identifying a pairwise grouping of nearest primitive elements comprises sets of instructions for:

identifying a set of glyphs with a common baseline;

sorting the set of glyphs based on coordinates of the glyphs in a first direction;

for each pair of consecutive glyphs in the sorted set, calculating a difference in coordinate values between the glyphs in the pair; and

storing the calculated differences in a first array.

11. The computer readable medium of claim 10, wherein the set of instructions for sorting the pairwise primitive elements based on an order from the closest to the furthest pairs comprises sets of instructions for:

sorting the calculated difference values; and

storing, in a second array, the indices of the first array that correspond to the sorted differences.

12. The computer readable medium of claim 11, wherein the index of the first array that stores a smallest difference value is stored as the value at the first index of the second array.

13. The computer readable medium of claim 11, wherein the computer program further comprises a set of instructions for determining a minimum difference between glyphs, wherein the stored single value is an index in the second array at which the index of the first array storing said minimum difference is stored.

14. The computer readable medium of claim 13, wherein the minimum difference represents gaps between words.

15. The computer readable medium of claim 13, wherein the set of instructions for using the stored value to identify and analyze the partitions comprises a set of instructions for splitting a third array that stores the sorted x-coordinate values at indices of the third array that are stored as values in the second array at all indices of the second array at and after the index stored as the single value.

16. The computer readable medium of claim 1, wherein the set of instructions for storing the single value comprises sets of instructions for storing a plurality of single values that each identify different partitions for the primitive elements.

17. The computer readable medium of claim 16, wherein the computer program further comprises analyzing the different partitions for the primitive elements in order to identify an ideal optimal partition representing an optimal distance scale.

18. The computer readable medium of claim 1, wherein the document is an unstructured document.

19. The computer readable medium of claim 1, wherein the document is a vector graphics document.

20. The computer readable medium of claim 1, wherein the document is a portable document format (PDF) document.

21. A method for defining a program for defining structure for a document, the method comprising:

defining a module for identifying a pairwise grouping of nearest primitive elements in a document comprising a plurality of primitive elements that are defined in terms of their position in the document;

defining a module for sorting the pairwise groupings of primitive elements based on an order from the closest to the furthest pairs;

defining a module for storing a single value that identifies which of the pairwise-grouped primitive elements are sufficiently far apart to form a partition; and

defining a module for using the stored value to identify and analyze the partitions in order to define structural elements for the document.

22. The method of claim 21 further comprising defining a module for defining a structured document based on the structural elements and the primitive elements.

23. The method of claim 22, wherein the structured document is a hierarchical structure in which the structural elements are nodes.