Method and system for attaching information to words of a trie

• US 6,675,169 B1
• Filed: 09/07/1999
• Issued: 01/06/2004
• Est. Priority Date: 09/07/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hullender, Gregory N., Karlov, Donald D., Bennett, John R.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/390,182
• Time in Patent Office: 1,582 Days
• Field of Search: 707/100, 707/532, 707/533, 707/101, 707/103.Y, 704/9, 704/10, 715/532, 715/533
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A method and improved data structure for attaching information to words in a trie of nodes. Each node of a trie includes a single tag bit which is interpreted according to information specified in a header of the trie. The information may specify that a node may be tagged with multiple tags, whereby if the tag bit is set in a given node, the node further includes a bitmask indicating which one or ones of the tags apply to that node. A value mask may be provided in the header indicating which of the tags (if any) have values associated therewith, whereby information representative of the value such as the value itself or a pointer thereto is stored in each node tagged with at least one tag having an associated value. Partial enumeration of tagged nodes may be provided by storing a count of the number of tagged words under a node, wherein if a trie has multiple tags, each tag may be selectively and separately enumerated as specified in header information. Partial enumeration may be combined with global enumeration of each word, with multiple tags, and/or with tags that have associated values.

Claims

1. A computer-readable medium having stored thereon a data structure, comprising:

a plurality of nodes;

a tag information field having information therein indicative of how the data structure is to be interpreted with respect to node tagging, including whether the nodes may or may not each include a tag mask field;

when the tag information field indicates that the nodes may each include a tag mask field, each node having a flag with a value that indicates whether that node has a tag mask field, at least one node of the plurality of nodes having the tag mask field and at least one other node not having the tag mask field; and

when the tag information field is interpreted to determine that the nodes may each have a tag mask field, the flag in each node is interpreted to determine whether that node has a tag mask field, and for each node having a tag mask field, data in the tag mask field is interpreted to determine whether to place the node into at least one subset of nodes of the plurality of nodes.

2. The computer-readable medium having stored thereon the data structure of claim 1, wherein the flag is a single bit.

3. The computer-readable medium having stored thereon the data structure of claim 1, wherein the tag information field is in a header of the data structure, the tag information field in the header applying to the plurality of nodes.

4. The computer-readable medium having stored thereon the data structure of claim 1, wherein at least some of the nodes represent a letter of a word.

5. The computer-readable medium having stored thereon the data structure of claim 1, wherein if the tag information field indicates that the nodes may have only one tag associated therewith, the value of the flag in each node indicates whether the node is tagged.

6. The computer-readable medium having stored thereon the data structure of claim 1, further comprising a tag value field indicative of whether at least one of the tags has a value associated therewith.

7. The computer-readable medium having stored thereon the data structure of claim 6, wherein the tag value field is in a header of the data structure, the tag value field in the header applying to the plurality of nodes.

8. The computer-readable medium having stored thereon the data structure of claim 6, further comprising a value size field representative of the size of the value for each tag having a value associated therewith.

9. The computer-readable medium having stored thereon the data structure of claim 6, wherein when the tag information field indicates that the nodes may each include a tag mask field, and the tag value field indicates that at least one tag has a value associated therewith, the data structure further comprises information indicative of which of the tags in the tag mask field have a value associated therewith.

10. The computer-readable medium having stored thereon the data structure of claim 9, further comprising a value size field representative of the size of the value for each tag having a value associated therewith.

11. The computer-readable medium having stored thereon the data structure of claim 9, wherein the information indicative of which of the tags have a value associated therewith is in a tag value mask in a header of the data structure, the tag value mask in the header applying to the plurality of nodes.

12. The computer-readable medium having stored thereon the data structure of claim 6, wherein if the tag value field indicates that at least one of the tags has a value associated therewith, for each node having at least one tag that has a value associated therewith, the node including information representative of the value for each tag having a value associated therewith.

13. The computer-readable medium having stored thereon the data structure of claim 1, wherein the nodes are globally enumerated.

14. The computer-readable medium having stored thereon the data structure of claim 1, further comprising a partial enumeration field indicative of whether tagged nodes are enumerated in the data structure.

15. The computer-readable medium having stored thereon the data structure of claim 14, wherein the tag information field indicates that the nodes may have only one tag associated therewith, and the partial enumeration field indicates that each tagged node is enumerated in the data structure.

16. The computer-readable medium having stored thereon the data structure of claim 15, wherein the nodes are globally enumerated.

17. The computer-readable medium having stored thereon the data structure of claim 14, wherein the tag information field indicates that each of the nodes may have a tag mask field, and the partial enumeration field indicates which ones of the tags correspond to a node being enumerated when a node is tagged therewith.

