Apparatus, system, and method of data compression
First Claim
Patent Images
1. A method comprising:
- storing in a compression array a first possible representation of an input data item;
comparing a first value of a compression efficiency parameter relating to one or more subsequences of said first representation, with a second value of said compression efficiency parameter relating to one or more subsequences of a second possible representation of said input data item; and
replacing in said compression with said one or more subsequences of said first possible representation with said one or more subsequences of the second possible representation if said comparison indicates that said second possible representation is more efficient for compression of said input data item;
wherein the first and second possible representations correspond to first and second partitions, respectively, of said input data item into subsequences looked up in a compression dictionary.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system of compressing an input data item such as, e.g., a cache line of machinc-executable code, by selecting a partition of the data item into subsequences that appear as words in a dictionary of a probability-based encoding scheme, such that the encoding of the subsequences produces a compressed representation of the data according to a desired efficiency parameter, e.g., minimized length. The method may implement an algorithm to identify one or more possible compressed representations of the input data item and to select a more efficient compressed representation.
14 Citations
22 Claims
-
1. A method comprising:
-
storing in a compression array a first possible representation of an input data item; comparing a first value of a compression efficiency parameter relating to one or more subsequences of said first representation, with a second value of said compression efficiency parameter relating to one or more subsequences of a second possible representation of said input data item; and replacing in said compression with said one or more subsequences of said first possible representation with said one or more subsequences of the second possible representation if said comparison indicates that said second possible representation is more efficient for compression of said input data item; wherein the first and second possible representations correspond to first and second partitions, respectively, of said input data item into subsequences looked up in a compression dictionary. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An apparatus comprising:
a compression engine to store a first possible representation of an input data item corresponding to a first partition of said input data item into one or more subsequences of said input data item, to compare a first value of a compression efficiency parameter relating to said first representation with a second value of said compression efficiency parameter relating to one or more subsequences of a second possible representation of said input data item, and to replace said one or more subsequences of said first possible representation with said one or more subsequences of the second possible representation if said comparison indicates that said second possible representation is more efficient for compression of said input data item. - View Dependent Claims (8, 9, 10, 11, 12)
-
13. A system comprising:
-
a memory having stored thereon at least a compression dictionary having entries corresponding to a plurality of subsequences of an input data item having a high recurrence probability; and a compression engine to store a first possible representation of an input data item corresponding to a first partition of said input data item into one or more subsequences of said input data item looked up in said encoding dictionary, to compare a first value of a compression efficiency parameter relating to said first representation with a second value of said compression efficiency parameter relating to one or more subsequences of a second possible representation of said input data item, and to replace said one or more subsequences of said first possible representation with said one or more subsequences of the second possible representation if said comparison indicates that said second possible representation is more efficient for compression of said input data item. - View Dependent Claims (14, 15, 16, 17, 18, 19)
-
-
20. A machine-readable medium having stored thereon data compressed by:
-
storing in a compression array a first possible compressed representation of an input data item; comparing a first value of a compression efficiency parameter relating to one or more subsequences of said first representation, with a second value of said compression efficiency parameter relating to one or more subsequences of a second possible compressed representation of said input data item; and replacing in said compression array said one or more subsequences of said first possible representation with said one or more subsequences of the second possible representation if said comparison indicates that said second possible representation is more efficient for compression of said input data item, wherein the first and second possible compressed representations correspond to first and second partitions, respectively, of said input data item into subsequences looked up in a compression dictionary. - View Dependent Claims (21, 22)
-
Specification