Patent Number: 6,298,321

Title: Trie compression using substates and utilizing pointers to replace or merge identical, reordered states

Abstract: An improved trie compression method that compresses by merging partially identical subtrees. States of the trie are selected, and the nodes of those states examined find nodes that are identical to one another. The most frequently occurring identical node is selected as a substate, and the states are separated into a first group of states that have the substate node therein and a second group of states that do not. The nodes in the first group of states are reordered such that the substate is at the end thereof. Then, the substate of each state is merged into a single node, replaced by a pointer from each state. Compression is performed recursively by choosing a new substate for the remaining nodes of the first group, and for subsequently separated groups, until no further identical nodes are available for merging.

Inventors: Karlov; Donald D. (Woodinville, WA), Hullender; Gregory N. (Kirkland, WA), Bennett; John R. (Redmond, WA)

Assignee: Microsoft Corporation

International Classification: H03M 7/30 (20060101); G06F 017/20 (); G06F 017/22 ()

Expiration Date: 10/02/2018