Method and apparatus for performing data compression
First Claim
1. A method for utilizing a processor to change the form of input data having symbols, comprising the steps of:
- a) providing the input data to the processor;
b) implementing a modelling method in the processor, the modelling method comprising mapping the frequencies of the symbols in at least a portion of the input data such that the sum of the frequencies of the symbols in the at least a portion of the input data, after mapping, equals a pre-set value;
c) processing the input data in the processor using a first coder comprising a shift operation instead of a divide or multiply operation to compute the symbols'"'"' probabilities and to produce compressed data;
d) applying the compressed data to a medium.
23 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus are disclosed for performing data compression on raw uncompressed data. The method develops a semi-adaptive modeler that sub-divides the length of an input data file into blocks of fixed size. The blocks are then sub-divided into sub-blocks in which the frequencies of the symbols are mapped to occupy the whole frequency space. The modeler is then used to develop a reduced complexity implementation of arithmetic coding, whereby, the time consuming divide operation used in computing the symbols'"'"' true probabilities is replaced by a simple shift operation. The reduced complexity arithmetic coder is referred to as approximate arithmetic coder. The modeler and the approximate arithmetic coder are then used in a multi-step data compression system that employs a ZL coder. The multi-step method results in high efficiency data compression systems that are ideal for real time operations and are better suited for network communications or data storage systems. The method overcomes many of the difficulties found in the prior art and generally achieves better compression ratios.
164 Citations
20 Claims
-
1. A method for utilizing a processor to change the form of input data having symbols, comprising the steps of:
-
a) providing the input data to the processor; b) implementing a modelling method in the processor, the modelling method comprising mapping the frequencies of the symbols in at least a portion of the input data such that the sum of the frequencies of the symbols in the at least a portion of the input data, after mapping, equals a pre-set value; c) processing the input data in the processor using a first coder comprising a shift operation instead of a divide or multiply operation to compute the symbols'"'"' probabilities and to produce compressed data; d) applying the compressed data to a medium. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An apparatus for utilizing a processor to change the form of input data having symbols comprising:
-
a) means for obtaining the input data at the processor; b) means at the processor for implementing a modelling method comprising means for mapping the frequencies of the symbols in at least a portion of the input data such that the sum of the frequencies of the symbols in the at least a portion of the input data, after mapping, equals a pre-set value; c) means at the processor for processing the input data using a first coder comprising a shift operation instead of a divide or multiply operation to compute the symbols'"'"' probabilities and to produce compressed data; and d) means for applying the compressed data to a medium. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification