Methods for efficient cluster analysis

• US 8,892,992 B2
• Filed: 07/20/2012
• Issued: 11/18/2014
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mansfield, Philip Andrew, Levy, Michael Robert
• Primary Examiner(s): HUYNH, THU V
• Application Number:
  US13/555,053
• Publication Number:
  US 20130042172A1
• Time in Patent Office: 851 Days
• Field of Search: 715/234, 715243-247, 715255-256, 715/270, 715/272
• 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 non-transitory machine readable medium storing a program which when executed by at least one processor defines structure for a document comprising a plurality of primitive elements, the program comprising sets of instructions for:

defining an indirectly sorted first array that stores sorted indices of a second array of difference values, wherein the difference values indicate differences between sorted attribute values of different primitive elements, the primitive elements being defined in terms of the attribute values;

using the indirectly sorted first array to generate a plurality of different partition sets at different distance scales for the plurality of primitive elements;

from the plurality of partition sets, selecting an optimal partition set based on a set of optimization measures; and

grouping the plurality of primitive elements using the optimal partition set in order to associate a subset of the primitive elements as a structured element in the document.

2. The non-transitory machine readable medium of claim 1, wherein the plurality of primitive elements are a set of glyphs in the document, the attribute values are location values of the primitive elements in the document, and the subsets of primitive elements are words in the document.

3. The non-transitory machine readable medium of claim 1, wherein the set of instructions for using the indirectly sorted first array to generate the plurality of different partition sets comprises a set of instructions for generating all possible partition sets of the primitive elements.

4. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for storing the distance scale used for the selected optimal partition set for later use in partitioning a different plurality of primitive elements.

5. The non-transitory machine readable medium of claim 1, wherein each different partition set divides the plurality of primitive elements into different subsets of primitive elements.

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

identifying pairs of nearest primitive elements in a document comprising a plurality of primitive elements that are defined in terms of their position in the document;

sorting the pairs of nearest primitive elements based on an order from a pair of nearest primitive elements that are a closest distance apart to a pair of nearest primitive elements that are a furthest distance apart;

storing a single value that identifies, from the sorted pairs of nearest primitive elements, a particular pair of nearest primitive elements whose primitive elements are a minimum distance apart to form a partition, wherein each pair of nearest primitive elements that are a greater distance apart than the minimum distance is after the particular pair in the order;

identifying partitions between the primitive elements in the document based on the single value and the sorted pairs of nearest primitive elements; and

using the partitions to define structural elements for the document.

7. The method of claim 6 further comprising defining a structured document based on the structural elements and the primitive elements.

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

9. The method of claim 6, wherein storing the single value comprises storing a plurality of single values that each identify different pairs of nearest primitive elements whose primitive elements are different minimum distances apart to form partitions.

10. The method of claim 9 further comprising analyzing the different partitions for the primitive elements in order to identify an optimal partition representing an optimal distance scale.

11. A method for defining a structure for a document comprising a plurality of primitive elements, the method comprising:

defining an indirectly sorted first array that stores sorted indices of a second array of difference values, wherein the difference values indicate differences between sorted attribute values of different primitive elements, the primitive elements being defined in terms of the attribute values;

using the indirectly sorted first array to generate a plurality of different partition sets at different distance scales for the plurality of primitive elements;

from the plurality of partition sets, selecting an optimal partition set based on a set of optimization measures; and

grouping the plurality of primitive elements using the optimal partition set in order to associate a subset of the primitive elements as a structured element in the document.

12. The method of claim 11, wherein the plurality of primitive elements are a set of glyphs in the document, the attribute values are location values of the primitive elements in the document, and the subsets of primitive elements are words in the document.

13. The method of claim 11, wherein using the indirectly sorted first array to generate the plurality of different partition sets comprises generating all possible partition sets of the primitive elements.

14. The method of claim 11 further comprising storing the distance scale used for the selected optimal partition set for later use in partitioning a different plurality of primitive elements.

15. The method of claim 11, wherein each different partition set divides the plurality of primitive elements into different subsets of primitive elements.

16. An apparatus comprising:

a set of processing units for executing sets of instructions;

a machine readable medium storing a program which when executed by at least one of the processing units defines a program for defining structure for a document, the program comprising sets of instructions for;

identifying pairs of nearest primitive elements in a document comprising a plurality of primitive elements that are defined in terms of their position in the document;

sorting the pairs of nearest primitive elements based on an order from a pair of nearest primitive elements that are a closest distance apart to a pair of nearest primitive elements that are a furthest distance apart;

storing a single value that identifies, from the sorted pairs of nearest primitive elements, a particular pair of nearest primitive elements whose primitive elements are a minimum distance apart to form a partition, wherein each pair of nearest primitive elements that are greater distance apart than the minimum distance is after the particular pair in the order;

identifying partitions between the primitive elements in the document based on the single value and the sorted pairs of nearest primitive elements; and

using the partitions to define structural elements for the document.

17. The apparatus of claim 16, wherein the program further comprises a set of instructions for defining a structured document based on the structural elements and the primitive elements.

18. The apparatus of claim 17, wherein the structured document is a hierarchical structure in which the structural elements are nodes.

19. The apparatus of claim 16, wherein the set of instructions for storing the single value comprises a set of instructions for storing a plurality of single values that each identify different nearest pairs of primitive elements whose primitive elements are different minimum distances apart to form partitions.

20. The apparatus of claim 19, wherein the program further comprises a set of instructions for analyzing the different partitions for the primitive elements in order to identify an optimal partition representing an optimal distance scale.