Efficient data structures for parsing and analyzing a document

• US 8,438,472 B2
• Filed: 06/07/2009
• Issued: 05/07/2013
• 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,842
• Publication Number:
  US 20100174976A1
• Time in Patent Office: 1,430 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 that parses an unstructured document that includes a number of primitive elements. The method stores the primitive elements in a random order in a first storage. The method stores references to the primitive elements in a second storage in an order based on locations of the primitive elements in the unstructured document. The method receives instructions to perform a document reconstruction operation. The method performs the received instructions without storing any new references to the primitive elements.

Claims

1. A non-transitory machine readable medium storing a program for execution by at least one processing unit, the program comprising sets of instructions for:

parsing an unstructured document comprising a plurality of primitive elements, wherein the plurality of primitive elements comprises a plurality of glyphs;

storing the primitive elements in a random order in a first array;

storing, in a second array, references to the stored primitive elements, the references ordered in the second array based on locations of the primitive elements in the document, wherein each of the references refers to a single primitive element in the first array;

receiving instructions to perform a document reconstruction operation that associates a portion of the primitive elements into a structural element in order to generate a structured document from the unstructured document; and

performing the received instructions to define the structural element using the references stored in the second array without storing any new references to the primitive elements.

2. The non-transitory machine readable medium of claim 1, wherein the program further comprises sets of instructions for:

receiving a second set of instructions to perform a second document reconstruction operation;

determining that performing the second document reconstruction operation requires new references to the stored primitive elements; and

storing new references to the stored primitive elements in a third array in an order different from that of the second array.

3. The non-transitory machine readable medium of claim 2, wherein the second array and third array are in a same physical storage.

4. The non-transitory machine readable medium of claim 1, wherein the random order is the order in which the primitive elements are defined in a bitstream representation of the document.

5. The non-transitory machine readable medium of claim 1, wherein the set of instructions for storing the references comprises sets of instructions for:

sorting the primitive elements according to a particular metric that sorts the primitive elements top to bottom as a primary metric and left to right as a secondary metric; and

storing the references in the second array based on the sort.

6. A system comprising:

a set of processing units for executing sets of instructions;

a memory for storing a program for execution by at least one of the processing units, the program comprising;

a first set of instructions for (i) parsing a document comprising a plurality of primitive elements and (ii) storing the primitive elements in a random order in a first storage, wherein the plurality of primitive elements comprises a plurality of glyphs;

a second set of instructions for (i) allocating memory in a second storage for storing a single reference for each of the randomly-ordered primitive elements and (ii) storing the references in a particular order in the allocated memory, wherein the particular order is based on the arrangement of the plurality of primitive elements in the document;

a third set of instructions for storing data structures for associating sets of the primitive elements with each other, each of the data structures comprising only a single reference to a first one of the ordered references in the second storage and a count value that indicates a number of the ordered references in the second storage associated with each other by the data structure; and

a fourth set of instructions for (i) receiving instructions to perform document reconstruction operations that associate sets of the primitive elements with each other in a particular order and (ii) identifying which of the first, second, and third sets of instructions is required to perform the document reconstruction operations while minimizing memory and computation usage.

7. The system of claim 6, wherein when only the third set of instructions is necessary to perform a particular document reconstruction operation, no new memory is allocated for either copies of the primitive elements or new references to the primitive elements.

8. The system of claim 6, wherein the document is an unstructured document.

9. The system of claim 6, wherein the document is a vector graphics document.

10. The system of claim 6, wherein the document is a portable document format (PDF) document.

11. The system of claim 6, wherein the third set of instructions is further for (i) associating sets of the glyphs as lines of text and (ii) associating sets of the glyphs as words.

12. The system of claim 11, wherein the third set of instructions is for associating sets of the glyphs as lines of text by storing a particular line of text as a first string that references the data associated with the primitive elements and for associating sets of glyphs as words by storing a particular word as a second string that references the same data associated with the primitive elements.

13. The system of claim 12, wherein the same data is for use without replication in associating sets of the glyphs as lines of text and in associating sets of the glyphs as words.

14. The system of claim 12, wherein each of the first and second strings reference the data by storing only two values.

15. The system of claim 14, wherein the two values are a reference to a first piece of data and a count of the number of pieces of data in the string.

16. The system of claim 14, wherein the first string and the second string reference the same first piece of data and store different counts.

17. A non-transitory machine readable medium storing a program for execution by at least one processing unit, the program comprising sets of instructions for:

receiving a document comprising a plurality of primitive elements, wherein the primitive elements each have a particular location in the document and wherein the plurality of primitive elements comprises a plurality of glyphs;

storing the primitive elements in a first storage in an order irrespective of their locations in the document;

storing a single reference to each of the stored primitive elements in a second storage in a first order based on the locations of the primitive elements;

performing a first document reconstruction operation that associates a first set of the primitive elements together as a first structural element of a structured document using the references stored in the second storage without storing any new references to the primitive elements; and

performing a second document reconstruction operation that associates a second set of the primitive elements together as a second structural element of the structured document by storing a new set of references to the stored primitive elements in a second, different order in the second storage.

18. The non-transitory machine readable medium of claim 17, wherein the first order is based on the locations of the primitive elements in the document from the top of the document to the bottom of the document.

19. The non-transitory machine readable medium of claim 17, wherein the first order is based on the locations of the primitive elements in the document from the left edge of the document to the right edge of the document.

20. The non-transitory machine readable medium of claim 17 further comprising managing the storage of data associated with the primitive elements using a shared memory data structure.

21. The non-transitory machine readable medium of claim 20, wherein the shared memory data structure is for use when at least two other data structures reference the data associated with the primitive elements.

22. The non-transitory machine readable medium of claim 20, wherein the shared memory data structure is for storing the number of other data structures that reference the data associated with the primitive elements.

23. The non-transitory machine readable medium of claim 21, wherein the at least two other data structures share ownership of the data associated with the primitive elements.

24. A non-transitory machine readable medium storing a program for execution by at least one processing unit, the program for analyzing documents, the program comprising:

a first module for (i) parsing a document comprising a plurality of glyphs, and (ii) storing the glyphs in a random order in a first storage;

a second module for (i) allocating memory in a second storage for storing references to the randomly-ordered glyphs and (ii) storing the references in a particular order in the allocated memory;

a third module for (i) associating sets of the glyphs as lines of text by storing a first string that references a first portion of the ordered references, (ii) associating sets of the glyphs as words by storing a second string that references a second portion of the ordered references, and (iii) associating sets of the glyphs as lines of text by storing a third string that references a third portion of the ordered references, wherein each string comprises only a reference to a first one of the ordered references and a count value; and

a fourth module for (i) receiving instructions to perform document reconstruction operations and (ii) identifying which of the first, second, and third modules is required to perform the document reconstruction operations while minimizing memory and computation usage.

25. The non-transitory machine readable medium of claim 24, wherein the same data is for use without replication in associating sets of glyphs as lines of text and in associating sets of glyphs as words.

26. The non-transitory machine readable medium of claim 24, wherein each of the first and second strings reference the data by storing only (i) a reference to a first glyph in the string and (ii) a count of the number of pieces of data in the string.

27. The non-transitory machine readable medium of claim 26, wherein the first string and the second string reference the same first glyph and store different counts.