Home > Archive > Compression > August 2005 > Re: No universal lossless compression
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: No universal lossless compression
|
|
| Hadmut Danisch 2005-07-24, 8:18 pm |
| Sportman wrote:
> Why do you need it to prove to a court?
Because the Faculty of Computer Science of the german University of
Karlsruhe denies this. In a thesis I made a statement based on the
fact that for every lossy compression scheme there is an input
where compression-decompression results in transmission errors (that's
why it is called lossy), and for every lossless compression, there is an
input where the output of compression is longer than input. Therefore,
any hidden compression algorithm can cause transmission errors.
The Faculty denied this and a professor claimed, that algorithms like
MTF and LZ are such epoch making, that they can compress just anything.
I claimed that MTF is not a compression scheme at all, because output is
always of the same length as input, for LZ well known counterexamples
exist, and simply by counting bit sequences you can easily prove that
it is impossible that an universal lossless compression exists.
However, judges are not allowed to judge in other subjects than law.
Mathematical proofs are nice, but the court does not accept them
directly. Unfortunately, no professor will ever witness against any
other in Germany, so what I need is a book as an evidence.
regards
Hadmut
| |
| George Johnson 2005-07-24, 8:18 pm |
| "Hadmut Danisch" <x5@danisch.de> wrote in message
news:dbktbk$5sg$01$1@news.t-online.com...
| Sportman wrote:
| > Why do you need it to prove to a court?
|
|
| Because the Faculty of Computer Science of the german University of
| Karlsruhe denies this. In a thesis I made a statement based on the
| fact that for every lossy compression scheme there is an input
| where compression-decompression results in transmission errors (that's
| why it is called lossy), and for every lossless compression, there is an
| input where the output of compression is longer than input. Therefore,
| any hidden compression algorithm can cause transmission errors.
|
| The Faculty denied this and a professor claimed, that algorithms like
| MTF and LZ are such epoch making, that they can compress just anything.
|
| I claimed that MTF is not a compression scheme at all, because output is
| always of the same length as input, for LZ well known counterexamples
| exist, and simply by counting bit sequences you can easily prove that
| it is impossible that an universal lossless compression exists.
|
| However, judges are not allowed to judge in other subjects than law.
| Mathematical proofs are nice, but the court does not accept them
| directly. Unfortunately, no professor will ever witness against any
| other in Germany, so what I need is a book as an evidence.
|
| regards
| Hadmut
Just pray that David A. Scott isn't called (he has a 1:1 "compression" /
"scrambling" program which he never shuts up about and is on a cru e to
make "Bijective" a household word).
| |
| Thomas Richter 2005-07-24, 8:18 pm |
| Hi,
> Sportman wrote:
[color=darkred]
> Because the Faculty of Computer Science of the german University of
> Karlsruhe denies this. In a thesis I made a statement based on the
> fact that for every lossy compression scheme there is an input
> where compression-decompression results in transmission errors (that's
> why it is called lossy), and for every lossless compression, there is an
> input where the output of compression is longer than input. Therefore,
> any hidden compression algorithm can cause transmission errors.
Based on the raised question, I *doubt* very much that the faculty
denies exactly *this* statement, and to judge anything about it,
more facts have to be brought up. My personal guess is that someone
here mis-understands the raised problem completely.
> The Faculty denied this and a professor claimed, that algorithms like
> MTF and LZ are such epoch making, that they can compress just anything.
And here is one question of a possible misunderstanding: Believing
that the LZ algorithm is able to generate a smaller output for every
input is easy to prove wrong. You *can* feed everything into the
algorithm, and it is in this sense universal.
A *very simple* question to ask the court would be:
Is the output of the LZ variants again compressible?
As soon as you ask this question, they will come up at least with
proper definitions of what the algorithms can compress. Whether or
not this is helps you with your thesis is a second question. I
doubt very much that this point is really the point of criticism.
(IOW, common sense and the above argument is enough, you don't
have to be a professor to see that there's something wrong with
this wording.)
> I claimed that MTF is not a compression scheme at all, because output is
> always of the same length as input,
But it could be *part* of possible compression codec. In the same
sense, arithmetic coding is not compression either. But *if* you
use the proper sub-division of the starting interval, then it can
be used to implement compression. IOW, I would believe that all the
struggle is around picking exactly the proper words.
> for LZ well known counterexamples
> exist, and simply by counting bit sequences you can easily prove that
> it is impossible that an universal lossless compression exists.
True enough. But is this the issue?
> However, judges are not allowed to judge in other subjects than law.
So what is the lawsuite at hand? The thesis was evaluated badly and
you did not pass?
> Mathematical proofs are nice, but the court does not accept them
> directly. Unfortunately, no professor will ever witness against any
> other in Germany, so what I need is a book as an evidence.
Not necessarely true. *IF* the case is as clear as you write. But
possibly it isn`t. I think before you come up with books and research
in the mathematical direction (which is as obvious as it can be) you
would need to study the arguing of the mentioned professors very
closely. I highly believe that something else is the issue here.
Greetings,
Thomas
| |
| newstome@comcast.net 2005-07-24, 8:18 pm |
| Hadmut Danisch <x5@danisch.de> wrote:
> I claimed that MTF is not a compression scheme at all, because output is
> always of the same length as input, for LZ well known counterexamples
> exist, and simply by counting bit sequences you can easily prove that
> it is impossible that an universal lossless compression exists.
You have to be careful about terminology. In information theory, a
"universal compression algorithm" is one that takes data from any
Markov source and gives an optimal-rate output. It does NOT mean that
all data is compressible: if you feed a uniform random stream into a
universal compressor, it will not compress it -- because it's already
at the optimal rate.
Universal lossless compression schemes exist: LZ77 and LZ78 were both
proved to be universal, as are PPM methods with the right parameters.
On the other hand, almost no one would have a hard time with the
argument that for any lossless compression algorithm, some input will
not get smaller. Even ornery faculty could be convince of this in
less than a minute. With your talk of "court" and "judges" I suspect
there's something else going on...
--
That's News To Me!
newstome@comcast.net
| |
| Hadmut Danisch 2005-07-24, 8:18 pm |
| newstome@comcast.net wrote:
>
> You have to be careful about terminology. In information theory, a
> "universal compression algorithm" is one that takes data from any
> Markov source and gives an optimal-rate output. It does NOT mean that
> all data is compressible: if you feed a uniform random stream into a
> universal compressor, it will not compress it -- because it's already
> at the optimal rate.
>
> Universal lossless compression schemes exist: LZ77 and LZ78 were both
> proved to be universal, as are PPM methods with the right parameters.
Sure, but the dispute was not about the term 'universal'.
In a thesis I made a claim based on the fact, that for every lossless
compression algorithm inputs exists where the output is longer than the
input.
The faculty claimed that this is wrong, because LZ and MTF (which
ironically doesn't change the length of its input) would compress
everything.
> On the other hand, almost no one would have a hard time with the
> argument that for any lossless compression algorithm, some input will
> not get smaller.
Sure. Just count the number of code words of length n of those of length
< n. They are not enough.
There are also simple counter examples for bit sequences which get
longer by LZ compression.
And even if you don't understand anything, just fill some random data in
a file, apply gzip or bzip2, and see how it grows.
Pretty easy. Stuff of the second or third semester in Informatik.
> Even ornery faculty could be convince of this in
> less than a minute.
The faculty of the University of Karlsruhe, Germany, couldn't be
convinced in more than 5 years.
Although they are said to be one of the largest and best faculties in
computer science in germany, the professors of the faculty stated that
they are not competent in this question and can't judge whether it is
correct or not.
> With your talk of "court" and "judges" I suspect
> there's something else going on...
Sure. Doctoral adviser said I'd receive the best grade for my thesis.
Then he demanded that I work for free for him for about one year on my
employers expense. Employer and I refused. Then my thesis was rejected
as wrong. Germany currently suffers from a dramatic raise in corruption.
A new scandal every w .
regards
Hadmut
| |
| Stephan Schulz 2005-08-28, 6:55 pm |
| In article <dbktbk$5sg$01$1@news.t-online.com>, Hadmut Danisch wrote:
>Sportman wrote:
>
>
>Because the Faculty of Computer Science of the german University of
>Karlsruhe denies this. In a thesis I made a statement based on the
>fact that for every lossy compression scheme there is an input
>where compression-decompression results in transmission errors (that's
>why it is called lossy), and for every lossless compression, there is an
>input where the output of compression is longer than input. Therefore,
>any hidden compression algorithm can cause transmission errors.
>
>The Faculty denied this and a professor claimed, that algorithms like
>MTF and LZ are such epoch making, that they can compress just anything.
[...]
>However, judges are not allowed to judge in other subjects than law.
>Mathematical proofs are nice, but the court does not accept them
>directly. Unfortunately, no professor will ever witness against any
>other in Germany, so what I need is a book as an evidence.
Bring an expert witness or witnesses. I'm willing to testify the truth
of the following statement:
"Every lossless compression algorithm that compresses at least one
input will also expand at least one input. In particular, there exist
inputs for the Lempel-Ziff algorithm where the algorithm will expand
the input."
If I'm required for only a single short statement, I'm willing to do
it for cost (about EUR 60-100 for train and cab), just for the fun of
it. If I need to spend more than one day, or if you need a written
report, my normal consulting rates apply.
However, as other noted, I'm very much certain that this is not your
problem, but rather that there are other misunderstandings.
Bye,
Stephan
--
-------------------------- It can be done! ---------------------------------
Please email me as schulz@informatik.tu-muenchen.de (Stephan Schulz)
----------------------------------------------------------------------------
|
|
|
|
|