Trie compression using substates and utilizing pointers to replace or merge identical, reordered states
US6298321A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Nov 23, 1998 |
| Grant date | Oct 2, 2001 |
| Priority date | — |
| Expiry date | Nov 23, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99942
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.