Method and apparatus for windowing in entropy encoding

• US 7,925,639 B2
• Filed: 10/12/2007
• Issued: 04/12/2011
• Est. Priority Date: 07/17/2003
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Vo, Kiem-Phong, Vo, Binh Dao
• Primary Examiner(s): Corrielus; Jean M
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US11/871,391
• Publication Number:
  US 20080040375A1
• Time in Patent Office: 1,278 Days
• Field of Search: 707/1, 707/10, 707100-102, 707/693, 707/796, 707/716, 707/700, 707/755, 707/756
• US Class Current: 707/693
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

1. A method for partitioning a data segment, P, with a length p into smaller segments, P_i, 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).

2. The method of claim 1, wherein the compressed length of the data segment is estimated using a function of:

3. The method of claim 1, where

4. The method of claim 1, further comprising:

ordering the 2-partition pairs by a length of the left parts of the 2-partition pairs, for all 2-partition pairs of P with parts having a minimum length of μ

(P), where μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

finding a π

_i such that Γ

(π

_i)<

Γ

(P) and Γ

(π

_i+1)>

Γ

(π

_i).

5. The method of claim 4, wherein the finding comprises:

when the π

_i is found, then recursively applying a right partition associated with the π

_i.

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, P_i, 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).

7. The computer-readable storage medium of claim 6, wherein the compressed length of the data segment is estimated using a function of:

8. The computer-readable storage medium of claim 6, where

9. The computer-readable storage medium of claim 6, further comprising:

ordering the 2-partition pairs by a length of the left parts of the 2-partition pairs, for all 2-partition pairs of P with parts having minimum length of μ

(P), where μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

finding a π

_i such that Γ

(π

_i)<

Γ

(P) and Γ

(π

_i+1)>

Γ

(π

_i).

10. The computer-readable storage medium of claim 9, wherein the finding comprises:

when the π

_i is found, then recursively applying a right partition associated with the π

_i.

11. An apparatus for performing a method for partitioning a data segment, P, with a length p into smaller segments, P_i, 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).

12. The apparatus of claim 11, wherein the compressed length of the data segment is estimated using a function of:

13. The apparatus of claim 11, where

14. The apparatus of claim 11, further comprising:

means for ordering the 2-partition pairs by a length of the left parts of the 2-partition pairs, for all 2-partition pairs of P with parts having a minimum length of μ

(P), where μ

P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

means for finding a π

_i such that Γ

(π

_i)<

Γ

(P) and Γ

(π

_{i +1})>

Γ

(π

_i).

15. The apparatus of claim 14, wherein the finding means, when the π

_i is found, then recursively applies a right partition associated with the π

_i.