Efficient Data Structures for Parsing and Analyzing a Document

• US 20100174976A1
• 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,438,472 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 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 method comprising:

defining a plurality of different processes for analyzing and manipulating a document comprising a plurality of primitive elements; and

defining a storage for data associated with the primitive elements, wherein at least some of the data is stored in a separate memory space from the processes and is shared by at least two different processes, wherein the processes access the data by use of references to the data, wherein the data is not replicated by the processes.

2. The method of claim 1, wherein the storage for data associated with the primitive elements is a first storage, the method further comprising defining a parser for (i) parsing the document to identify the primitive elements and (ii) storing the primitive elements in a second storage.

3. The method of claim 2, wherein the data associated with the primitive elements comprises references to the primitive elements in the second storage.

4. The method of claim 2, wherein the parser is for (i) parsing the document to identify the primitive elements in a random order and (ii) storing the primitive elements in the random order in the second storage.

5. The method of claim 2, wherein the random order is the order in which the primitive elements are defined in a bitstream representation of the document.

6. The method of claim 2 further comprising defining a module for (i) sorting the primitive elements according to a particular metric and (ii) storing the data associated with the primitive elements in the first storage in a sorted order.

7. The method of claim 6, wherein the primitive elements comprise information regarding their location in the document, wherein the particular metric is based on the location of the primitive elements.

8. The method of claim 6, wherein within a particular page of the document, the particular metric sorts the primitive elements top to bottom as a primary metric and left to right as a secondary metric.

9. The method of claim 1, wherein the primitive elements comprise a plurality of glyphs.

10. The method of claim 9, wherein the plurality of different processes comprises:

a process for associating sets of glyphs as lines of text; and

a process for associating sets of glyphs as words.

11. The method of claim 10, wherein:

the process for associating sets of glyphs as lines of text stores a particular line of text as a first string that references the data associated with the primitive elements; and

the process for associating sets of glyphs as words stores a particular word as a second string that references the same data associated with the primitive elements.

12. The method of claim 11, wherein the same data is for use by both processes without replication.

13. The method of claim 11, wherein each of the first and second strings reference the data by storing only two values.

14. The method of claim 13, 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.

15. The method of claim 13, wherein the first string and second string reference the same first piece of data and store different counts.

16. The method of claim 1 further comprising defining a shared memory data structure for managing the storage for data associated with the primitive elements.

17. The method of claim 16, wherein the shared memory data structure is for storing a location in the separate memory space at which the data associated with the primitive elements is stored.

18. The method of claim 16, wherein the shared memory data structure is for use when at least two other data structures reference the data associated with the primitive elements.

19. The method of claim 18, wherein the at least two other data structures share ownership of the data associated with the primitive elements.

20. The method of claim 16, wherein the shared memory data structure is for storing the number of other data structures that reference the data associated with the primitive elements.

21. A computer readable medium storing a computer program for execution by at least one processor, the computer program comprising sets of instructions for:

parsing a document comprising a plurality of primitive elements;

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

storing references to the primitive elements in a second storage in an order based on locations of the primitive elements in the document;

receiving instructions to perform a document reconstruction operation; and

performing the received instructions without storing any new references to the primitive elements.

22. The computer readable medium of claim 21, wherein the computer 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 primitive elements; and

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

23. The computer readable medium of claim 22, wherein the second storage and third storage are in the same physical storage.

24. A method comprising:

defining a first module 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;

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

defining a third module for storing a data structure that references a portion of the ordered references, the data structure comprising only a reference to a first one of the ordered references and a count value.

defining 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 method of claim 24, wherein when only the third module 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.

26. The method of claim 24, wherein the document is an unstructured document.

27. The method of claim 24, wherein the document is a vector graphics document.

28. The method of claim 24, wherein the document is a portable document format (PDF) document.