Symbol compression using conditional entropy estimation

1. A method for symbol compression using conditional entropy estimation, comprising:

approximating a plurality of symbol encoding bits for a number of symbols using a conditional entropy estimation;

generating dictionary entries from the number of symbols so as to minimize a total bit-stream, the total bit-stream including at least the approximated plurality of symbol encoding bits and a plurality of dictionary entries encoding bits; and

encoding the number of symbols using the dictionary entries as a reference.

2. The method according to claim 1 , further comprising:

segmenting a text region from an image of digital content; and

extracting from the text region connected components as symbols.

3. The method according to claim 1 , wherein approximating the plurality of symbol encoding bits for the number of symbols includes estimating for each symbol the conditional probability of a pixel in the symbol conditioned on a context of the pixel in the symbol.

4. The method according to claim 3 , wherein the context of the pixel includes pixels the symbol neighborhood and pixels in the dictionary entry neighborhood for a dictionary entry used as a reference for the pixel in the symbol.

5. The method according to claim 3 , wherein the context of the pixel includes 4 pixels of the symbol neighborhood that are located:

diagonally above and to the left of the pixel in the symbol;

above the pixel in the symbol;

diagonally above and to the right of the pixel in the symbol; and

to the left of the pixel in the symbol.

6. The method according to claim 3 , wherein the context of the pixel includes 6 pixels of the dictionary entry neighborhood for the dictionary entry used as the reference for the pixel in the symbol that are located:

as the center pixel of the dictionary entry;

above the center pixel of the dictionary entry;

to the left of the center pixel of the dictionary entry;

to the right of the center pixel of the dictionary entry;

diagonally below and to the left of the center pixel of the dictionary entry; and

below the center pixel of the dictionary entry.

7. The method according to claim 3 , wherein estimating for each symbol the conditional probability includes correlating the context of the pixel to a lookup table of indexed probability values via a hash function, wherein the lookup table includes 1024 elements.

8. The method according to claim 1 , wherein generating dictionary entries from the quantity of symbols so as to minimize a total bit-stream includes clustering the symbols into subgroups by a prescreening or multistage clustering process, with a last stage of clustering being based on conditional entropy estimation, the dictionary entries corresponding to subgroups.

9. The method according to claim 8 , wherein clustering the symbols into subgroups by a multistage clustering process includes:

clustering symbols in a first stage into size subgroups based on symbol size;

clustering symbols of each size subgroup based on Hamming distance; and

clustering symbols of each Hamming distance subgroup into entropy subgroups based on conditional entropy estimation.

10. The method according to claim 9 , further comprising selecting a representative character from each of the entropy subgroups as a dictionary entry.

11. The method according to claim 10 , further comprising iteratively merging entropy subgroups selected to minimize intra-distortion increased by entropy-cluster merging.

12. A non-transitory machine-readable medium having machine-readable instructions stored thereon that, if executed by a processing resource, cause the processing resource to:

estimate a conditional probability of a pixel of a symbol to be encoded conditioned on its context pixels;

approximate a plurality of symbol encoding bits for a number of symbols using the estimated conditional probability;

generate dictionary entries from the plurality of symbols in a manner that minimizes a total bit-stream that includes the approximated plurality of symbol encoding bits and a plurality of dictionary entries encoding bits; and

encode the symbols using the dictionary entries as a reference.

13. The non-transitory computer-readable medium of claim 12 , further comprising machine-readable instructions stored thereon that, if executed by the processing resource, cause the processing resource to:

select dictionary entries from entropy clusters determined by a multistage clustering process based on symbol size, XOR, and conditional entropy estimation clustering stages.

14. An encoder, comprising:

a computing system having a processing resource; and

a non-transitory machine-readable medium having machine-readable instructions stored thereon that, if executed by the processing resource, cause the processing resource to:

approximate a plurality of symbol encoding bits for a number of symbols using a conditional entropy estimation;

generate dictionary entries from the plurality of symbols so as to minimize a total bit-stream, the total bit-stream including at least the approximated plurality of symbol encoding bits and a quantity of dictionary entries encoding bits; and

encode the symbols using the dictionary entries as a reference.

15. The encoder of claim 14 , wherein machine-readable instructions to approximate a quantity of symbol encoding include machine-readable instructions to:

estimate a conditional probability of a pixel of a symbol to be encoded conditioned on its context pixels;

calculate information contained in the pixel of the symbol; and

approximate the plurality of symbol encoding bits to encode the symbol using its associated dictionary entry.