Multi-level list detection engine

• US 9,384,172 B2
• Filed: 07/06/2012
• Issued: 07/05/2016
• Est. Priority Date: 07/06/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lukic, Dusan, Jitlin, Victor, Raskovic, Milos
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US13/808,052
• Publication Number:
  US 20150149893A1
• Time in Patent Office: 1,460 Days
• US Class Current: 1/1
• 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/151 Transformation
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

A multi-level list detection engine. The multi-level list detection engine detects text obtained from a fixed format document that is formatted as a static multi-level list and creates a dynamic multi-level list object in a flow format document. The resulting dynamic multi-level list object automatically updates as the end user edits the multi-level list in the flow format document. The multi-level list detection engine identifies list elements in the fixed format text based on the presence of a list identifier. The list elements are grouped into lists based on the properties of each list element relative to other list elements. List elements are then assigned to a list level based on the relative properties of the list elements within a list. Finally, level list assignments are verified and corrected, the levels are merged, as necessary, and the lists are consistently formatted as appropriate to create a final well-formed dynamic multi-level list object.

Claims

1. A method of converting a fixed format document into a flow format document including one or more multi-level lists that dynamically update when edited by an end user, said method comprising:

identifying each text object in a collection of text objects that begins with a list identifier as a list element, said text objects derived from said fixed format document;

creating a new list when said list element and a previous list element in said list do not have selected properties that are substantially similar;

adding said list element to an existing list when said list element and said previous list element in said list have said selected properties that are substantially similar;

assigning said list element to a list level based on said selected properties;

determining a list level format for each said list level based on common properties of list elements belonging to said list level;

determining a list format from each said list level format; and

merging list levels with common numbering schemes, including merging a lower list level having a first numbering scheme with a higher list level having a second numbering scheme when said first numbering scheme and said second numbering scheme use the same list format and said first numbering scheme and said second numbering scheme begin with a same list identifier.

2. The method of claim 1 characterized in that assigning said list element to a list level based on said selected properties further comprises assigning said list element to a new list level when said list element does not continue a numbering sequence of the last list element in said list.

3. The method of claim 1 characterized in that assigning said list element to a list level based on said selected properties further comprises assigning said list element to the same list level as the last list element in said list when said list identifier of said list element follows said last list element list identifier in sequence.

4. The method of claim 1 characterized in that assigning said list element to a list level based on said selected properties further comprises assigning said list element to the highest list level in said list when said list identifier of said list element continues the numbering sequence of said first list level.

5. The method of claim 1 characterized in that assigning said list element to a list level based on said properties further comprises assigning said list element to a list level other than a highest list level when said list element has a list identifier comprising a multi-number.

6. The method of claim 1 wherein said first numbering scheme and said second numbering scheme begin with same number for said list identifier.

7. The method of claim 1 further comprises merging a lower said list level with a higher said list when said lower list level continues the numbering sequence of said higher list level.

8. The method of claim 1 further comprising discarding each said list containing a single list element.

9. The method of claim 1 further comprising moving at least one selected said list level into a separate list.

10. A system for generating a flow format document including a multi-level list object from a fixed format document, said system comprising:

a processing unit; and

a memory including computer executable instructions which, when executed by a computer, provide a multi-level list detection engine application operable to;

identify a first text object as a first list element when the first text object begins with a first list identifier;

create a first list beginning with a first list element;

add said first list element to a first list level having a first numbering sequence;

identify a second text object as a second list element when the second text object begins with a second list identifier;

determine whether said second list identifier continues said first numbering sequence;

add said second list element to said first list level when said second list identifier continues said first numbering sequence;

compare a first value corresponding to an indentation of one or more list elements in said first list level to a second value corresponding to an indentation of said second list element to obtain a first indentation comparison result;

add said second list element to a second list level having a second numbering sequence when said second list identifier does not continue said first numbering sequence, and said first indentation comparison result indicates that said indentation of said second list element is greater than said indentation of at least one list element in said first list level; and

merging list levels with common numbering schemes, including merging a lower list level having a first numbering scheme with a higher list level having a second numbering scheme when said first numbering scheme and said second numbering scheme use the same list format and said first numbering scheme and said second numbering scheme begin with a same list identifier.

11. The system of claim 10 characterized in that said multi-level list detection engine application is further operable to:

determine a list level format for each said list level based on selected properties of each list element in said first list belonging to the same list level; and

define a list format based on each said list level format.

12. The system of claim 10 characterized in that said multi-level list detection engine application is further operable to create a second list beginning with said second list element when said second indentation is less than said first indentation and said second list identifier does not continue said first numbering sequence.

13. The system of claim 10 characterized in that said multi-level list detection engine application is further operable to:

identify a third text object as a third list element when the third text object begins with a third list identifier;

determine whether said third list identifier continues said second numbering sequence;

add said third list element to said second list level when said third list identifier continues second first numbering sequence;

compare a third value corresponding to an indentation of said third list element to said first value to obtain a second indentation comparison result; and

add said third list element to a third list level when said third list identifier does not continue said second numbering sequence and said second indentation comparison result indicates that said indentation of said third list element is greater than said indentation of at least one list element in said first list level.

14. The system of claim 13 characterized in that said multi-level list detection engine application is further operable to create a second list beginning with said third list element when said third list element does not continue said first numbering sequence or said second numbering sequence and said second indentation comparison result indicates that said indentation of said third list element is less than or substantially equal to said indentation of at least one list element in said first list level.

15. The system of claim 10 characterized in that said multi-level list detection engine application is further operable to merge said third list level with said first list level when said list elements in said third list level continue said first numbering sequence.

16. A computer readable storage medium containing computer executable instructions which, when executed by a computer, perform a method of generating a flow format document including a multi-level list object from a fixed format document, said method comprising:

identifying a list element appearing in the text obtained from the fixed format document;

making a first comparison between at least one property associated with said list element and at least one list element appearing in a first list;

placing said list element in said first list when said first comparison has a first result;

making a second comparison between at least one property associated with said list element and a second list element appearing in a first list after said first list element;

assigning said second list element to a list level based on said second comparison;

making a third comparison between at least one property of said list element and other list elements in said first list at a selected list level;

adjusting said list level of said list element based on said third comparison; and

merging list levels with common numbering schemes, including merging a lower list level having a first numbering scheme with a higher list level having a second numbering scheme when said first numbering scheme and said second numbering scheme use the same list format and said first numbering scheme and said second numbering scheme begin with a same list identifier.

17. The computer readable medium of claim 16 characterized in that said list element appears after a first list element and a second list element in the text obtained from the fixed format document.

18. The computer readable medium of claim 16 characterized in that said method further comprises determining a list level format for each said list level based on selected properties of each list element belonging to the same list level.

19. The computer readable medium of claim 18 characterized in that said method further comprises defining a list format based on each list level format.

20. The computer readable medium of claim 16 characterized in that adjusting said list level of said list element based on said third comparison includes merging said list level containing said list element with said selected list level when said third comparison indicates that said list element belongs to said selected list level.