Method and system for improved enumeration of tries

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 linear search otherwise, until a node is found that matches the search character or a soft or regular terminal node is reached.