METHOD AND APPARATUS FOR WINDOWING IN ENTROPY ENCODING

• US 20080040375A1
• Filed: 10/12/2007
• Published: 02/14/2008
• Est. Priority Date: 07/17/2003
• Status: Active Grant

• Current Assignee: Binh Vo, Kiem-Phong Vo
• Original Assignee: Binh Vo, Kiem-Phong Vo
• Inventors: Vo, Binh, Vo, Kiem-Phong
• Granted Patent: US 7,925,639 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• 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 length p into smaller segments, P_i, that can be compressed separately, said method comprising:

storing said data segment, P in a computer readable medium;

dividing said data segment, P into a plurality of 2-partition pairs π

where both partitions within each pair having a predefined length of at least μ

(P);

estimating a compressed length of each partition within each pair; and

selecting one of said 2-partition pairs π

for partitioning said data segment, P, such that Γ

(π

)<

Γ

(P), where Γ

(π

) represents a compressed length of said partition and Γ

(P) represents a compressed length of said data segment, P.

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

${\mathrm{\Gamma <br><br>}}_e<br><br>\left(P\right)=\mathrm{\tau <br><br>}+\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(\frac{p}{F_p<br><br>\left[i\right]}\right)=\mathrm{\tau <br><br>}+p<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>p-\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(F_p<br><br>\left[i\right]\right)$

where F_P[i] is a corresponding array of frequencies for a byte i and τ

is an estimate for the length of a table of codes or frequencies that a static Huffman or arithmetic compressor needs to decode data.

3. The method of claim 1, wherein said method has a computation complexity O(plog p).

4. The method of claim 1, where

$\Gamma$

⁡

( π

) = ∑

i = 1 k ⁢

Γ

⁡

( P i )

and μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter.

5. The method of claim 1, further comprising:

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

(P), where μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

finding the first π

_i such that Γ

(π

_i)<

Γ

(P) and Γ

(π

_i+1)>

Γ

(π

_i).

6. The method of claim 5, wherein said finding step comprises:

when said π

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

_i.

7. A computer-readable 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 the steps of a method for partitioning a data segment, P, with length p into smaller segments, P_i, that can be compressed separately, comprising of:

storing said data segment, P in a computer readable medium;

dividing said data segment, P into a plurality of 2-partition pairs x where both partitions within each pair having a predefined length of at least μ

(P);

estimating a compressed length of each partition within each pair; and

selecting one of said 2-partition pairs Ti for partitioning said data segment, P, such that Γ

(π

)<

Γ

(P), where Γ

(π

) represents a compressed length of said partition and Γ

(P) represents a compressed length of said data segment, P.

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

${\mathrm{\Gamma <br><br>}}_e<br><br>\left(P\right)=\mathrm{\tau <br><br>}+\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(\frac{p}{F_p<br><br>\left[i\right]}\right)=\mathrm{\tau <br><br>}+p<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>p-\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(F_p<br><br>\left[i\right]\right)$

where F_P[i] is a corresponding array of frequencies for a byte i and τ

is an estimate for the length of a table of codes or frequencies that a static Huffman or arithmetic compressor needs to decode data.

9. The computer-readable medium of claim 7, wherein said method has a computation complexity O(plog p).

10. The computer-readable medium of claim 7, where

$\Gamma$

⁡

( π

) = ∑

i = 1 k ⁢

Γ

⁡

( P i )

and μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter.

11. The computer-readable medium of claim 7, further comprising:

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

(P), where μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

finding the first π

_i such that Γ

(π

_i)<

Γ

(π

_i+1) and Γ

(π

_i+1)>

Γ

(π

_i).

12. The computer-readable medium of claim 11, wherein said finding step comprises:

when said π

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

_i.

13. An apparatus for partitioning a data segment, P, with length p into smaller segments, P_i, that can be compressed separately, comprising:

means for storing said data segment, P in a computer readable medium;

means for dividing said data segment, P into a plurality of 2-partition pairs π

where both partitions within each pair having a predefined length of at least μ

(P);

means for estimating a compressed length of each partition within each pair; and

means for selecting one of said 2-partition pairs c for partitioning said data segment, P, such that Γ

(π

)<

Γ

(P), where Γ

(π

) represents a compressed length of said partition and F(P) represents a compressed length of said data segment, P.

14. The apparatus of claim 13, wherein said the compressed length of said data segment is estimated using the function of:

${\mathrm{\Gamma <br><br>}}_e<br><br>\left(P\right)=\mathrm{\tau <br><br>}+\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(\frac{p}{F_p<br><br>\left[i\right]}\right)=\mathrm{\tau <br><br>}+p<br><br>\text{\hspace{1em}<br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>p-\underset{i=0}{\overset{255}{\sum <br><br>}}<br><br>F_p<br><br>\left[i\right]<br><br>\log <br><br>\left(F_p<br><br>\left[i\right]\right)$

where F_P[i] is a corresponding array of frequencies for a byte i and τ

is an estimate for the length of a table of codes or frequencies that a static Huffman or arithmetic compressor needs to decode data.

15. The apparatus of claim 13, wherein said method has a computation complexity O(plog p).

16. The apparatus of claim 13, where

$\Gamma$

⁡

( π

) = ∑

i = 1 k ⁢

Γ

⁡

( P i )

and μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter.

17. The apparatus of claim 13, further comprising:

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

(P), where μ

(P)=max(p/5, ε

) and ε

is an arbitrary parameter; and

means for finding the first π

_i such that Γ

(π

_i)<

Γ

(P) and Γ

(π

_i+1)>

Γ

(π

_i).

18. The apparatus of claim 17, wherein said finding means when said π

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

_i.