Re: How much lossless compression is possible in images?

From: Richard Tobin (richard_at_cogsci.ed.ac.uk)
Date: 12/06/04 

Date: 6 Dec 2004 21:59:06 GMT

In article <ce89r050s5p1gv3mip16fmi1hl5qvdrmfv@4ax.com>,
Mxsmanic <mxsmanic@hotmail.com> wrote:

>Actually, the chance that a random image will become smaller after
>compression with any given algorithm is always 0.5.

Why?

Consider the algorithm that precedes all input strings with a 1-bit.
It makes all strings longer.

Perhaps you don't consider that a compression algorithm. So now
consider the algorithm that replaces all strings starting with a
sequence of ten or more zeros with a byte count of the zeros (up to
255) followed by the rest of the string, and the other strings with a
0 byte followed by the original string. That only make 1 in 1024
strings smaller.

So maybe you mean an algorithm that, on average, doesn't change the
length (which is the "best" kind of algorithm). Maybe it makes one
very long string small, and lots of others just lightly bigger. This
will obviously not make 50% of images smaller.

-- Richard

Relevant Pages

  • Re: What is the state-of-the-art analysing hardware impact on achievable compression rat
    ... > about the strings for which programs exist and the strings for which it is ... You are asking about algorithmic complexity. ... There is no algorithm to compute Kfor all x in any L. ... Given that ideal compression is not ...
    (comp.compression)
  • Re: What is the state-of-the-art analysing hardware impact on achievable compression rat
    ... >> about the strings for which programs exist and the strings for which it ... >> depend on the instruction set supported by the CPU? ... compression possible: some of the content of the string to compress is ... There is no algorithm to compute Kfor all x in any L. ...
    (comp.compression)
  • Re: Best Job Skill --> .NET or Java
    ... strings, ... But the same basic brute-force algorithm was ... It compiled a histogram of trigrams, ... finds one random trigram that is unique, it expands that one, ...
    (comp.programming)
  • Re: How to efficiently determine if a string contains any one of many strings
    ... If you are looking to apply an algorithm similar to determining what is ... the algorithm that is used in most heuristic spam filters. ... kinds of classifications lend themselves to searches for string literals: ... Of course, assuming more input strings to match, you'd have a lot more ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Data mining algorithm
    ... the "best" descriptive strings for data. ... That sounds like the first step of a compression algorithm. ... In a similar data set this column will show similar repetativeness at ...
    (comp.programming)