Computer implemented compact 0-complete tree dynamic storage structure and method of processing stored data

A computer implemented C0-trie search process, comprising:

• for each subtrie in a next level beneath a top search level, searching depths of the top-1 search level subtries;
• examining depth values selected by the top-1 search level selector vector;
• if the value is not identified as being part of the current top-1 search level subtrie, determining if here are any remaining top-1 level subtries to search;
• if there are not any remaining top-1 level subtries to search, terminating the process and if there are more top-1 level subtries to search, continuing searching the remaining top-1 level subtries;
• when a top-1 search level subtrie including the searched for value is identified, descending the process one level by making the current top-1 search level th top search level and the identified top-1 search level subtrie an identified top search level subtrie;
• and
• determining if a new top search level is a leaf selector level and if not, continuing searching the top-1 search level subtries of the identified top search level subtrie.

A computer implemented C0-trie delete process, comprising:

• receiving a list of lexical identifiers to delete;
• if the number of lexical identifiers to be deleted exceeds a threshold value, then generating a new C0-trie using remaining lexical identifiers in the C0-trie;
• if the number of lexical identifiers to be deleted does not exceed the threshold value then performing the following:
• if there are only two levels in the C0-trie then deleting leaves including the lexical identifiers;
• if the C0-trie has more than two levels, then performing the following:
• traversing a branch of the C0-trie including a lexical identifier to be deleted;
• and
• deleting the lexical identifier from the branch of the C0-trie;
• if the remaining C0-trie has more than two levels, then examining the C0-trie and merging subtries of th C0-trie.

A computer implemented C0-trie insert process, comprising:

• receiving values to insert;
• if the C0-trie has two levels, then performing the following:
• while there are values to insert, iteratively performing the following:
• identifying a key interval in an existing leaf of the C0-trie to which a value belongs;
• and
• inserting one or more values into the identified key interval;
• splitting a subtrie of the C0-trie if the subtrie includes new values that have a depth less than or equal to the depth of the subtree;
• and
• after all values have been inserted, examining the C0-trie and splitting as needed.

A data processing system for implementing a C0-trie, comprising:

• a processor;
• and
• a memory coupled to the processor, the memory having processor executable program instructions stored therein, the program instructions including:
• providing a depth vector having encoded depth values for depths of leaves of an C0-trie, the depth vector being encoded to show whether or not the corresponding leaf is an empty leaf node and being of arbitrary length;
• providing a set of selector vectors, grouped in a compound vector, each selector vector corresponding to a level of the C0-trie, each selector vector being a vector used to select entries of the depth vector and the number of selector vectors in the set of selector vectors being arbitrary;
• and
• providing a set of counter vectors, grouped in a compound vector, each selector vector having paired therewith a corresponding counter vector, the counter vector being a vector whose length is equal to the number of 1-bits in the corresponding selector vector.

A data processing system for implementing a C0-trie search process, comprising:

• a processor;
• and
• a memory coupled to the processor, the memory having processor executable program instructions stored herein, the program instructions including:
• for each subtrie in a next level beneath a top search level, searching depths of the top-1 search level subtries;
• examining depth values selected by the top-1 search level selector vector;
• if the value is not identified as being part of the current top-1 search level subtrie, determining if there are any remaining top-1 level subtries to search;
• if there are not any remaining top-1 level subtries to search, terminating the process and if there are more top-1 level subtries to search, continuing searching the remaining top-1 level subtries;
• when a top-1 search level subtrie including the searched for value is identified, descending the process one level by making the current top-1 search level the top search level and the identified top-1 search level subtrie an identified top search level subtrie;
• and
• determining if a new top search level is a leaf selector level and if not, continuing searching the top-1 search level subtries of the identified top search level subtrie.

A data processing system for implementing a C0-trie delete process, comprising:

• a processor;
• and
• a memory coupled to the processor, the memory having processor executable program instructions stored therein, the program instructions including:
• receiving a list of lexical identifiers to delete;
• if the number of lexical identifiers to be deleted exceeds a threshold value, then generating new C0-trie using remaining lexical identifiers in the C0-trie;
• if the number of lexical identifiers to be deleted does not exceed the threshold value then performing the following:
• if there are only two levels in the C0-trie then deleting leaves including the lexical identifiers;
• if the C0-trie has more than two levels, then performing the following:
• traversing a branch of the C0-trie including a lexical identifier to be deleted;
• and
• deleting the lexical identifier from the branch of the C0-trie;
• if the remaining C0-trie has more than two levels, then examining the C0-trie and merging subtries of the C0-trie.

