Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Patent
1998-02-26
2000-06-13
Young, Brian
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
341106, H03M 700
Patent
active
060754702
ABSTRACT:
A block-wise adaptive statistical data compressor is disclosed that operates by replacing characters in a data block with super-character codewords comprising a variable length prefix and a fixed length index. The codewords are determined by treating a plurality of groups of characters as super-character groups and then adapting the codewords, for each data block, based upon the actual frequency of occurrence of the characters in each group. The super-character prefix value identifies the group to which a particular character belongs, and the index value identifies the individual character of the group. By grouping and indexing the characters into these super-character groups, the present invention models a particular data block using a fraction of the information generally required by a fixed statistical compressor. Also disclosed are multi-stage lossless block data compressors that include the block-wise adaptive statistical compressor and also include a clustering stage and a reordering stage. The clustering stage clusters like characters into similar locations within the data block, and the reordering stage reorders the data to generate an expected skew in the frequency distribution of characters in the data block so that the block can be more efficiently compressed by the block-wise adaptive statistical compressor.
REFERENCES:
patent: 3675211 (1972-07-01), Raviv
patent: 3675212 (1972-07-01), Raviv et al.
patent: 3694813 (1972-09-01), Loh et al.
patent: 3701108 (1972-10-01), Loh et al.
patent: 3717851 (1973-02-01), Cocke et al.
patent: 4121259 (1978-10-01), Preuss et al.
patent: 4386416 (1983-05-01), Giltner et al.
patent: 4506325 (1985-03-01), Bennett et al.
patent: 4516246 (1985-05-01), Kenemuth
patent: 4558302 (1985-12-01), Welch
patent: 4560976 (1985-12-01), Finn
patent: 4597057 (1986-06-01), Snow
patent: 4626829 (1986-12-01), Hauck
patent: 4701745 (1987-10-01), Waterworth
patent: 4706264 (1987-11-01), Cung
patent: 4862167 (1989-08-01), Copeland, III
patent: 4881075 (1989-11-01), Weng
patent: 4955066 (1990-09-01), Notenboom
patent: 4988998 (1991-01-01), O'Brien
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5049881 (1991-09-01), Gibson et al.
patent: 5051745 (1991-09-01), Katz
patent: 5109433 (1992-04-01), Notenboom
patent: 5140321 (1992-08-01), Jung
patent: 5684478 (1997-11-01), Panaoussis
patent: 5717393 (1998-02-01), Nakano et al.
patent: 5886655 (1999-03-01), Rust
"A Block-sorting Lossless Data Compression Algorithm", Burrows, M. and Wheeler, D.J., SRC Research Report of Digital Systems Research Center, dated May 10, 1994.
"Data Compression with the Burrows-Wheeler Transform", Nelson, Mark, Dr. Dobb's Journal, Sep., 1996.
MNP Update No. 8, Mar. 30, 1987.
"Block Sorting Text Compression", Fenwick, Peter, Department of Computer Science, The University of Auckland.
"Experiments with a Block Sorting Text Compression Algorithm", Fenwick, Peter, Technical Report 111, ISSN 1173-3500, Department of Computer Science, The University of Auckland, May 17, 1995.
"Improvements to the Block Sorting Text Compression Algorithm", Fenwick, Peter, Technical Report 120, ISSN 1173-3500, Department of Computer Science, The University of Auckland, Aug. 3, 1995.
"An Adaptive System For Data Compression", Faller, Newton, Proc. 7th Asilomar Conf. On Circuits, Systems & Computers (1973).
"Information Compression By Facotirising Common Strings", Mayne, A. and James, E.B.; The Computer Journal, vol. 18, No. 2 (Aug. 1973) (pp. 157-160).
"Automatic File Compression", McCarthy, J.P.; A. Gunther et al (eds.), International Computing Symposium 1973(pp. 511-516).
"Text Compression Using A 4 Bit Coding Scheme", Pike J., The Computer Journal, vol. 24, No. 4, 1981 (pp. 324-330).
"Data Compression For a Source With Markov Characteristics", Llewellyn, J.A.; The Computer Journal, vol. 30, No. 2, 1987 (pp. 149-156).
"Data Compression", Lelewer, Debra A. and Hirschberg, Daniel S.; ACM Computing Surveys, vol. 19, No. 3, Sep. 1967 (pp. 261-296).
"Fast Pattern Matching In Strings", Knuth, Donald E., Morris, Jr., James H., and Pratt, Vaughan R.; Siam J. Comput., vol. 6, No. 2, Jun. 1977 (pp. 323-350).
"Dynamic Huffman Coding", Knuth, Donald E.; Journal of Algorithms 6 (1985) (pp. 163-180).
"Is Text Compression By Prefixes and Suffixes Practical?", Fraenkel, A.S., Mor, M. and Perl, Y.; Acta Informatica 20 (1983) (pp. 371-389).
"Text Compression Using Variable- To Fixed-Length Encodings", Cooper, David and Lynch, Michael F.; Journal of The American Society For Information Science (Jan. 1982) (pp. 18-31).
"A Locally Adaptive Data Compression Scheme", Bentley, Jon Louis, Sleator, Daniel D., Tarjan, Robert E., and Wei, Victor K.; Communications of the ACM, Apr. 1986, vol/ 29, No. 4 (pp. 320-330).
Hind Hugh R.
Little Herb A.
Kost Jason L W
Meyer, Esq. Charles B.
Research In Motion Limited
Young Brian
LandOfFree
Block-wise adaptive statistical data compressor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block-wise adaptive statistical data compressor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block-wise adaptive statistical data compressor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2072131