Prefix compression for keyed values
Systems and techniques are described for compressing strings by using a tree data structure. Specifically, for each string in a sequence of strings, the embodiments can traverse the tree data structure by matching characters of the string with characters associated with nodes of the tree data structure until either (1) all characters in the string have been processed, or (2) a current character in the string does not match a corresponding character in a current node of the tree data structure. Next, a first node identifier associated with the current node can be returned if all characters have been processed. Otherwise, a new node can be created in the tree data structure to store the remaining characters in the string, and a second node identifier associated with the new node in the tree data structure can be returned.
1. A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method, the method comprising:
initializing a tree data structure; and
for each string in a sequence of strings, performing a set of operations comprising:
traversing the tree data structure by matching characters of the string with characters associated with nodes of the tree data structure until either (1) all characters in the string have been processed, or (2) a current character in the string does not match a corresponding character in a current node of the tree data structure,
in response to determining that all characters in the string have been processed, returning a first node identifier associated with the current node, and
in response to determining that the current character in the string does not match the corresponding character in the current node of the tree data structure,
creating a new node in the tree data structure to store characters starting from the current character in the string to an end of the string, and
returning a second node identifier associated with the new node in the tree data structure.
2. The non-transitory computer-readable storage medium of claim 1 , wherein the tree data structure includes a root node upon said initializing the tree data structure, wherein the root nodes is not associated with any characters.
3. The non-transitory computer-readable storage medium of claim 2 , wherein the tree data structure comprises a set of nodes other than the root node, each node in the set of nodes is associated with a sequence of one or more characters.
4. The non-transitory computer-readable storage medium of claim 3 , wherein each node in the set of nodes is associated with a unique node identifier.
5. The non-transitory computer-readable storage medium of claim 3 , wherein the sequence of one or more characters is stored either in an internal buffer or in an external buffer, and wherein the node includes a flag indicating where the sequence of one or more characters is stored.
6. The non-transitory computer-readable storage medium of claim 5 , wherein multiple nodes in the tree data structure share the external buffer.
7. The non-transitory computer-readable storage medium of claim 3 , wherein each node in the set of nodes is either a leaf node or includes a reference to at least one additional node.
8. The non-transitory computer-readable storage medium of claim 7 , wherein the reference is a memory pointer that points to a memory location where the at least one additional node is stored.
9. The non-transitory computer-readable storage medium of claim 7 , wherein the nodes are stored in contiguous memory blocks, and wherein the reference is a number that indicates a position in the contiguous memory blocks.
10. The non-transitory computer-readable storage medium of claim 1 , wherein the method further comprises constructing a representation of the string, the representation including either (1) the first node identifier, or (2) a third node identifier associated with a parent of the new node and characters associated with the new node.
11. The non-transitory computer-readable storage medium of claim 10 , wherein the method further comprises recreating the string from the representation of the string, said recreating comprising determining a sequence of one or more characters associated with the first node identifier or the third node identifier.
12. The non-transitory computer-readable storage medium of claim 1 , wherein the method comprises reinitializing the tree data structure once a size of the tree data structure is greater than a threshold.
13. The non-transitory computer-readable storage medium of claim 1 , wherein the tree data structure is stored as a collection of subtrees, each subtree storing a subset of nodes of tree data structure.
14. A method, comprising:
initializing a tree data structure; and
for each string in a sequence of strings, performing a set of operations comprising:
traversing the tree data structure by matching characters of the string with characters associated with nodes of the tree data structure until either (1) all characters in the string have been processed, or (2) a current character in the string does not match a corresponding character in a current node of the tree data structure,
in response to determining that all characters in the string have been processed, returning a first node identifier associated with the current node, and
in response to determining that the current character in the string does not match the corresponding character in the current node of the tree data structure,
creating a new node in the tree data structure to store characters starting from the current character in the string to an end of the string, and
returning a second node identifier associated with the new node in the tree data structure.
15. The method of claim 14 , further comprising constructing a representation of the string, the representation including either (1) the first node identifier, or (2) a third node identifier associated with a parent of the new node and characters associated with the new node.
16. The method of claim 15 , further comprising recreating the string from the representation of the string, said recreating comprising determining a sequence of one or more characters associated with the first node identifier or the third node identifier.
17. An apparatus, comprising:
a processor; and
a non-transitory computer-readable storage medium storing instructions that, when executed by the processor, cause the apparatus to perform a method, the method comprising:
initializing a tree data structure; and
for each string in a sequence of strings, performing a set of operations comprising:
traversing the tree data structure by matching characters of the string with characters associated with nodes of the tree data structure until either (1) all characters in the string have been processed, or (2) a current character in the string does not match a corresponding character in a current node of the tree data structure,
in response to determining that all characters in the string have been processed, returning a first node identifier associated with the current node, and
in response to determining that the current character in the string does not match the corresponding character in the current node of the tree data structure,
creating a new node in the tree data structure to store characters starting from the current character in the string to an end of the string, and
returning a second node identifier associated with the new node in the tree data structure.
18. The apparatus of claim 17 , wherein the method further comprises constructing a representation of the string, the representation including either (1) the first node identifier, or (2) a third node identifier associated with a parent of the new node and characters associated with the new node.
19. The apparatus of claim 18 , wherein the method further comprises recreating the string from the representation of the string, said recreating comprising determining a sequence of one or more characters associated with the first node identifier or the third node identifier.