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, 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;
selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that r(π
)<
r(P), where r(π
) 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; and
wherein the method has a computation complexity O(plog p).
0 Assignments
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, 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; selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that r(π
)<
r(P), where r(π
) 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; andwherein the method has a computation complexity O(plog p). - 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, 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; selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that r(π
)<
r(P), where r(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P; andwherein the method has a computation complexity O(plog 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, is compressed separately, comprising:
-
means for storing the data segment, P in a computer readable storage medium; means for 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);means for estimating a compressed length of each partition within each pair; means for selecting one of the 2-partition pairs π
for partitioning the data segment, P, such that r(π
)<
r(P), where r(π
) represents a compressed length of the one of the 2-partition pairs and Γ
(P) represents a compressed length of the data segment, P; andwherein the method has a computation complexity O(plog p). - View Dependent Claims (12, 13, 14, 15)
-
Specification