Reconstruction of lists in a document

• US 8,886,676 B2
• Filed: 02/11/2013
• Issued: 11/11/2014
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Mansfield, Philip Andrew, Levy, Michael Robert
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/764,761
• Publication Number:
  US 20130227406A1
• Time in Patent Office: 638 Days
• Field of Search: 707600-899
• US Class Current: 707/791
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

Some embodiments provide a method for analyzing a document that includes several primitive elements. The method identifies that a set of primitive elements include an implicit list in the document based on location and appearance of the set of primitive elements. The method defines the identified implicit list as an explicit list. The method stores the explicit list as a structure associated with the document.

Claims

1. A method for analyzing a document comprising a plurality of primitive elements, the method comprising:

identifying a first set of hierarchically-organized lists in a first column and a second set of hierarchically-organized lists in a second column subsequent to the first column in the document, each of the first and second sets of hierarchically-organized lists comprising one or more list items identified by a list label;

determining that a first list in the first set of hierarchically-organized lists continues as a second list in the second set of hierarchically-organized lists based on an analysis of the list labels of a last list item in the first list and a first list item in the second list;

storing the first list and the second list as a single list structure associated with the document.

2. The method of claim 1, wherein determining that the first list in the first set of hierarchically-organized lists continues as the second list in the second set of hierarchically-organized lists comprises:

determining that the first list has an open end state and the second list has an open start state;

determining that an alphabet used for list labels in the first list is the same alphabet used for list labels in the second list; and

determining that a header of the first list item in the second list follows a header of the last list item in the first list according to the alphabet.

3. The method of claim 1 further comprising determining that a third list in the first set of hierarchically-organized lists continues as a fourth list in the second set of hierarchically-organized lists.

4. The method of claim 3, wherein a relationship between a level of the first list and a level of the third list is the same as a relationship between a level of the second list and a level of the fourth list.

5. The method of claim 1, wherein the second column is immediately after the first column in a reading order of the document.

6. The method of claim 1, wherein at least one column exists between the first column and the second column within a reading order of the document.

7. A machine readable medium storing a program which when executed by at least one processing unit analyzes a document comprising a plurality of primitive elements, the program comprising sets of instructions for:

identifying a first set of hierarchically-organized lists in a first column and a second set of hierarchically-organized lists in a second column subsequent to the first column in the document, each of the first and second sets of hierarchically-organized lists comprising one or more list items identified by a list label;

determining that a first list in the first set of hierarchically-organized lists continues as a second list in the second set of hierarchically-organized lists based on an analysis of the list labels of a last list item in the first list and a first list item in the second list; and

storing the first list and the second list as a single list structure associated with the document.

8. The machine readable medium of claim 7, wherein the set of instructions for determining that the first list in the first set of hierarchically-organized lists continues as the second list in the second set of hierarchically-organized lists comprises sets of instructions for:

determining that the first list has an open end state and the second list has an open start state;

determining that an alphabet used for list labels in the first list is the same alphabet used for list labels in the second list; and

determining that a header of the first list item in the second list follows a header of the last list item in the first list according to the alphabet.

9. The machine readable medium of claim 7, wherein the program further comprises a set of instructions for determining that a third list in the first set of hierarchically-organized lists continues as a fourth list in the second set of hierarchically-organized lists.

10. The machine readable medium of claim 9, wherein a relationship between a level of the first list and a level of the third list is the same as a relationship between a level of the second list and a level of the fourth list.

11. The machine readable medium of claim 7, wherein the second column is immediately after the first column in a reading order of the document.

12. The machine readable medium of claim 7, wherein at least one column exists between the first column and the second column within a reading order of the document.

13. A non-transitory machine readable medium storing a program which when executed by at least one processing unit analyzes a document comprising a plurality of primitive elements, the program comprising sets of instructions for:

identifying different sets of lists for different columns of the document, each column ordered within the document based on a reading order;

identifying a first list in a first column of the document that has an open end state;

identifying a second list, in a second column of the document subsequent to the first column in the reading order, that has an open start state;

determining that the first list in the first column continues as the second list in the second column of the document; and

storing the first list and the second list as a single list structure associated with the document.

14. The non-transitory machine readable medium of claim 13, wherein an alphabet used for list labels in the first list is a same alphabet used for list labels in the second list.

15. The non-transitory machine readable medium of claim 13, wherein an alignment, spacing and content of list items in the first list matches an alignment, spacing, and content of list items in the second list.

16. The non-transitory machine readable medium of claim 13, wherein the set of instructions for determining that the first list in the first column continues with the second list in the second column comprises sets of instructions for:

generating, using a label generation function, a next list item label for the first list; and

determining that the next list item label matches a label of a first list item of the second list in the second column.

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

detecting more than one matching list between the first column and the second column; and

comparing indentations of the matching lists to determine a best matching list between the first column and the second column.

18. The non-transitory machine readable medium of claim 13, wherein the second column in the document is immediately after the first column of the document in a reading order of the document.

19. The non-transitory machine readable medium of claim 13, wherein the program further comprises a set of instructions for determining that a third list in the first column continues as a fourth list in the second column.

20. The non-transitory machine readable medium of claim 19, wherein a relationship between a level of the first list and a level of the third list is the same as a relationship between a level of the second list and a level of the fourth list.

21. The non-transitory machine readable medium of claim 13, wherein the program further comprises a set of instructions for determining that a plurality of lists in the first column continue as a second plurality of lists in the second column with each list in the second plurality matched to a different list in the first plurality such that a set of all matched list levels in the second plurality are a monotonically increasing function of list levels to which they are matched in the first plurality.

22. A method for analyzing a document comprising a plurality of primitive elements, the method comprising:

identifying different sets of lists for different columns of the document, each column ordered within the document based on a reading order;

identifying a first list in a first column of the document that has an open end state;

identifying a second list, in a second column of the document subsequent to the first column in the reading order, that has an open start state;

determining that the first list in the first column continues as the second list in the second column of the document; and

storing the first list and the second list as a single list structure associated with the document.

23. The method of claim 22, wherein an alignment, spacing and content of list items in the first list matches an alignment, spacing, and content of list items in the second list.

24. The method of claim 22, wherein determining that the first list in the first column continues with the second list in the second column comprises:

generating, using a label generation function, a next list item label for the first list; and

determining that the next list item label matches a label of a first list item of the second list in the second column.

25. The method of claim 24 further comprising:

detecting more than one matching list between the first column and the second column; and

comparing indentations of the matching lists to determine a best matching list between the first column and the second column.