An integer of potentially unbounded size is compression coded by first transforming the integer into a binary representation in which the length of the sequence of bits representing the integer is self-contained within the sequence itself. Each of the bits within the sequence is then coded with a binary arithmetic coder, such as the QM-Coder, which uses as a conditioning context for each bit, the bits of the sequence previously coded. In order to limit the amount of memory used to store the probability information associated with each conditioning context, memory is allocated for storing such information as that conditioning context is needed. Also, once a predetermined amount of memory has been used to store this probability information for different conditioning contexts, no further memory space is allocated for newly occurring conditioning contexts. Rather a special overflow memory space is allocated and used for all conditioning contexts not previously defined.
A system that encodes a sequence of integers using a variable-length compression technique is described. During operation, the system scans the sequence of integers and observes the sizes of the integers to determine a threshold value K from the observed sizes. For a given integer which is N bits in length, if N-K is greater than or equal to zero, the system generates a tag for the encoded integer which comprises a sequence of N-K zeros followed by a one, and generates a set of remaining bits for the encoded integer as a sequence of the N bits which make up the integer. Otherwise, if N-K is less than zero, the system generates a tag for the encoded integer as a single one, and generates a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.
