Method and system for reducing contexts for context based compression systems

Abstract

For context based compression techniques, for example Context Based YK compression, a method and system for grouping contexts from a given context model together to create a new context model that has fewer contexts, but retains acceptable compression gains compared to the original context model. According to an exemplary embodiment of the method empirical statistics are determined for a file type of a file to be compressed; and the context model is generated by iteratively grouping contexts of an initial context model in accordance with the empirical statistics, the context model having fewer contexts than an initial context model.

What is claimed is: 
     
         1 . A method of generating a context model for context-based compression, the method comprising:
 determining empirical statistics for a file type of a file to be compressed; and   generating the context model by iteratively grouping contexts of an initial context model in accordance with the empirical statistics, the context model having fewer contexts than the initial context model.   
     
     
         2 . The method as claimed in  claim 1 , wherein the determining the empirical statistics includes determining joint, conditional, and unconditional probabilities. 
     
     
         3 . The method of  claim 1 , further comprising generating a mapping file for mapping data elements to a set of contexts of size equal to a size of the context model. 
     
     
         4 . The method of  claim 3 , wherein the determining the empirical statistics comprises:
 determining file categorization criteria for the file type;   determining the initial context model including an initial value for a current number of contexts and an initial context set based on the file categorization criteria; and   determining, for the initial context model, the empirical statistics of contexts and symbols.   
     
     
         5 . The method as claimed in  claim 4 , wherein the generating the context model by iteratively grouping contexts comprises iteratively using the empirical statistics to incrementally reduce the number of contexts until the number of contexts equals a predetermined number of contexts. 
     
     
         6 . The method as claimed in  claim 4  wherein the generating the context model by iteratively grouping contexts comprises applying a grouping function to the context set to combine the contexts into a smaller set of contexts. 
     
     
         7 . The method as claimed in  claim 4  wherein the determining the initial context model comprises determining an initial context length dependent on the file categorization criteria, and wherein the initial context set is derived based on the initial context length. 
     
     
         8 . The method as claimed in  claim 4  wherein the determining the initial context model comprises determining a size of an alphabet used in the file based on the determined file categorization criteria and then assigning an initial context length equal to a number of bits based on the number of bits needed to encode all elements of the alphabet; and wherein the initial context set is derived based on the initial context length. 
     
     
         9 . The method as claimed in  claim 6  wherein the applying a grouping function comprises:
 creating groupings of contexts from the initial context set; 
 calculating a conditional entropy for each grouping of contexts; 
 selecting a reduced number of groupings based on the calculated conditional entropy; and 
 reducing a size of the initial context set by replacing elements which comprise the selected groupings with the groupings. 
 
     
     
         10 . The method as claimed in  claim 6  wherein the applying a grouping function comprises:
 iteratively, until a size of the set of contexts equals the predetermined number of contexts, performing:
 creating groupings of contexts from the initial context set; 
 calculating a conditional entropy for each grouping of contexts; 
 selecting a grouping with a lowest conditional entropy; and 
 reducing a size of the set of contexts by replacing elements which comprise the selected grouping with the grouping. 
 
 
     
     
         11 . The method as claimed in  claim 10  wherein the selecting the grouping with the lowest conditional entropy comprises determining joint, conditional, and unconditional probabilities from a large set of data files having the same file categorization criteria as the determined file categorization. 
     
     
         12 . The method as claimed in  claim 10  wherein the selecting the grouping with the lowest conditional entropy comprises determining the nth order empirical statistics from a large set of data files having the same file categorization criteria as the determined file categorization, where n is a prescribed parameter. 
     
     
         13 . The method as claimed in  claim 10  wherein the context model is used in a context-dependent grammar based compression process for compressing a sequence by parsing the sequence, and wherein the context set is such that a next context is determined from the current context and a current parsed phrase. 
     
     
         14 . The method as claimed in  claim 10  wherein the initial context model is a state machine context model and wherein the initial context model is used in a context-based YK compression process for compressing a sequence x=x1x2 . . . xm by parsing the sequence, and wherein the context set is chosen such that a next context from the context model is determined from the current context and a current parsed phrase. 
     
     
         15 . The method as claimed in  claim 10  wherein the initial context model is a state machine context model and wherein the context model is used in a context-based YK compression process for compressing a sequence x=x1x2 . . . xm by parsing the sequence, and wherein the step of creating grouping only creates groups such that when the groups are combined, a next context from the reduced set of contexts can still be determined from the current context and a current parsed phrase. 
     
     
         16 . The method as claimed in  claim 1  wherein the file categorization criteria include at least one of content type, language, and file structure. 
     
     
         17 . A compression system, comprising:
 a processor configured for generating a context model for context-based compression by determining empirical statistics for a file type of a file to be compressed; and generating the context model by iteratively grouping contexts of an initial context model in accordance with the empirical statistics, the context model having fewer contexts than the initial context model.   
     
     
         18 . The system of  claim 17 , wherein the processor is further configured to generate a mapping file, for mapping data elements to a set of contexts of size equal to a size of the context model. 
     
     
         19 . The system of  claim 17 , wherein the processor is configured to determine the empirical statistics by:
 determining file categorization criteria for the file type;   determining the initial context model including an initial value for a current number of contexts and an initial context set based on the file categorization criteria; and   determining, for the initial context model, the empirical statistics of contexts and symbols.   
     
     
         20 . The system as claimed in  claim 17 , wherein determining the empirical statistics includes determining joint, conditional, and unconditional probabilities.