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

1. A computer implemented data structure for representing a C 0 -trie, comprising:

a depth vector having encoded depth values for depths of leaves of the C 0 -trie, the depth vector being encoded to show whether or not the corresponding leaf is an empty leaf node and being of arbitrary length;

a set of selector vectors, grouped in a compound vector, each selector vector corresponding to a level of the C 0 -trie, each selector vector being a bit vector used to select entries of the depth vector and the number of selector vectors in the set of selector vectors being arbitrary; and

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.

2. The computer implemented data structure of claim 1 ,

wherein for any level 1 subtrie A of the C 0 -trie, and its level 1 predecessor B, the depths of all the level l- 1 subtries of A are greater than the depths of A and B; and

wherein values or strings in the C 0 -trie are distinguished by the shortest possible prefixes y having no empty nodes included in the leaves of the subtries.

3. The computer implemented data structure of claim 1 , wherein the C 0 -trie is a representation of a 0-complete tree.

4. The computer implemented data structure of claim 1 , wherein each encoded depth value further indicates a depth of the corresponding leaf.

5. The computer implemented data structure of claim 1 , wherein a particular selector vector associated with a particular level of the C 0 -trie identifies one or more entries in the depth vector also associated with the particular level of the C 0 -trie.

6. The computer implemented data structure of claim 1 , wherein the counter vector stores a number of non-empty leaves in a portion of the C 0 -trie designated by a corresponding selector vector.

7. A computer implemented C 0 -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.

8. A computer implemented C 0 -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 C 0 -trie using remaining lexical identifiers in the C 0 -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 C 0 -trie then deleting leaves including the lexical identifiers;

if the C 0 -trie has more than two levels, then performing the following:

traversing a branch of the C 0 -trie including a lexical identifier to be deleted; and

deleting the lexical identifier from the branch of the C 0 -trie;

if the remaining C 0 -trie has more than two levels, then examining the C 0 -trie and merging subtries of th C 0 -trie.

9. A computer implemented C 0 -trie insert process, comprising:

receiving values to insert;

if the C 0 -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 C 0 -trie to which a value belongs; and

inserting one or more values into the identified key interval;

splitting a subtrie of the C 0 -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 C 0 -trie and splitting as needed.

10. The process of claim 9 , further comprising:

if the C 0 -trie has more than two levels, then performing the following:

while there are values to insert, iteratively performing the following:

while a selected level immediately below a current level is not a level above a leaf level, recursively determining which level immediately below the current level includes a subtrie of the C 0 -trie whose key interval includes a value and selecting the determined subtrie;

identifying a key interval in an existing leaf of the C 0 -trie to which a value belongs; and

inserting one or more value into the identified key interval;

splitting the subtrie if the subtrie includes new values that have a depth less than or equal to the depth of the subtree; and

after all values are inserted examining the C 0 -trie and splitting subtries as needed.

11. A data processing system for implementing a C 0 -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 C 0 -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 C 0 -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.

12. The data processing system of claim 11 ,

wherein for any level l subtrie A of the compact C 0 -trie, and its level l predecessor B, the depths of all the level l-1 subtries of A are greater than the depths of A and B; and

wherein values or strings in the compact C 0 -trie are distinguished by the shortest possible prefixes by having no empty nodes included in the leaves of the subtries.

13. A data processing system for implementing a C 0 -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.

14. A data processing system for implementing a C 0 -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 C 0 -trie using remaining lexical identifiers in the C 0 -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 C 0 -trie then deleting leaves including the lexical identifiers;

if the C 0 -trie has more than two levels, then performing the following:

traversing a branch of the C 0 -trie including a lexical identifier to be deleted; and

deleting the lexical identifier from the branch of the C 0 -trie;

if the remaining C 0 -trie has more than two levels, then examining the C 0 -trie and merging subtries of the C 0 -trie.

15. A data processing system for implementing a C 0 -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 C 0 -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 C 0 -trie to which a value belongs; and

inserting one or more values into the identified key interval;

splitting a subtrie of the C 0 -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 C 0 -trie and splitting as needed.

16. The data processing system of claim 15 , the program instructions further including:

if the C 0 -trie has more than two levels, then performing the following:

while there are values to insert, iteratively performing the following:

while a selected level immediately below a current level is not the level above a leaf level, recursively determining which subtrie immediately below the current level's subtrie includes a key interval which includes value and selecting the determined subtrie;

identifying a key interval in an existing leaf of the C 0 -trie to which a value belongs; and

inserting one or more value into the identified key interval;

splitting the subtrie if he subtrie includes new values that have a depth less than or equal to the depth of the subtree; and

after all values have bee inserted, examining the C 0 -trie and splitting subtries as needed.

17. A computer program product embodying computer program instructions for implementing a data structure for representing a C 0 -trie, the program instructions comprising:

providing a depth vector having encoded depth values for depths of leaves of an C 0 -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 C 0 -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.

18. The computer program product of claim 17 ,

wherein for any level l subtrie A of the C 0 -trie, and its level l predecessor B, the depths of all the level l-1 subtries of A are greater than the depths of A and B; and

wherein values or strings in the C 0 -trie are distinguished by the shortest possible prefixes by having no empty nodes included in the leaves of the subtries.

19. A computer program product embodying computer program instructions for implementing a C 0 -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.

20. A computer program product embodying computer program instructions for implementing a C 0 -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 C 0 -trie using remaining lexical identifiers in the C 0 -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 C 0 -trie then deleting leaves including the lexical identifiers;

if the C 0 -trie has more than two levels, then performing the following:

traversing a branch of the C 0 -trie including a lexical identifier to be deleted; and

deleting the lexical identifier from the branch of the C 0 -trie;

if the remaining C 0 -trie has more than two levels, then examining the C 0 -trie and merging subtries of the C 0 -trie.

21. A computer program product embodying computer program instructions for implementing a C 0 -trie insert process, the program instructions comprising:

receiving values to insert;

if the C 0 -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 C 0 -trie to which a value belongs; and

inserting one or more value into the identified key interval;

splitting a subtrie of the C 0 -trie if the subtrie includes new values that have a depth less than or equal to the depth of the subtrie.

22. The computer program product of claim 21 , the instructions further comprising:

if the C 0 -trie has more than two levels, then performing the following:

while there are values to insert, iteratively performing the following:

while a selected level immediately below a current level is not a level above a leaf level, recursively determining which level immediately below the current level includes a subtrie of the C 0 -trie whose key interval includes a value and selecting the determined subtrie;

identifying a key interval in an existing leaf of the C 0 -trie to which a value belongs; and

inserting one or more values into the identified key interval;

splitting the subtrie if the subtrie includes new values that have a depth less than or equal to the depth of the subtrie.

23. 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.

24. The data processing system of claim 23 ,

wherein for any level l subtrie A of the C 0 -trie, and the level l subtrie A's level l predecessor B, the depths of all the level l-1 subtries of A are greater than the depths of A and B; and

wherein values or strings in the C 0 -trie are distinguished by the shortest possible prefixes having no empty nodes included in the leaves of the subtries.