Methods for efficient cluster analysis

• US 8,261,186 B2
• Filed: 06/07/2009
• Issued: 09/04/2012
• 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:
  US12/479,843
• Publication Number:
  US 20100174977A1
• Time in Patent Office: 1,185 Days
• Field of Search: 715/234, 715243-247, 715/255, 715/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 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 positions in the document, the computer program comprising sets of instructions for:

sorting a particular set of primitive elements in a first order based on their positions in the document;

calculating relative difference values between adjacent pairs of primitive elements in the first order based on their positions;

sorting the relative difference values of the pairs of primitive elements into a second order from closest to furthest pairs;

storing a single value from the second order that identifies which of the pairs of primitive elements are sufficiently far apart to form partitions between subsets of primitive elements; and

using the stored single value to identify and analyze the partitions 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 partitions 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 partitions 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 primitive elements in 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 partitions 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 computer program comprises a set of instructions for identifying a set of glyphs with a common baseline, wherein the set of instructions for sorting the particular set of primitive elements in a first order comprises a set of instructions for sorting the set of glyphs based on coordinates of the glyphs, wherein the set of instructions for calculating relative difference values comprises:

calculating, for each pair of consecutive glyphs in the sorted set, 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 relative difference values of the pairs of primitive elements into the second order from closest to furthest pairs comprises sets of instructions for:

sorting the calculated differences; and

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

12. The computer readable medium of claim 11, wherein an index of the first array that stores a smallest difference is stored as the value at a 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 the glyphs, wherein the stored single value is an index in the second array at which an 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 the 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 a set of x-coordinate values for the glyphs at indices of the third array according to the 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 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 attribute values, the computer program comprising sets of instructions for:

defining an indirectly sorted array by calculating difference values between adjacent pairs of sorted primitive elements based on their attribute values and storing indices of the calculated difference values in a sorted array as values of the indirectly sorted array;

using the indirectly sorted array to generate a plurality of different partition sets at different distance scales for the plurality of primitive elements, wherein each different partition set divides the plurality of primitive elements into different subsets 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 at least one subset of the primitive elements as a structured element in the document.

22. The computer readable medium of claim 21, wherein the plurality of primitive elements are a set of glyphs in the document and the subsets of primitive elements are words in the document.

23. The computer readable medium of claim 22, wherein the set of instructions for using the indirectly sorted array to generate a plurality of partition sets comprises a set of instructions for generating all possible partition sets of primitive elements.

24. The computer readable medium of claim 22, wherein the set of optimization measures comprises a set of density constraints.

25. The computer readable medium of claim 22, wherein the computer program further comprises a set of instructions for storing a distance scale used for the selected optimal partition for later use in partitioning a different plurality of primitive elements.

26. A method for defining structure for a document comprising a plurality of primitive elements that are defined in terms of their positions in the document, the method comprising:

sorting a particular set of primitive elements in a first order based on their positions in the document;

calculating relative difference values between adjacent pairs of primitive elements in the first order based on their positions;

sorting the relative difference values of the pairs of primitive elements into a second order from closest to furthest pairs;

storing a single value from the second order that identifies which of the pairs of primitive elements are sufficiently far apart to form partitions between subsets of primitive elements; and

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

27. The method of claim 26, wherein:

the document comprises a plurality of glyphs;

the method further comprises associating sets of glyphs as words;

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

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

28. The method of claim 26, wherein primitive elements in the particular set of primitive elements are primitive graphic elements and using the stored single value to identify and analyze the partitions in order to define structural elements comprises associating nearby primitive graphic elements as structural graphic elements.

29. The method of claim 26, wherein the primitive elements are glyphs, and defining structural elements comprises associating sets of nearby glyphs as words.

30. The method of claim 29 further comprising identifying a set of glyphs with a common baseline, wherein sorting the particular set of primitive elements in a first order comprises sorting the set of glyphs based on coordinates of the glyphs, and wherein calculating relative difference values comprises:

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

storing the calculated differences in a first array.

31. The method of claim 30, wherein sorting the relative difference values of the pairs of primitive elements into the second order from closest to furthest pairs comprises:

sorting the calculated differences; and

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

32. A method for defining structure for a document comprising a plurality of primitive elements that are defined in terms of attribute values, the method comprising:

defining an indirectly sorted array by calculating difference values between adjacent pairs of sorted primitive elements based on their attribute values and storing indices of the calculated difference values in a sorted array as values of the indirectly sorted array;

using the indirectly sorted array to generate a plurality of different partition sets at different distance scales for the plurality of primitive elements, wherein each different partition set divides the plurality of primitive elements into different subsets 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 at least one subset of the primitive elements as a structured element in the document.

33. The method of claim 32, wherein the plurality of primitive elements are a set of glyphs in the document and the subsets of primitive elements are words in the document.

34. The method of claim 33, wherein using the indirectly sorted array to generate a plurality of partition sets comprises generating all possible partition sets of primitive elements.

35. The method of claim 33, wherein the set of optimization measures comprises a set of density constraints.

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