18. The computer-readable medium having stored thereon the data structure of claim 14, wherein at least one tagged node is partially enumerated in the data structure, and at least one node in a state above a state of the at least one tagged node has a partial enumeration count therein including a count of the tagged node.

19. The computer-readable medium having stored thereon a data structure of claim 18 wherein the at least one node in a state above a state of the at least one tagged node has a plurality of partial enumeration counts therein.

20. The computer-readable medium having stored thereon the data structure of claim 14, and further comprising a tag value field indicative of whether at least one of the tags has a value associated therewith.

21. A computer-readable medium having stored thereon a data structure, comprising:

a plurality of nodes, each node having a flag therein with a value indicative of whether that node has a tag mask field or does not, at least one node of the plurality of nodes having a tag mask field and at least one other node not having a tag mask field;

a tag information field indicative of whether each of the nodes may be tagged with at least one tag of a plurality of tags, the tags represented by values in the tag mask field; and

when the tag information field is interpreted to determine that the nodes may each be tagged with a plurality of tags, the flag in each node is interpreted to determine whether that node is tagged, and for each node that is tagged, the tag mask field is interpreted to determine with which of the plurality of tags the node is tagged.

22. The computer-readable medium having stored thereon the data structure of claim 21, wherein each tagged node is partially enumerated in the data structure.

23. The computer-readable medium having stored thereon the data structure of claim 21, further comprising a tag value field indicative of whether at least one of the tags has a value associated therewith.

24. The computer-readable medium having stored thereon the data structure of claim 23, further comprising a value size field representative of the size of the value for each tag having a value associated therewith.

25. The computer-readable medium having stored thereon the data structure of claim 24, wherein the tag information field indicates that the nodes may each be tagged with a plurality of tags, the tag value field indicates that at least one tag has a value associated therewith, and wherein the data structure further comprises information indicative of which of the tags have a value associated therewith, and a value size field representative of the size of the value for each tag having a value associated therewith.

26. The computer-readable medium having stored thereon the data structure of claim 25, wherein for each node having at least one tag that has a value associated therewith, the node includes information representative of the value for each tag having a value associated therewith.

27. The computer-readable medium having stored thereon the data structure of claim 21, wherein the nodes are globally enumerated.

28. The computer-readable medium having stored thereon the data structure of claim 21, wherein at least some of the nodes having at least one tag associated therewith are partially enumerated.

29. The computer-readable medium having stored thereon the data structure of claim 28, and further comprising a tag value field indicative of whether at least one of the tags has a value associated therewith.

30. A method of attaching information to words in a trie of nodes, comprising the steps of:

providing a tag flag with each node in the trie;

setting the tag flag on selected nodes in the trie, at least some of the nodes being non-selected nodes that do not have the tag flag set; and

for each selected node after setting the tag flag, providing a tag mask therein indicative of further information associated with data represented by the node, and for each non-selected node, not providing the tag mask, wherein at least one node in a state above one of the selected nodes has a partial enumeration count therein, the partial enumeration count including a count of the one selected node, the partial enumeration count being different from a global enumeration count of the trie.

31. The method of claim 30 wherein the tag mask includes a plurality of tags.

32. The method of claim 31 wherein at least one of the plurality of tags has a value associated therewith.

33. The method of claim 32 wherein at least one value is stored in a node having a tag mask therein.

34. The method of claim 32 wherein at least one value is stored in an encoded table.

35. A computer-readable medium having stored thereon a data structure, comprising:

a trie of nodes, each node including a tag flag;

a first set of the nodes having the tag flag set to a value indicating that each node in the first set is tagged;

a second set of the nodes having the tag flag set to a value indicating that each node in the second set is not tagged;

at least one partial enumeration count in at least one node that is based on a number of nodes thereunder that are tagged, the partial enumeration count being different from a global enumeration count of the trie of nodes; and

when the trie is interpreted, the partial enumeration count is interpreted to locate a set of nodes under a node, and the tag flag for at least one node is interpreted to determine which tagged node in the set corresponds to the partial enumeration count.

36. The computer-readable medium having stored thereon the data structure of claim 35 wherein the first set of nodes is tagged with at least one tag of a multiple tag field.

37. The computer-readable medium having stored thereon the data structure of claim 36 wherein the partial enumeration count comprises at least two values, including one value for one tag of the multiple tag field and another value for another tag of the multiple tag field.

38. The computer-readable medium having stored thereon the data structure of claim 35, further comprising, at least one global enumeration count in at least one node that is based on a number of nodes thereunder.