Stream compression and decompression

Abstract

A method for compressing a sequence of records, each record comprising a sequence of fields, comprises steps of buffering a record in a line of a matrix, reordering the lines of the matrix according to locality sensitive hash values of the buffered records such that records with similar contents in corresponding fields are placed in proximity, and consolidating fields in columns of the matrix into a block of codes. In this, consolidating yields codes of one of a first type comprising a sequence of individual fields and a second type comprising a sequence of fields with at least one repetition. The second type of code comprises a presence field indicating repeated fields and an iteration field indicating a number of respective repetitions. Decompression of the records from the block codes compressed above is also described.

What is claimed is: 
     
         1 . An apparatus for compressing a sequence of records, each record comprising a sequence of fields, the method comprising, comprising:
 a memory;   a processor communicatively coupled to the memory for performing;
 buffering a record in a line of a matrix; 
 reordering the lines of the matrix according to locality sensitive hash values of the buffered records such that records with similar contents in corresponding fields are placed in proximity; 
 consolidating fields in columns of the matrix into a block of codes; and 
 consolidating yields codes of one of a first type comprising a sequence of individual fields and a second type comprising a sequence of fields with at least one repetition; 
 wherein the second type of code comprises a presence field indicating repeated fields and an iteration field indicating the number of respective repetitions. 
   
     
     
         2 . The apparatus according to  claim 1 , wherein a sequence of less than three repeated fields is treated as two individual fields. 
     
     
         3 . The apparatus according to  claims 1 , further comprising
 decompressing records from a block of codes, for each code that is to be extracted from the block:   determining the type of the code;   decompressing the sequence of individual fields if the code is of the first type; and   decompressing the sequence of repeated fields if the code is of the second type.   
     
     
         4 . The apparatus according to  claims 3 , further comprising a preceding determination which codes must be decompressed for obtaining a predetermined record. 
     
     
         5 . The apparatus according to  claims 4 , wherein the fields are extracted into a matrix with lines representing records, the matrix is addressable in linearized form such that each field of each record has an offset address in the linearized matrix, and determination comprises the steps of:
 determining an offset address for each field of the predetermined record;   for each code in the block:   determining a range of offset addresses the code decompresses to; and   determining that the code must be decompressed if the range comprises at least one offset address in the set.   
     
     
         6 . The apparatus according to  claims 4 , wherein the fields are extracted into a matrix with lines representing records, the matrix is addressable in linearized form such that each field of each record has an offset address in the linearized matrix, and determination comprises the steps of:
 determining an offset address for each field of the predetermined record;   linearly rescaling the determined offset addresses with a predetermined factor and setting a bit in a bitmap at the rescaled offset address to a predetermined value;   for each code in the block:   determining a range of offset addresses the code decompresses to;   linearly rescaling the range of offset addresses with the predetermined factor; and   determining that the code must be decompressed if the bitmap contains a bit with the predetermined value at a rescaled address that falls within the rescaled range of offset addresses.   
     
     
         7 . The apparatus according to  claims 4 , further comprising a preceding determination whether to decompress all codes of the block or to employ partial decompression according, wherein the determination is carried out on the basis of at least one of:
 a compression ratio indicating a quotient of a size of the block of codes by a size of the decompressed records; and   a selectivity indicating a quotient of the number of records to be decompressed by the number of records in the block.   
     
     
         8 . The apparatus according to  claims 7 , wherein determination whether to use full or partial decompression is done on the basis of a table indicating the method to use for different combinations of compression ratio and selectivity. 
     
     
         9 . The apparatus according to  claims 8 , wherein elements of the table hold an indication of an average effort for carrying out full and/or partial decompression. 
     
     
         10 . A nontransitory machine readable medium encoded with a program for compressing a sequence of records, each record comprising a sequence of fields, the program comprising instructions for:
 buffering a record in a line of a matrix;   reordering the lines of the matrix according to locality sensitive hash values of the buffered records such that records with similar contents in corresponding fields are placed in proximity;   consolidating fields in columns of the matrix into a block of codes; and   consolidating yields codes of one of a first type comprising a sequence of individual fields and a second type comprising a sequence of fields with at least one repetition;   wherein the second type of code comprises a presence field indicating repeated fields and an iteration field indicating the number of respective repetitions.   
     
     
         11 . The nontransitory machine readable medium according to  claim 10 , wherein a sequence of less than three repeated fields is treated as two individual fields.