Data compression via alphabet partitioning and group partitioning

A method for compressing data, said method comprising:

• (a) grouping a plurality of integer numbers representative of the data into at least two groups;
• (b) establishing a group list containing said at least two groups;
• (c) identifying a maximum integer number (N.sub.m) within the at least two groups and entropy coding said maximum integer number (N.sub.m);
• (d) if N.sub.m >0, then for each group in the group list
• (i) divide the group into n subgroups, wherein n.gtoreq.2;
• (ii) create a binary mask of n bits, each bit said corresponding to one subgroup of said n subgroups and comprising 1 if the corresponding subgroup's maximum integer number (N.sub.ms) equals the maximum integer number (N.sub.m), otherwise the bit is 0;
• (iii) entropy coding the binary mask and entropy coding every subgroup maximum integer number (N.sub.ms) which is less than the maximum integer number (N.sub.m);
• (iv) add to the group list each subgroup with more than one integer number and a subgroup maximum integer number (N.sub.ms)>0;
• and
• (e) repeating said steps (c) & (d) for each group and subgroup in the group list until the group list is empty, thereby achieving encoding of said plurality of integer numbers and compressing of said data.

An encoder for encoding a plurality of integer numbers comprising:

• (a) means for renumbering the plurality of integer numbers so that smaller numbers correspond to more probable integer numbers, and for outputting a stream of numbers based thereon;
• (b) means for grouping the stream of numbers into at least two groups;
• (c) means for finding a maximum number N.sub.m in a group from the at least two groups;
• (d) means for entropy-coding the maximum number N.sub.m ;
• (e) means for recursively encoding the group of numbers using the maximum number N.sub.m ;
• and
• (f) means for repeating, for each group of the at least two groups, said means for finding (c), said means for entropy-coding (d) and said means for recursively encoding (e), thereby producing codewords comprising said encoded plurality of integer numbers.

A computer system for processing source integer numbers comprising:

• an encoder for encoding said source integer numbers to produce codewords;
• a transmission/storage subsystem for accommodating said codewords;
• a decoder for receiving said codewords from said transmission/storage subsystem and for decoding said codewords to reobtain said source integer numbers;
• and
• wherein said encoder comprises:
• (i) means for renumbering the source numbers so that smaller numbers correspond to more probable source numbers and for outputting a stream of numbers based thereon;
• (ii) partition means for grouping said stream of numbers into at least two groups;
• (iii) means for finding a maximum number (N.sub.m) in a group of numbers from the at least two groups;
• (iv) means for entropy-coding the maximum number N.sub.m ;
• (v) means for recursively encoding the group of numbers using the maximum number N.sub.m ;
• and
• (vi) means for repeating said means (iii)-(v).

A computer program product comprising a computer usable medium having computer readable program code means therein for use in compressing data in a computer system, said computer readable program code means in said computer program product comprising:

• (i) computer readable program code means for renumbering a plurality of integer numbers representative of the data employing associated probabilities so that smaller numbers correspond to more probable integer numbers of said plurality of integer numbers and for outputting a stream of numbers based upon said renumbering;
• (ii) computer readable code means for grouping said stream of numbers into at least two groups;
• (iii) computer readable code means for finding a maximum number (N.sub.m) in a group from the at least two groups;
• (iv) computer readable code means for entropy-coding the maximum number N.sub.m ;
• (v) computer readable program code means for recursively encoding the numbers of the group using the maximum number N.sub.m ;
• and
• (vi) computer readable program code means for repeating processings of said computer readable code means (i)-(iv) for each group of the at least two groups.