Voting based scheme for electronic document node reuse

• US 20050175245A1
• Filed: 02/10/2004
• Published: 08/11/2005
• Est. Priority Date: 02/10/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sutanto, Herry, Wakeam, Jamie, Duncan, Richard, Szilagyi, Zoltan, Kannapel, Timothy H., Raghupathy, Sashi, Turner, Jerome
• Granted Patent: US 7,958,132 B2
• Time in Patent Office: Days
• US Class Current: 382/229
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• 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

Systems and methods for processing data transform a first data structure (e.g., a hierarchical data structure) into a second data structure (e.g., using a parsing system), wherein the second data structure includes a first set of leaf nodes under a first ancestor node (additional sets of leaf nodes and/or ancestor nodes also may be defined in the second data structure). One or more potential candidate nodes for the ancestor nodes may be identified based, at least in part, on the ancestor nodes from the first data structure associated with the leaf nodes grouped under the new ancestor nodes. In at least some examples, the leaf nodes grouped under a new ancestor node will “vote” for their original ancestor node, and the node receiving the most “votes,” in at least some instances, will be reused as the corresponding ancestor node in the second data structure.

Claims

1. A method, comprising:

transforming data from a first data structure to a second data structure, wherein the second data structure includes at least a first set of leaf nodes under a first ancestor node and a second set of leaf nodes under a second ancestor node;

identifying one or more potential candidate nodes for the first ancestor node based, at least in part, on ancestor nodes from the first data structure associated with the leaf nodes in the first set; and

identifying one or more potential candidate nodes for the second ancestor node based, at least in part, on ancestor nodes from the first data structure associated with the leaf nodes in the second set.

2. A method according to claim 1, further comprising:

assigning the first ancestor node based on the potential candidate node most often identified as associated with the leaf nodes in the first set.

3. A method according to claim 2, further comprising:

assigning the second ancestor node based on the potential candidate node most often identified as associated with the leaf nodes in the second set unless the potential candidate node most often identified as associated with the leaf nodes in the second set is the same as the potential candidate node most often identified as associated with the leaf nodes in the first set, and wherein when the potential candidate node most often identified as associated with the leaf nodes in the second set is the same as the potential candidate node most often identified as associated with the leaf nodes in the first set, then assigning the second ancestor node based on the potential candidate node second most often identified as associated with the leaf nodes in the second set or creating a new node for the second ancestor node.

4. A method according to claim 1, further comprising:

determining which potential candidate node to assign as the first ancestor node and which potential candidate node to assign as the second ancestor node, based, at least in part, on a determination of which arrangement of potential candidate nodes will most reduce data processing operations when converting an original document data structure to a form represented by the second data structure.

5. A computer-readable medium having computer-executable instructions stored thereon for performing the method of claim 1.

6. A method, comprising:

transforming data from a first data structure to a second data structure, wherein the second data structure includes at least a first set of leaf nodes under a first ancestor node; and

identifying one or more potential candidate nodes for the first ancestor node based, at least in part, on parent nodes from the first data structure associated with the leaf nodes in the first set.

7. A method according to claim 6, further comprising:

determining which potential candidate node to assign as the first ancestor node based, at least in part, on the potential candidate node most often identified as associated with the leaf nodes in the first set.

8. A method according to claim 7, wherein the determining further is based, at least in part, on a determination of which arrangement of potential candidate nodes will most reduce data processing operations when converting an original document data structure to a form represented by the second data structure.

9. A method according to claim 6, further comprising:

determining which potential candidate node to assign as the first ancestor node; and

assigning the first ancestor node based on the determined potential candidate node.

10. A method according to claim 9, further comprising:

creating a revised document data structure based on the second data structure and the assigned potential candidate node.

11. A method according to claim 6, wherein the data in the first data structure represents electronic ink data.

12. A method according to claim 6, wherein the transforming includes parsing electronic ink data into a hierarchical data structure corresponding to the second data structure.

13. A computer-readable medium having computer-executable instructions stored thereon for performing the method of claim 6.

14. A system, comprising:

a computer-readable medium containing data representing a first data structure; and

a processor programmed and adapted to;

(a) transform the data in the first data structure to a second data structure, wherein the second data structure includes at least a first set of leaf nodes under a first ancestor node and a second set of leaf nodes under a second ancestor node;

(b) identify one or more potential candidate nodes for the first ancestor node based, at least in part, on ancestor nodes from the first data structure associated with the leaf nodes in the first set; and

(c) identify one or more potential candidate nodes for the second ancestor node based, at least in part, on ancestor nodes from the first data structure associated with the leaf nodes in the second set.

15. A system according to claim 14, wherein the processor is further programmed and adapted to assign the first ancestor node based on the potential candidate node most often identified as associated with the leaf nodes in the first set.

16. A system according to claim 15, wherein the processor is further programmed and adapted to assign the second ancestor node based on the potential candidate node most often identified as associated with the leaf nodes in the second set unless the potential candidate node most often identified as associated with the leaf nodes in the second set is the same as the potential candidate node most often identified as associated with the leaf nodes in the first set, and wherein when the potential candidate node most often identified as associated with the leaf nodes in the second set is the same as the potential candidate node most often identified as associated with the leaf nodes in the first set, then the processor is further programmed and adapted to assign the second ancestor node based on the potential candidate node second most often identified as associated with the leaf nodes in the second set or create a new node for the second ancestor node.

17. A system according to claim 14, wherein the processor is further programmed and adapted to determine which potential candidate node to assign as the first ancestor node and which potential candidate node to assign as the second ancestor node based, at least in part, on a determination of which arrangement of potential candidate nodes will most reduce data processing operations when converting an original document data structure to a form represented by the second data structure.

18. A system, comprising:

a computer-readable medium containing data representing a first data structure; and

a processor programmed and adapted to;

(a) transform data in the first data structure to a second data structure, wherein the second data structure includes at least a first set of leaf nodes under a first ancestor node; and

(b) identify one or more potential candidate nodes for the first ancestor node based, at least in part, on ancestor nodes from the first data structure associated with the leaf nodes in the first set.

19. A system according to claim 18, wherein the processor is further programmed and adapted to determine which potential candidate node to assign as the first ancestor node based, at least in part, on the potential candidate node most often identified as associated with the leaf nodes in the first set.

20. A system according to claim 19, wherein the determining further is based, at least in part, on a determination of which arrangement of potential candidate nodes will most reduce data processing operations when converting an original document data structure to a form represented by the second data structure.

21. A system according to claim 18, wherein the processor is further programmed and adapted to:

(c) determine which potential candidate node to assign as the first ancestor node; and

(d) assign the first ancestor node based on the determined potential candidate node.

22. A system according to claim 21, wherein the processor is further programmed and adapted to create a revised document data structure based on the second data structure and the assigned potential candidate node.

23. A system according to claim 18, wherein the data in the first data structure represents electronic ink data.

24. A system according to claim 18, wherein the transforming includes parsing electronic ink data into a hierarchical data structure corresponding to the second data structure.