Method and system for improved enumeration of tries
US6304878A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Nov 23, 1998 |
| Grant date | Oct 16, 2001 |
| Priority date | — |
| Expiry date | Nov 23, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system for enumerating a trie of states of nodes. A node near the middle of a state of alphabetically ordered nodes is selected as a skip node and moved to the logical beginning of the state. The skip node is provided with a pointer to a jump node that is at the skip node's former position, and the node immediately to the left of the node's former position is marked as a soft terminal node. As a result of the alphabetic ordering, the segment of nodes before the jump node are alphabetically before the skip node, while the segment of nodes after the jump node are alphabetically after the skip node. The segments of the state may be recursively split into further segments via further skip nodes, jump nodes and soft terminal nodes, and, once the segments are split as desired, the nodes within the segment may be sorted. When searching the state, if a skip node is reached that does not equal the search character, the search moves to the jump node if the search character is greater than the skip node, or to the next node if the search character is less than the skip node. The search of the nodes continues, essentially as a binary search when skip nodes are encountered, and a l…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.