Method and apparatus for windowing in entropy encoding

• US 8,200,680 B2
• Filed: 03/22/2011
• Issued: 06/12/2012
• Est. Priority Date: 07/17/2003
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Vo, Binh Dao, Vo, Kiem-Phong
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US13/069,366
• Publication Number:
  US 20110173167A1
• Time in Patent Office: 448 Days
• Field of Search: 707/755, 707/756, 707/781
• US Class Current: 707/755
• 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, 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.

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+i)>

Γ

(π

_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, 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.

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

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

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:

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

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

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

_i.