Method and apparatus for windowing in entropy encoding
AssigneeAT&T Intellectual Property II, L.P.
InventorsBinh Dao Vo, Kiem-Phong Vo
Life of this patent
Estimating the term…
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.
Claims15
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).
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;
- and
- wherein the method has a computation complexity O(plog p).
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;
- and
- wherein the method has a computation complexity O(plog p).
Dependencies are inferred from the claim text.