System and method for data compaction utilizing mismatch probability estimation

Abstract

A system and method for encoding data utilizing mismatch probability estimates. A training data set can be statistically analyzed to calculate a mismatch probability estimate which is the estimated frequency at which a data packet received during system runtime is not part of (i.e., a mismatch) the training data set. A plurality of tokens may be created, based on the mismatch probability estimate, to represent potential mismatched data that may be encountered during runtime, and an entropy encoder may generate codewords for the tokens using the mismatch probability estimate. An opcode, indicating a mismatch, may be generated and appended to the generated codewords to form a mismatch codeword. During runtime when a mismatch occurs, the system can retrieve a mismatch codeword and assign it to the mismatched data, making the encoder system robust against previously unencountered data.

What is claimed is: 
     
         1 . A system for encoding data using mismatch probability estimation comprising:
 a computing device comprising a processor, a memory, and a non-volatile data storage device;   a statistical analyzer comprising a first plurality of programming instructions stored in the memory and operable on the processor, wherein the first plurality of programming instructions, when operating on the processor, causes the processor to:   receive a data set for encoding;   perform statistical analysis on the data set to calculate a mismatch probability estimate; and   forward the mismatch probability estimate to a mismatch codeword generator; and   a mismatch codeword generator comprising a second plurality of programming instructions stored in the memory and operable on the processor, wherein the second plurality of programming instructions, when operating on the processor, causes the processor to:   receive the mismatch probability estimate;   create one or more tokens based on the received mismatch probability estimate, wherein the one or more tokens represent one or more probable mismatched sourceblocks;   feed the one or more tokens into an entropy encoder to generate a codeword for each of the one or more probable mismatched sourceblocks;   append an opcode to each of the one or more generated codewords to form one or more mismatch codewords; and   store the one or more mismatch codewords in a codebook; and   an encoder comprising a third plurality of programming instructions stored in the memory and operable on the processor, wherein the third plurality of programming instructions, when operating on the processor, causes the processor to:   receive a mismatched sourceblock during runtime;   identify a mismatch codeword in the codebook using the opcode and retrieve the identified mismatch codeword;   encode the mismatched sourceblock using a mismatch codeword from the codebook and delete the opcode; and   store the received mismatched sourceblock and the encoded mismatched sourceblock as a codeword pair in the codebook.   
     
     
         2 . The system of  claim 1 , wherein the statistical analysis is performed via a modified exponentially-weighted moving average. 
     
     
         3 . The system of  claim 1 , wherein the entropy encoder is a Huffman binary tree. 
     
     
         4 . A method for encoding data using a plurality of codebooks, comprising the steps of:
 receiving a data set for encoding;   performing statistical analysis on the data set to calculate a mismatch probability estimate;   forwarding the mismatch probability estimate to a mismatch codeword generator;   receiving the mismatch probability estimate;   creating one or more tokens based on the received mismatch probability estimate, wherein the one or more tokens represent one or more probable mismatched sourceblocks;   feeding the one or more tokens into an entropy encoder to generate a codeword for each of the one or more probable mismatched sourceblocks;   appending an opcode to each of the one or more generated codewords to form one or more mismatch codewords;   storing the one or more mismatch codewords in a codebook;   receiving a mismatched sourceblock during runtime;   identifying a mismatch codeword in the codebook using the opcode and retrieve the identified mismatch codeword;   encoding the mismatched sourceblock using a mismatch codeword from the codebook and delete the opcode; and   storing the received mismatched sourceblock and the encoded mismatched sourceblock as a codeword pair in the codebook.   
     
     
         5 . The method of  claim 4 , wherein the statistical analysis is performed via a modified exponentially-weighted moving average. 
     
     
         6 . The method of  claim 4 , wherein the entropy encoder is a Huffman binary tree.