Prefix compression for keyed values

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.

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.