A data processing system for implementing a C0-trie insert process, comprising:

• a processor;
• and
• a memory coupled to the processor, the memory having processor executable program instructions stored therein, the program instructions including:
• receiving values to insert;
• if the C0-trie has two levels, then performing the following:
• while there are values to insert, iteratively performing the following:
• identifying a key interval in an existing leaf of the C0-trie to which a value belongs;
• and
• inserting one or more values into the identified key interval;
• splitting a subtrie of the C0-trie if the subtrie includes new values that have a depth less than or equal to the depth of the subtree;
• and
• after all values have been inserted, examining the C0-trie and splitting as needed.

A computer program product embodying computer program instructions for implementing a data structure for representing a C0-trie, the program instructions comprising:

• providing a depth vector having encoded depth values for depths of leaves of an C0-trie, the depth vector being encoded to show whether or not the corresponding leaf is an empty leaf node and being of arbitrary length;
• providing a set of selector vectors, grouped in a compound vector, each selector vector corresponding to a level of the C0-trie, each selector vector being a vector used to select entries of the depth vector and the number of selector vectors in the set of selector vectors being arbitrary;
• and
• providing a set of counter vectors, grouped in a compound vector, each selector vector having paired therewith a corresponding counter vector, the counter vector being a vector whose length is equal to the number of 1-bits in the corresponding selector vector.

A computer program product embodying computer program instructions for implementing a C0-trie search process, the program instructions comprising:

• for each subtrie in a next level beneath a top search level, searching depths of the top-1 search level subtries;
• examining depth values selected by the top-1 search level selector vector;
• if the value is not identified as being part of the current top-1 search level subtrie, determining if there are any remaining top-1 level subtries to search;
• if there are not any remaining top-1 level subtries to search, terminating the process and if there are more top-1 level subtries to search, continuing searching the remaining top-1 level subtries;
• when a top-1 search level subtrie including the searched for value is identified, descending the process one level by making the current top-1 search level the top search level and the identified top-1 search level subtrie an identified top search level subtrie;
• and
• determining if a new top search level is a leaf selector level and if not, continuing searching the top-1 search level subtries of the identified top search level subtrie.

A computer program product embodying computer program instructions for implementing a C0-trie delete process, the program instructions comprising:

• receiving a list of lexical identifiers to delete;
• if the number of lexical identifiers to be deleted exceeds a threshold value, then generating a new C0-trie using remaining lexical identifiers in the C0-trie;
• if the number of lexical identifiers to be deleted does not exceed the threshold value then performing the following:
• if there are only two levels in the C0-trie then deleting leaves including the lexical identifiers;
• if the C0-trie has more than two levels, then performing the following:
• traversing a branch of the C0-trie including a lexical identifier to be deleted;
• and
• deleting the lexical identifier from the branch of the C0-trie;
• if the remaining C0-trie has more than two levels, then examining the C0-trie and merging subtries of the C0-trie.

A computer program product embodying computer program instructions for implementing a C0-trie insert process, the program instructions comprising:

• receiving values to insert;
• if the C0-trie has two levels, then performing the following:
• while there are values to insert, iteratively performing the following:
• identifying a key interval in an existing leaf of the C0-trie to which a value belongs;
• and
• inserting one or more value into the identified key interval;
• splitting a subtrie of the C0-trie if the subtrie includes new values that have a depth less than or equal to the depth of the subtrie.

A data processing system for implementing a compact 0-complete binary tree, comprising:

• means for providing a depth vector having encoded depth values for depths of leaves of a 0-complete binary tree, the depth vector being encoded to show whether or not the corresponding leaf is an empty leaf node and being of arbitrary length;
• means for providing a set of selector vectors, grouped in a compound vector, each selector vector corresponding to a level of the compact 0-complete binary tree, each selector vector being a vector used to select entries of the depth vector and the number of selector vectors in the set of selector vectors being arbitrary;
• and
• means for providing a set of counter vectors, grouped in a compound vector, each selector vector having paired therewith a corresponding counter vector, the counter vector being a vector whose length is equal to the number of 1-bits in the corresponding selector vector.