Double-pass lempel-ziv data compression with automatic selection of static encoding trees and prefix dictionaries

Abstract

A method includes receiving an input data stream at a processor, and for each byte sequence from a plurality of byte sequences of the input data stream, a hash is generated and compared to a hash table to determine whether a match exists. If a match exists, that byte sequence is incrementally expanded to include one or more additional adjacent bytes from the input data stream, to produce multiple expanded byte sequences. Each of the expanded byte sequences is compared to the hash table to identify a maximum-length matched byte sequence from a set that includes the byte sequence and the plurality of expanded byte sequences. A representation of the maximum-length matched byte sequence is stored in the memory. If a match does not exist, a representation of that byte sequence is stored as a byte sequence literal in the memory.

1 . (canceled) 
     
     
         2 . A non-transitory, processor-readable medium storing instructions to cause a processor to:
 for each byte sequence from a plurality of byte sequences of an input data stream:
 compare a hash of that byte sequence to a hash table to determine whether a match exists, the hash table stored in a memory operably coupled to the processor; 
 in response to a match existing:
 incrementally expand that byte sequence to produce a plurality of expanded byte sequences, and 
 compare each expanded byte sequence from the plurality of expanded byte sequences to the hash table to identify a maximum-length matched byte sequence from a set of matched byte sequences that includes the byte sequence and the plurality of expanded byte sequences; and 
 
 in response to the match not existing:
 cause storage of a representation of that byte sequence as a byte sequence literal in the memory. 
 
   
     
     
         3 . The non-transitory, processor-readable medium of  claim 2 , further storing instructions to cause the processor to encode data based on a plurality of maximum-length matched byte sequences and a plurality of byte sequence literals. 
     
     
         4 . The non-transitory, processor-readable medium of  claim 2 , wherein the instructions to incrementally expand each byte sequence from the plurality of byte sequences include instructions to add, to that byte sequence, a subsequent one or more additional adjacent bytes from the input data stream. 
     
     
         5 . The non-transitory, processor-readable medium of  claim 2 , wherein a representation of the maximum-length matched byte sequence is stored as a triad that includes a representation of a length of the maximum-length matched byte sequence, an offset between the maximum-length matched byte sequence and a current byte sequence, and a number of byte literals between the maximum-length matched byte sequence and a previous match associated with the input data stream. 
     
     
         6 . The non-transitory, processor-readable medium of  claim 2 , wherein the instructions to compare the hash of each byte sequence from the plurality of byte sequences of the input data stream to the hash table to determine whether a match exists include instructions to compare the hash of each byte sequence from the plurality of byte sequences of the input data stream to the hash table in response to detecting that that hash has a length that is greater than a minimum match size. 
     
     
         7 . A system, comprising:
 a processor; and   a memory, operably coupled to the processor and storing instructions that, when executed by the processor, cause the processor to:
 generate, for each byte sequence from a plurality of byte sequences of an input data stream, a hash of that byte sequence, to define a plurality of hashes; 
 store, in the memory, an array that includes a last observed position within the input data stream of each hash from the plurality of hashes; 
 identify, based on the array, a plurality of potential matches between the plurality of byte sequences and a hash table; 
 calculate a score, from a plurality of scores, for each potential match from the plurality of potential matches; 
 select a subset of potential matches from the plurality of potential matches, based on the plurality of scores; and 
 store, in the memory, a representation of the selected subset of potential matches. 
   
     
     
         8 . The system of  claim 7 , wherein a size of the array is equal to a size of the input byte stream. 
     
     
         9 . The system of  claim 7 , wherein the memory is a first memory and the plurality of byte sequences is a first plurality of byte sequences, the first memory further storing instructions to cause the processor to store, in a second memory different from the first memory, a representation of a second plurality of byte sequences that has not been matched to the hash table. 
     
     
         10 . The system of  claim 7 , wherein the instructions to identify the plurality of potential matches between the plurality of byte sequences and the hash table based on the array include instructions to identify the plurality of potential matches between the plurality of byte sequences and the hash table at least one of:
 by performing a predefined number of searches of the array;   without reference to the input data stream; or   by iteratively incrementing at least one position from the plurality of positions.   
     
     
         11 . A non-transitory, processor-readable medium storing instructions to cause a processor to:
 compare each hash from a plurality of hashes to a hash table to identify a plurality of matched hashes associated with a first subset of byte sequences from a plurality of byte sequences, a second subset of byte sequences from the plurality of byte sequences including byte sequences that are not associated with a matched hash from the plurality of matched hashes;   select a static Huffman tree to encode the second subset of byte sequences, based on a predefined encoding strategy;   determine whether a result size associated with the selected static Huffman tree is within a predefined percentage of a number of byte sequences in the second subset of byte sequences;   when the result size is within the predefined percentage of the number of byte sequences in the second subset of byte sequences, set an encoding type to static encoding; and   when the result size is not within the predefined percentage of the number of byte sequences in the second subset of byte sequences:
 when the number of byte sequences in the second subset of byte sequences is less than a predefined first threshold value and the result size is less than the predefined first threshold value, set the encoding type to an encoding procedure that is performed based on an inverted index array and a rank table; 
 when at least one of: (1) the number of byte sequences in the second subset of byte sequences is not less than the predefined first threshold value, or (2) the result size is not less than the predefined first threshold value:
 when a custom prefix is preferable to the selected static Huffman tree, set the encoding type to custom; and 
 when the custom prefix is not preferable to the selected static Huffman tree, set the encoding type to static encoding. 
 
   
     
     
         12 . The non-transitory, processor-readable medium of  claim 11 , further storing instructions to cause the processor to encode the second subset of byte sequences using an encoder having the encoding type. 
     
     
         13 . The non-transitory, processor-readable medium of  claim 11 , further storing instructions to cause the processor to select the predefined encoding strategy based on a frequency of occurrence of each character from a plurality of characters of the second subset of byte sequences. 
     
     
         14 . The non-transitory, processor-readable medium of  claim 11 , further storing instructions to cause the processor to:
 select the predefined encoding strategy based on a frequency of occurrence of each character from a plurality of characters of the second subset of byte sequences; and   determine the frequency of occurrence of each character from a plurality of characters of the second subset of byte sequences using an unrolled loop.   
     
     
         15 . The non-transitory, processor-readable medium of  claim 11 , wherein the instructions to cause the processor to select the static Huffman tree include instructions to select the static Huffman tree using principal components analysis (PCA). 
     
     
         16 . The non-transitory, processor-readable medium of  claim 11 , wherein the predefined encoding strategy is to prioritize speed of compression. 
     
     
         17 . The non-transitory, processor-readable medium of  claim 11 , wherein the instructions to cause the processor to select the static Huffman tree include instructions to select the static Huffman tree using principal components analysis (PCA), and the predefined encoding strategy is to prioritize speed of compression. 
     
     
         18 . The non-transitory, processor-readable medium of  claim 11 , wherein the instructions to cause the processor to select the static Huffman tree include instructions to select the static Huffman tree using a cross-entropy heuristic. 
     
     
         19 . The non-transitory, processor-readable medium of  claim 11 , wherein the predefined encoding strategy is to prioritize accuracy over speed of compression. 
     
     
         20 . A method, comprising:
 identifying, via a processor, a first subset of an input data and a second subset of the input data;   selecting, via the processor, a Huffman tree from a plurality of Huffman trees, based on a predefined encoding level;   encoding the first subset of the input data using the selected Huffman tree;   generating a frequency curve for the second subset of the input data, using one of (1) a Riemann Sum or (2) a triple lookup table having a plurality of accuracies; and   encoding the second subset of the input data based on the frequency curve.