Patent Publication Number: US-8537038-B1

Title: Efficient compression method for sorted data representations

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
     The present application claims the benefit of U.S. Provisional Patent Application Ser. No. 61/406,088, filed Oct. 22, 2010. 
    
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     Not applicable. 
     THE NAMES OR PARTIES TO A JOINT RESEARCH AGREEMENT 
     Not applicable. 
     INCORPORATION-BY-REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC 
     Not applicable. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to the field of general purpose lossless data compression based on block sorting. More specifically, the present invention relates to compression of sorted data representations obtained as a result of the Burrows-Wheeler Transform (BWT) [as described in M. Burrows, D. J. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm”, Res. rept. 124, DIGITAL Systems Research Center, 1994], or the Sort Transform (ST) [described in M. Schindler, “A Fast Block-sorting Algorithm for Lossless Data Compression”, Proc. IEEE Data Compression Conference (DCC &#39;97), pp. 469, 1997]. 
     2. Background Discussion 
     Lossless compression is a process of obtaining economical representation of source information. Lossless compression methods are used in many areas, principally including data storage and data transmission. General-purpose lossless compression methods represent a universal approach to the problem. These methods are universal in terms of the kinds of data for which they are designed. 
     There are several approaches to the general-purpose lossless compression problem. One of the most efficient is block sorting compression first introduced by M. Burrows and D. J. Wheeler. The Burrows-Wheeler (BW) compression process consists of two stages: transform stage and encoding stage. In the first stage symbols of the original data block are permuted with the use of the Burrows-Wheeler Transform or its modification—the Sort Transform. In the both cases the symbols are put into an order determined by the lexicographic ordering of their contexts. High probability of coincidence of symbols occurring in similar contexts makes the new representation much more suitable for compression. In the second stage a dedicated lossless compression algorithm is sequentially (symbol-by-symbol) applied to the reordered (sorted) block to obtain a compressed data representation. Decompression becomes possible due to the reversibility of the transform and application of the zero-loss second stage compression algorithm. 
     Since the actual compression is performed in the second stage, one of the most important problems is finding an efficient compression method for sorted representations. Although sorted representations are convenient for compression, the best results are obtained with the use of nontrivial approaches. 
     There are two main approaches to compression of sorted representations. The first approach uses dynamic symbol ranking. Symbols are dynamically ranked using an appropriate rule. Typically, most recently processed symbols are assigned lower ranks During encoding (decoding) ranks, rather than symbols, are encoded (decoded) using various probabilistic methods. Rank encoding is frequently supplemented by run-length encoding as an efficient method of processing series of repeating symbols. The use of run-length encoding significantly reduces the computational complexity of an algorithm. Known ranking methods are: (1) Move-To-Front (MTF) [see M. Burrows, D. J. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm”, Res. rept. 124, DIGITAL Systems Research Center, 1994; see also, B. Balkenhol, S. Kurtz, Y. M. Shtarkov, “Modifications of the Burrows and Wheeler Data Compression Algorithm”, Proc. IEEE Data Compression Conference (DCC &#39;99), pp. 188-197, 1999]; (2) Inversion Frequencies (IF) [Z. Arnavut, S. S. Magliveras, “Block Sorting and Compression”, Proc. IEEE Data Compression Conference (DCC &#39;97), pp. 181-190, 1997]; (3) Distance Coding (DC) [E. Binder, “Distance Coder”, comp. compression, 2000]; (4) Time Stamp (TS) [see, S. Albers, “Improved randomized on-line algorithms for the list update problem”, Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 412-419, 1995; see also, S. Albers, M. Mitzenmacher, “Average Case Analyses of List Update Algorithms, with Applications to Data Compression”, Algorithmica, vol. 21, no. 3, pp. 312-329, 1998]; (5) Weighted Frequency Count (WFC) [see, S. Deorowicz, “Improvements to Burrows-Wheeler compression algorithm”, Software—Practice and Experience, vol. 30, no. 13, pp. 1465-1483, 2000; see also, S. Deorowicz, “Second step algorithms in the Burrows-Wheeler compression algorithm”, Software-Practice and Experience, vol. 32, no. 2, pp. 99-111, 2002]; and (6) QLFC [F. Ghido, “QLFC—A Compression Algorithm Using the Burrows-Wheeler Transform”, Proc. IEEE Data Compression Conference (DCC &#39;05), pp. 459, 2005]. 
     An alternative approach implies using complicated adaptive probabilistic modeling in the symbol domain. In this technique, the probability of a symbol&#39;s appearance is estimated using the statistics of symbol appearances in already processed data. Most advanced technologies use binary context-based probabilistic models. Code is usually generated with the use of arithmetic encoding. There are many practical efforts currently being made in this direction. Although some projects are open source, no specific algorithms or unique methods have been publicly introduced (i.e., described in papers or patents). 
     Solutions of the first type use an indirect approach to information modeling in which the specifics of the original data are replaced by the rank specifics. Such an approach, although having several advantages, makes modeling less effective and results in larger encoded data sizes. 
     Although there were no efforts to properly expose the original ideas behind existing direct probabilistic methods, according to the information derived from open sources, existing algorithms that use this approach, especially those using binary oriented modeling, are impractical and unacceptable in many situations because of their extremely high computational complexity. Accordingly, it is desirable to have a new method of compressing sorted data presentations that outperforms known methods. 
     Certain portions of the detailed description set out below employ algorithms, arithmetic, or other symbolic representations of operations performed on data stored within a computing system. The terminology and nomenclature employed are common among those with skill in the art to communicate the substance of their understanding to others similarly skilled and knowledgeable. It will be understood that the operations discussed are performed on electrical and/or magnetic signals stored or capable of being stored, as bits, data, values, characters, elements, symbols, characters, terms, numbers, and the like, within the computer system processors, memory, registers, or other information storage, transmission, or display devices. The operations, actions or processes involve the transformation of physical electronic and/or magnetic quantities within such storage, transmission, or display devices. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic block diagrammatic flow chart showing the efficient method for compressing sorted data representations of the present invention; and 
         FIG. 2  is a schematic block diagrammatic flow chart showing the method steps for sequentially decompressing a compressed data representation achieved using the compression method illustrated in  FIG. 1 . 
     
    
    
     DESCRIPTION OF THE INVENTION 
     The present invention is a lossless compression method designed mainly for compressing sorted data representations in the second stage of a Burrows-Wheeler compression process. The inventive method provides a good trade-off between efficiency and speed. The efficiency of the algorithms that implement this method is comparable to the efficiency of the best-known probabilistic compression algorithms while their computational complexity is significantly lower. Although implementations of the method are usually slower than simpler ranking-based algorithms on redundant data, these implementations outperform ranking-based algorithms on information with low redundancy. 
     The sorted representation is processed (encoded or decoded) sequentially, symbol-by-symbol. A two-state (binary) event—whether the current symbol is identical to the previous symbol or different from it—is processed first. If the current symbol is the same as the previous symbol, the processing of the symbol is finished. If not, a delta processing possibility check is performed. If there is a constant difference between several previous pairs of symbols, the following binary event is processed: whether the difference between the current symbol and the previous symbol is the same as the difference between the previous symbol and the symbol preceding it. If delta processing is applied and differences are identical, the processing of the symbol is finished. Otherwise, the symbol is processed using a bitwise procedure: the bits of the symbol&#39;s binary representation are processed sequentially from the most significant bit to the least significant bit. 
     The proposed method can be better understood if described using algorithmic notation: 
     1. i :=0; 
     2. i :=i+1; 
     3. ENCODE/DECODE (S[i]=S[i−1]); 
     4. if S[i]=S[i−1] go to 2; 
     5. if S[i−1]−S[i−2]=S[i−2]−S[i−3]=S[i−3]−S[i−4] . . . ;
         a. ENCODE/DECODE (S[i]−S[i−1]=S[i−1]−S[i−2]);   b. if S[i]−S[i−1]=S[i−1]−S[i−2] go to 2;       

     6. b=MSB, . . . , LSB: ENCODE/DECODE ((S[i][b]); 
     7. go to 2. 
     Wherein, 
     S[i]—i-th symbol in data representation, 
     S[i][b]—b-th bit of i-th symbol in data representation, 
     MSB/LSB—most significant bit/least significant bit. 
     A complicated context-based mixed statistical binary modeling can be used during processing of binary events and symbol representation bits. Most resent binary events, already processed bits of the current symbol&#39;s binary representation, previous symbols, and/or particular bits of their binary representation can be taken into account during the estimation of the probability of a binary event or a bit appearance. Arithmetic coding can be applied for code generation. 
     As a further improvement, parts of the sorted representation can be analyzed in order to detect invariable bits of a symbol&#39;s binary representation. Invariable bits are skipped during processing. 
     Variation of the method is proposed to improve the speed. Run-length encoding can be used instead of the binary event processing. Simpler alphabet-based encoding methods can replace bitwise encoding of symbol&#39;s binary representation. 
     From the foregoing, and by way of reference first to  FIG. 1 , it will be appreciated that the method  100  is a method of sequentially compressing data on a symbol-by-symbol basis, and the method includes the following steps: (a) determining whether a symbol currently being encoded is identical to an immediately preceding symbol  106 ; (b) encoding the result of step (a) as a binary event (c) if the result in step (a) is positive, ending the encoding of the symbol  108 ; (d) if the result in step (a) is negative, proceeding to step (d); (d) determining, whether there is a constant difference between several previous pairs of symbols  110 ; (e) if the result in step (d) is positive: (i) determining, whether the difference between the current symbol a and the symbol immediately preceding it b is the same as the difference between the symbol b and the symbol immediately preceding it c  112 ; (ii) encoding the result of step (i) as a binary event; (1) if the result in substep (i) is positive, ending the encoding of the symbol  108 ; (2) if the result in substep (i) is negative, proceeding to step (g); (f) if the result in step (d) is negative, proceeding to step (f); (g) encoding the symbol using a bitwise operation in which bits of the symbol&#39;s binary representation are processed sequentially from the most significant bit to the least significant bit  114 . In some applications, steps (e), (f), and (g) can be omitted. 
     Next, and now with reference to  FIG. 2 , it will be appreciated that the inventive compression method includes and calls for a complementary method  120  of sequentially decompressing a compressed data achieved using the compression method set out in the immediately preceding paragraph, also on a symbol-by-symbol basis, the decompression method including the steps of: (a) decoding a binary event  121  determining whether a symbol currently being decoded is identical to an immediately preceding symbol by decoding a binary event  122  encoded in step (a) of the inventive compression method set out in the immediately preceding paragraph; (b) if the result in step (a) is positive, ending the decoding  124  of the symbol; (c) if the result in step (a) is negative, proceeding to step (d); (d) determining  126  whether there is a constant difference between several previous pairs of symbols; (e) if the result in step (d) is positive: (i) encoding a binary event  127  determining whether the difference between the current symbol a and the symbol immediately preceding it b is the same as the difference between the symbol b and the symbol immediately preceding it c  128  by decoding a binary event encoded in step (ii) of claim  1 ; (ii) if the result in step (i) is positive, ending the decoding  124  of the symbol; (iii) if the result in step (i) is negative, proceeding to step (g); (f) if the result in step (d) is negative, proceeding to step (g); (g) decoding the symbol  130  using a bitwise operation in which bits of the symbol&#39;s binary representation are processed sequentially from the most significant bit to the least significant bit. In some applications, steps (d), (e), and (f) can be omitted.