PPM-based data compression
View Patent ↗Techniques are disclosed that reduce the computational complexity of PPM-based data compression through use of certain simplifying assumptions that permit faster search for a close-to-optimal PPM model than conventional techniques. The disclosed techniques permit the cost of the computationally-expensive model building task to be amortized over many compression/decompression cycles by maintaining a PersistentModel class, accessible to both the coder and decoder side of the system. This allows the computationally-expensive model building task to be performed only occasionally, as opposed to each time a message is coded. Furthermore, the model-building task is preferably scheduled to run at non-busy times, such that it minimizes user-perceptible service disruptions.
1. A method of compressing data comprising:
(a) providing a string to be compressed;
(b) selecting an approximately optimal PPM model for the string by:
(i) providing an objective function that measures the desirability of proposed PPM models;
(ii) starting with i=1, determining an order-i PPM model for the string;
(iii) determining an order-(i+1) PPM model for the string;
(iv) using the objective function to determine whether the order-(i+1) PPM model is more desirable than the order-i PPM model; and,
(v) if the order-(i+1) PPM model is less desirable than the order-i PPM model, selecting the order-i PPM model as the approximately optimal PPM model for the string; otherwise, increasing the value of i by one, and repeating steps (iv)-(v);
(c) using the approximately optimal PPM model to compress the string.
2. A method of compressing data, as defined in claim 1 , further comprising:
(d) providing additional strings to be compressed; and,
(e) using the approximately optimal PPM model to compress the additional strings.
3. A method of compressing data, as defined in claim 1 , further comprising:
(d) storing the selected, approximately optimal PPM model as a persistent model.
4. A method of compressing data, as defined in claim 3 , further comprising:
(e) providing additional strings to be compressed; and,
(f) using the stored persistent to compress the additional strings.
5. A method of compressing data, as defined in claim 1 , wherein:
providing an objective function that measures the desirability of proposed PPM models involves providing an objective function that considers at least two of:
(1) the entropy of proposed PPM models;
(2) the number of states of proposed PPM models; and,
(3) the compressed string length for proposed PPM models.
6. A method of compressing data, as defined in claim 1 , wherein:
providing an objective function that measures the desirability of proposed PPM models involves providing an objective function that considers at least:
(1) the entropy of proposed PPM models;
(2) the number of states of proposed PPM models; and,
(3) the compressed string length for proposed PPM models.
7. A method of compressing data, as defined in claim 1 , wherein:
determining an order-i PPM model involves performing a constrained search of prospective order-i PPM models and selecting the prospective order-i PPM model that minimizes the objective function; and,
determining an order-(i+1) PPM model involves performing a constrained search of prospective order-(i+1) PPM models and selecting the prospective order-(i+1) PPM model that minimizes the objective function.
8. A PPM-based data compression system comprising:
(a) compression means for utilizing a persistent PPM model to compress strings to produce compressed strings;
(b) decompression means for utilizing the persistent PPM model to decompress compressed strings;
(c) optimization means, invoked occasionally, for updating the persistent PPM by:
(i) utilizing a current string-to-be compressed to select an approximately optimal PPM model for the current string-to-be-compressed; and,
(ii) replacing the persistent PPM model with the selected, approximately optimal PPM model for the current string-to-be-compressed.
9. A PPM-based data compression system, as defined in claim 8 , wherein:
the optimization means is, on average, invoked less than once for every ten strings that the compression means compresses.
10. A PPM-based data compression system, as defined in claim 8 , wherein:
the optimization means is, on average, invoked less than once for every hundred strings that the compression means compresses.
11. A PPM-based data compression system, as defined in claim 8 , wherein:
the optimization means is invoked on a periodic basis.
12. A PPM-based data compression system, as defined in claim 8 , wherein:
the optimization means is selectively invoked at time(s) when its operation is not likely to create customer-perceptible disruptions in service quality.
13. A PPM-based data compression system, as defined in claim 8 , further comprising:
(d) an performance monitor adapted to track the compression ratio for strings compressed using the persistent PPM model; and,
wherein the model optimizer is invoked in respond to changes in the tracked compression ratio for strings compressed using the persistent PPM model.
14. A PPM-based data compression system, as defined in claim 8 , wherein the model optimizer includes:
a objective function computation module that evaluates the desirability of candidate PPM models by considering at least two of:
(1) the entropy of candidate PPM models;
(2) the number of states of candidate PPM models; and,
(3) the compressed string length for candidate PPM models.
15. A PPM-based data compression system, as defined in claim 8 , wherein the optimization means includes:
a objective function computation module that evaluates the desirability of candidate PPM models by considering at least:
(1) the entropy of candidate PPM models;
(2) the number of states of candidate PPM models; and,
(3) the compressed string length for candidate PPM models.
16. A PPM-based data compression system, as defined in claim 14 , wherein the optimization means further includes:
a candidate model generator module that produces approximately optimal candidate PPM models using a constrained exponential search process.
17. A PPM-based compression system, as defined in claim 16 , wherein the candidate model generator successively produces higher-order candidate PPM models.
18. An article-of-manufacture comprising a computer-readable medium, for use in connection with a computer, the computer-readable medium including software that, when executed causes the computer to:
compress strings using a persistent PPM model;
monitor compression performance of the persistent PPM model; and,
occasionally update the persistent PPM model by substituting a new, approximately optimal PPM-model computed using recently-acquired contextual information.
19. An article-of-manufacture, as defined in claim 18 , further comprising computer-executable code corresponding to FIGS. 1 - 8 .