Method and system for reducing contexts for context based...

Details Method and system for reducing contexts for context based... Method and system for reducing contexts for context based...

2008-02-29

2009-11-10

Mai, Lam T (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

C714S006130

Reexamination Certificate

active

07616132

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 context model with more contexts is provided. According to an exemplary embodiment a set of files that are correlated to the file to be compressed (hereafter called training files) are read to determine, for an initial context model, the empirical statistics of contexts and symbols. In some embodiments, this includes determining the estimated joint and conditional probabilities of the various contexts and symbols (or blocks of symbols). The initial context model is then reduced to a desired number of contexts, for example, by applying a grouping function g to the original set of contexts to obtain a new and smaller set of contexts. In some embodiments the step of applying a grouping function comprises iteratively grouping a pair of contexts together to form a grouped context, wherein each grouped context represents a local minimum based on the empirical statistics.

REFERENCES:
patent: 5045852 (1991-09-01), Mitchell et al.
patent: 5710562 (1998-01-01), Gormish et al.
patent: 5818877 (1998-10-01), Tsai et al.
patent: 5886655 (1999-03-01), Rust
patent: 6400289 (2002-06-01), Banerji
patent: 6762699 (2004-07-01), Yang
patent: 6801141 (2004-10-01), Yang et al.
patent: 2007/0120712 (2007-05-01), Cai et al.
Banerji et al., “Architecture for Efficient Implementation of the YK Lossless Data Compression Algorithm”, Proceedings of the Data Compression Conference (DCC'01), IEEE, 2001.
Bookstein et al., “An Overhead Reduction Technique For Mega-State Compression Schemes”, May 1, 1997, pp. 1-28.
Yang et al., “Efficient Universal Lossless Data Compresion Algorithms Based on a Greedy Sequential Grammar Transform—Part One: Without Context Models”, IEEE Transactions on Information Theory, vol. 46, No. 3, May 2000, pp. 755-777.
Yang et al., “Efficient Universal Lossless Data Compresion Algorithms Based on a Greedy Sequential Grammar Transform—Part Two: Without Context Models”, IEEE Transactions on Information Theory, vol. 49, No. 11, Nov. 2003, pp. 2874-2894.
Feregrino, “High Performance PPMC Compression Algorithm”, IEEE, 2003, pp. 1-8.
International Search Report for PCT Patent Application No. PCT/CA2008/000385, dated Jun. 4, 2008.

Affiliated with

Also associated with

Rating

Method and system for reducing contexts for context based... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for reducing contexts for context based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reducing contexts for context based... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4108703