Efficient data structures for parsing and analyzing a document

• US 9,575,945 B2
• Filed: 04/19/2013
• Issued: 02/21/2017
• 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
• Application Number:
  US13/866,493
• Publication Number:
  US 20130311490A1
• Time in Patent Office: 1,404 Days
• US Class Current: 1/1
• 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:

receiving an unstructured document comprising a plurality of primitive elements, wherein each of the plurality of primitive elements is a character;

performing a plurality of different processes for analyzing and manipulating the unstructured document in order to generate a structured document from the unstructured document; and

storing a plurality of references associated with the plurality of primitive elements, wherein each of the references refers to a different primitive element of the plurality of primitive elements, wherein at least some of the references are stored in a separate memory space from the plurality of different processes and are shared by at least two different processes of the plurality of different processes, wherein the two different processes access the plurality of references by use of objects that refer to the plurality of references, wherein the plurality of references are not replicated by the two different processes.

2. The method of claim 1, wherein the plurality of references are stored in a first storage, the method further comprising:

parsing the unstructured document to identify the plurality of primitive elements; and

storing the plurality of primitive elements in a second storage.

3. The method of claim 2, wherein the identified primitive elements are in a random order, wherein the primitive elements are stored in the random order in the second storage.

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

5. The method of claim 2 further comprising sorting the plurality of primitive elements according to a particular metric, wherein the plurality of references are stored in the first storage in a sorted order.

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

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

8. The method of claim 1, wherein the plurality of references are stored in an array and the objects refer to the plurality of references by using pointers that point to the references within the array.

9. The method of claim 1, wherein the plurality of references are not replicated by the plurality of different processes.

10. A system comprising:

a set of processors for executing sets of instructions; and

a non-transitory machine readable medium storing a program for execution by at least one of the processors, the program comprising sets of instructions for;

receiving an unstructured document comprising a plurality of primitive elements, wherein each of the plurality of primitive elements is a character;

performing a plurality of different processes for analyzing and manipulating the unstructured document in order to generate a structured document from the unstructured document; and

storing a plurality of references associated with the plurality of primitive elements, wherein each of the references refers to a different primitive element of the plurality of primitive elements, wherein at least some of the references are stored in a separate memory space from the plurality of different processes and are shared by at least two different processes of the plurality of different processes, wherein the two different processes access the plurality of references by use of objects that refer to the plurality of references, and wherein the plurality of references are not replicated by the two different processes.

11. The system of claim 10, wherein the plurality of different processes comprises:

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

a process for associating sets of characters as words.

12. The system of claim 11, wherein:

the process for associating sets of characters as lines of text stores a particular line of text as a first object that refers to a first subset of the references; and

the process for associating sets of characters as words stores a particular word as a second object that refers to a second subset of the references.

13. The system of claim 12, wherein the first subset of the references comprises the second subset of the references, wherein the second subset of the references are used by both processes without replication.

14. The system of claim 12, wherein each of the first and second objects refer to their corresponding subsets of the references by storing only two values.

15. The system of claim 10, wherein the set of instructions for storing the plurality of references associated with the primitive elements comprises a set of instructions for storing the plurality of references in a shared memory data structure.

16. A system comprising:

a set of processors for executing sets of instructions; and

a non-transitory machine readable medium storing a program for execution by at least one of the processors, the program comprising sets of instructions for;

receiving an unstructured comprising a plurality of primitive elements, wherein each of the plurality of primitive elements is a character;

performing a plurality of different processes for analyzing and manipulating the unstructured document in order to generate a structured document from the unstructured document, wherein the plurality of different processes comprises (i) a first process for associating sets of characters as a line of text and storing the line of text as a first string and (ii) a second process for associating sets of characters as a word and storing the word as a second string; and

storing 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, and wherein the data is not replicated by the processes,

wherein the first and second strings reference a same piece of data associated with the primitive elements, wherein the first string comprises a reference to the same piece of data and a first count of a number of characters in the first string, wherein the second string comprises the reference to the same piece of data and a second count of a number of characters in the second string.

17. The system of claim 16, wherein the set of instructions for storing data associated with the primitive elements comprises a set of instructions for storing the references to the data in a shared memory data structure.

18. The system of claim 16, wherein the first string and the second string store different counts.

19. The system of claim 16, wherein the data comprises a plurality of references that each refer to a different primitive element of the plurality of primitive elements.

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

receiving an unstructured document comprising a plurality of primitive elements, wherein each of the plurality of primitive elements is a character;

performing a plurality of different processes for analyzing and manipulating the unstructured document in order to generate a structured document from the unstructured document; and

storing a plurality of references associated with the plurality of primitive elements, wherein each of the references refers to a different primitive element of the plurality of primitive elements, wherein at least some of the references are stored in a separate memory space from the plurality of different processes and are shared by at least two different processes of the plurality of different processes, wherein the two different processes access the plurality of references by use of objects that refer to the plurality of references, and wherein the plurality of references are not replicated by the two different processes.

21. The non-transitory machine readable medium of claim 20, wherein the set of instructions for storing the plurality of references associated with the primitive elements comprises a set of instructions for storing the plurality of references in a shared memory data structure.

22. The non-transitory machine readable medium of claim 21, wherein the shared memory data structure is for storing a location in the separate memory space at which the plurality of references associated with the primitive elements is stored.

23. The non-transitory machine readable medium of claim 21, wherein the shared memory data structure is for storing a number of objects that refer to the plurality of references associated with the primitive elements.

24. The non-transitory machine readable medium of claim 21, wherein the shared memory data structure is for use when at least two objects refer to the plurality of references associated with the primitive elements.

25. The non-transitory machine readable medium of claim 24, wherein the two objects share ownership of the plurality of references associated with the primitive elements.