Method and apparatus for windowing in entropy encoding
First Claim
Patent Images
1. A method for partitioning a data segment, P, with a length p into smaller segments, Pi, wherein each of the smaller segments is compressed separately, the method comprising:
- storing the data segment, P in a computer readable storage medium;
dividing the data segment, P into a plurality of 2-partition pairs π
where both partitions within each pair have a predefined length of at least μ
(P);
estimating a compressed length of each partition within each pair; and
selecting one of the 2-partition pairs it for partitioning the data segment, P, such that Γ
(π
)<
Γ
(P), where Γ
(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P, wherein at least one of;
the storing, the dividing, the estimating or the selecting is performed via a processor.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention provides efficient window partitioning algorithms for entropy-encoding. The present invention enhances compression performance of entropy encoding based on the approach of modeling a dataset with the frequencies of its n-grams. The present invention may then employ approximation algorithms to compute good partitions in time O(s*log s) and O(s) respectively, for any data segment S with length s.
-
Citations
15 Claims
-
1. A method for partitioning a data segment, P, with a length p into smaller segments, Pi, wherein each of the smaller segments is compressed separately, the method comprising:
-
storing the data segment, P in a computer readable storage medium; dividing the data segment, P into a plurality of 2-partition pairs π
where both partitions within each pair have a predefined length of at least μ
(P);estimating a compressed length of each partition within each pair; and selecting one of the 2-partition pairs it for partitioning the data segment, P, such that Γ
(π
)<
Γ
(P), where Γ
(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P, wherein at least one of;
the storing, the dividing, the estimating or the selecting is performed via a processor. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform a method for partitioning a data segment, P, with a length p into smaller segments, Pi, wherein each of the smaller segments is compressed separately, comprising:
-
storing the data segment, P in a computer readable storage medium; dividing the data segment, P into a plurality of 2-partition pairs π
where both partitions within each pair have a predefined length of at least μ
(P);estimating a compressed length of each partition within each pair; and selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that Γ
(π
)<
Γ
(P), where Γ
(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P. - View Dependent Claims (7, 8, 9, 10)
-
-
11. An apparatus for performing a method for partitioning a data segment, P, with a length p into smaller segments, Pi, wherein each of the smaller segments is compressed separately, comprising:
-
a processor; and a computer-readable medium in communication with the processor, wherein the computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by the processor, cause the processor to perform a method, comprising; storing the data segment, P in a computer readable storage medium; dividing the data segment, P into a plurality of 2-partition pairs π
where both partitions within each pair have a predefined length of at least μ
(P);estimating a compressed length of each partition within each pair; and selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that Γ
(π
)<
Γ
(P), where Γ
(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P. - View Dependent Claims (12, 13, 14, 15)
-
Specification