Loss less random data compression – Is it possible? The answer is NO (.... and yes!)
Kechu
Sorry I couldn't post here for 2 reasons.
1. Blog is too long
2. I want the user comments to be available at my blog.
Tom St Denis
> The article I posted in my blog -http://blog.adityon.com/2009/12/random-data-compression-is-it-possible/
>
> Sorry I couldn't post here for 2 reasons.
> 1. Blog is too long
> 2. I want the user comments to be available at my blog.
Good luck with that.
Earl_Colby_Pottinger
>
> Sorry I couldn't post here for 2 reasons.
> 1. Blog is too long
> 2. I want the user comments to be available at my blog.
You try to make a claim, but you refused to show the math. You lost
me at that point.
So if you want anyone to pay you any attention WRITE SOME WORKING
CODE! All else is scam artists claims, and in this case an attempt to
raise hits on your blog. If you want to see your hit count fly WRITE
SOME WORKING CODE!
jules Gilbert
Don't feel too bad, Kechu:
Earl hasn't been real nice to me, either. I'm sure his Mom loves him,
but me, not so much...
However, I've decided I have a retraction to make. Read my latest
note (which I am going to compose now.)
--jg
Earl_Colby_Pottinger
> Earl hasn't been real nice to me, either. I'm sure his Mom loves him,
> but me, not so much...
Not nice? I have been very nice considering the lanuage you have used
to me and others in the past. Add in the fact of all your scam-like
claims without proof and how you try so hard to avoid any honest
testing of your claims.
Anyone reading my exchanges and comparing them to your weasel-like
replies will consider me to be very nice indeed.
Phil Carmody
But why? The guy's a waste of biomass who has demonstrated absolutely
no intention to learn anything about the field he pretends to be working
in, and spews inane crap constantly which ranges in content between
lies, being wrong, and being *not even wrong*.
There's precisely no reason for anyone to be nice to him at all.
Making him so irate that he throws his computer off his desk and can
no longer post to usenet would be a vast improvement.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
jules Gilbert
wrote:
First, whatever is "r a s -- f1"? I hope you will enlighten me.
I am familiar with an English CS researcher by that name. Are you
referring to his work in numerical processing (I may have the name
slightly wrong, I didn't Google it, I read his papers a year or so
ago...)
To Phil and Earl, you guys are two of the big reasons I haven't
disclosed -- in fact I wrote up a patent for one method but my patent
attorney explained to me that it would be impossible to stop others
from making use of my algorithm outside of the US. Sadly I really
don't have any alternative but to keep my work under wraps until I
sell the method, -- and I've made at least a dent in this field, I'll
let others decide how much of a dent.
Noob
> Phil Carmody wrote:
>
>> Phil
>> --
Phil, your signature delimiter is missing the trailing SPACE.
>> Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
>
> First, whatever is "r a s -- f1"? I hope you will enlighten me.
Are you new to Usenet?
Jim Leonard
> To Phil and Earl, you guys are two of the big reasons I haven't
Nice try. There are years of examples of you blaming others, like
Mark Nelson or Matt Mahoney.
I know about your previous experiments and demonstrations. You run
data through a program and it spits out stats on how that data could
be reconstructed. But you never consider that the output of the stat
program can never be in a representation smaller than the input data.
So your system does not actually compress anything. You just look at
the stat output and assume that the information is "free". Nothing is
free.
Phil Carmody
> Jules Gilbert wrote:
>
>> Phil Carmody wrote:
>>
>>> Phil
>>> --
>
> Phil, your signature delimiter is missing the trailing SPACE.
Please check your facts before posting nonsense to usenet; I always do.
Phil
--
Kechu
> The article I posted in my blog -http://blog.adityon.com/2009/12/random-data-compression-is-it-possible/
>
> Sorry I couldn't post here for 2 reasons.
> 1. Blog is too long
> 2. I want the user comments to be available at my blog.
Hi all,
Second part of the article published in my blog -
http://blog.adityon.com/2009/12/random-data-compression-is-it-possible-part-2/
All valuable comments are welcome.
If you feel blog contents are not logical or reasonable, please ignore
instead of giving negative feedback without any valuable or correct
suggestion.
Thanks & regards
Keshav K Shetty (Kechu)
Thomas Richter
> All valuable comments are welcome.
>
> If you feel blog contents are not logical or reasonable, please ignore
> instead of giving negative feedback without any valuable or correct
> suggestion.
Your blog *is not* logical or reasonable, indeed. This is because you
haven't well-defined the problem you want to talk about, and thus you
mess with issues from physics, mathematics, meta-physics etc, that have
no relation to compression.
If you want to analyze a problem, you *first* need to define the problem
- and this very crucial step is missing - and this is why you fail.
Asking people to *ignore* such problems instead of pointing at them is
not very professional. If you want to improve, you need to be open for
critique instead of asking people to shut up.
So, here is the very first exercise: What *is* compression?
So long,
Thomas
inconnu
I would answer:
keeping the noise of a file :)))
or, transforming a nice file into noise :)))
and if you don't believe me, just have a look at a compressed file !
Kechu
Hi Thomas,
About the problem definition
All valuable feedback are welcome.
I mentioned "please ignore instead of giving negative feedback without
any valuable suggestion".
Earlier I received few email like "one more fraud or fake claim" etc -
such feedback won't help anyone.
Negative feedback without any reason or justification will not serve
any purpose.
I repeat all valuable feedback are welcome. But "feedback without any
reason or without any valuable feedback" are not necessary.
I hope you understood my point of view when I said "please ignore
instead of giving negative feedback without any valuable suggestion".
About defining problem "Indeed it is not well defined in my initial
article", which I will correct it and define well in coming post as
well as old posts.
Thomas Richter
Well, in a "humorous" way, yes, of course. In fact, one can prove that a
compressed file must have zero-order statistics that looks like a
Bernoulli source (i.e. like a coin-throw experiment).
Anyhow, if taken serious, this argument starts at the wrong ends since
one then first need to understand what "noise" is, which is an even
harder problem.
Compression, as a definition of the word, has nothing to do with noise,
just with 1:1 mappings between sets, that's all. The "noise" part comes
in when it comes to the question which sources can be compressed by a
given algorithm and which can't, but somehow this is almost a tautology:
Noise is what is what you cannot compress, so you cannot compress noise.
Thus, any attempt to *define* compression should probably better avoid
the word. It is not needed in its definition, and IMHO a secondary term.
So long,
Thomas
biject
> inconnu wrote:
> >> So, here is the very first exercise: What *is* compression?
>
> > I would answer:
>
> > keeping the noise of a file :)))
>
> > or, transforming a nice file into noise :)))
>
> > and if you don't believe me, just have a look at a compressed file !
>
> Well, in a "humorous" way, yes, of course. In fact, one can prove that a
> compressed file must have zero-order statistics that looks like a
> Bernoulli source (i.e. like a coin-throw experiment).
>
Actually with a bijective compressor any file can be thought
of as either a compressed file or uncompressed file. Maybe like
the argument is light a wave or particle.
Just like a coin toss you could end up with the greatest
written works in literature. Yes its not likely but its not
zero either.
I don't believe you can prove a compressed file must have
zero-order statistics that looks like a Bernoulli source.
Mybe a certain subset of compressed files from a small set
of files would have this propery but thats all.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Thomas Richter
> I don't believe you can prove a compressed file must have
> zero-order statistics that looks like a Bernoulli source.
> Mybe a certain subset of compressed files from a small set
> of files would have this propery but thats all.
See the proceedings of last year's DCC (Data Compression Conference) for
a precise statement and the proof, by Robert Gray. Yes, one can prove
that. Here is the article:
Bits in Asymptotically Optimal Lossy Source Codes Are Asymptotically
Bernoulli
Gray, R.M.; Linder, T.
Page(s): 272-281
Digital Object Identifier 10.1109/DCC.2009.21
The hand-waving argument is of course that in case the statistics
wouldn't be Bernoulli, you could compress the output again with a
zero-order coder, hence you would be in contraction to optimal coding.
The article makes that just more precise, i.e. in which sense the output
approximates Bernoulli.
Greetings,
Thomas
biject
Actually your wrong since its a fact for a good bijective
compressor its possible to get any file as an output. Since
any file can either be thought of as a compressed file
or an uncompressed file.
Its quite possible even with an I.I.D. source to get the
best compression with my bijective arb255. And yet you
could still get an output file that if you ran it through
arb255 a second time you get more compression. However that
does not mean the compressor failed. Since for most files
you get with real data a second pass would likely cause the
file to increase in length.
I don't have much faith in so called peer reviewed proofs
is there a pointer normal people can read. But clearly the
fact that sometimes an output file could be compressed smaller
my the same or other means is not proof the original compressor
failed to do its job in an optimal way.
Thomas Richter
> Actually your wrong since its a fact for a good bijective
> compressor its possible to get any file as an output. Since
> any file can either be thought of as a compressed file
> or an uncompressed file.
/* snip */
You seem to misread on purpose, otherwise I don't see what you're
getting at.
First of all, you need to understand the terms precisely Robert talks
about. "Optimal" doesn't mean "bijective". "Optimal" means reaching
asymptotically the entropy bound. The difference between that and a
coder that uses the coding space optimally is asymptotically
neglectable. Second of all, you need to understand *how* it approaches
the Bernoulli statistics, i.e. in which measure this limit is reached.
> Its quite possible even with an I.I.D. source to get the
> best compression with my bijective arb255. And yet you
> could still get an output file that if you ran it through
> arb255 a second time you get more compression.
Self-contradicting. Either it is "best" or "not best". If it is "best",
you cannot compress it a second time. Anyhow, this is not the meaning
of "optimal" in the sense of the paper above, i.e. "optimal" doesn't
mean taking the infimum over all possible compressors to compress a
random bit stream, but a compressor that reaches the entropy limit on an
ergodic source.
> However that
> does not mean the compressor failed.
Depending on the definition of "failed", I would call a compressor that
isn't able to reach the entropy limit "failing", yes. But that doesn't
matter really for the discussion.
> Since for most files
> you get with real data a second pass would likely cause the
> file to increase in length.
>
> I don't have much faith in so called peer reviewed proofs
> is there a pointer normal people can read.
Huh? Why simply don't you read it? Robert Gray is not an unknown in
source coding, looking back at >30 years of experience in the field.
Thus, holding your inability to read a well-written scientific paper
against the author is not a very founded critique.
> But clearly the
> fact that sometimes an output file could be compressed smaller
> my the same or other means is not proof the original compressor
> failed to do its job in an optimal way.
No, you don't understand. Scott, your problem is that you want to
discuss the contents of what is stated without really understanding
*what is precisely stated*. You first need to understand what is meant
precisely, and whether or not your compressor can compress the same
source a second time a bit better is mostly irrelevant. What is relevant
here is the asymptotics and the limiting case, and not whether a coder
uses its coding space completely. The latter is typically not considered
a required property, and doesn't matter for most applications in first
place if the loss is vanishing in the limit case.
Greetings,
Thomas
Willem
) biject wrote:
)> On Dec 23, 11:24 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
)>> biject wrote:
)
)> Actually your wrong since its a fact for a good bijective
)> compressor its possible to get any file as an output. Since
)> any file can either be thought of as a compressed file
)> or an uncompressed file.
)
) /* snip */
)
) You seem to misread on purpose, otherwise I don't see what you're
) getting at.
He's simply getting at the fact that if you exclude compressible files from
the output space, you're needlessly restricting it, forcing the output to
be bigger on average.
)> Its quite possible even with an I.I.D. source to get the
)> best compression with my bijective arb255. And yet you
)> could still get an output file that if you ran it through
)> arb255 a second time you get more compression.
)
) Self-contradicting. Either it is "best" or "not best". If it is "best",
) you cannot compress it a second time.
Only if you use a stupid definition for 'best', see above and below.
) Anyhow, this is not the meaning
) of "optimal" in the sense of the paper above, i.e. "optimal" doesn't
) mean taking the infimum over all possible compressors to compress a
) random bit stream, but a compressor that reaches the entropy limit on an
) ergodic source.
And such a compressor will output compressible data for some inputs.
Except if you specifically tailor it not to, which would be stupid as
explained above.
) Depending on the definition of "failed", I would call a compressor that
) isn't able to reach the entropy limit "failing", yes. But that doesn't
) matter really for the discussion.
This has nothing to do with reaching the entropy limit.
You can reach the entropy limit and still output compressible data.
Hell, even a row of all-zero bits is a possible valid output.
Highly unlikely, yes, but not impossible.
I know what you're trying to get at, but you really should be more
careful in phrasing your arguments.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
biject
Great Post I wrote a longer one right after Thomas but
maybe I hit the wrong button since it never appeared. I
guess what angered my more was that I could not find a
paper that Mr Thomas said to read. Where is it? Where is
a link on the net to find it. I found some that lead you
to a site to pay $19. But why pay for something that at
least the way Thomas explains it appears to be wrong?
I hope he can follow what you said but I doubt it.
Again Thanks for you post Willem
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
Thomas Richter
> ) You seem to misread on purpose, otherwise I don't see what you're
> ) getting at.
>
> He's simply getting at the fact that if you exclude compressible files from
> the output space, you're needlessly restricting it, forcing the output to
> be bigger on average.
No, that's not the case, I'm not *excluding* anything. I'm only taking
about the "average" case, as always.
> )> Its quite possible even with an I.I.D. source to get the
> )> best compression with my bijective arb255. And yet you
> )> could still get an output file that if you ran it through
> )> arb255 a second time you get more compression.
> )
> ) Self-contradicting. Either it is "best" or "not best". If it is "best",
> ) you cannot compress it a second time.
>
> Only if you use a stupid definition for 'best', see above and below.
Actually, this is not the definition of "optimal" that matters here, see
my next sentence.
> ) Anyhow, this is not the meaning
> ) of "optimal" in the sense of the paper above, i.e. "optimal" doesn't
> ) mean taking the infimum over all possible compressors to compress a
> ) random bit stream, but a compressor that reaches the entropy limit on an
> ) ergodic source.
>
> And such a compressor will output compressible data for some inputs.
Sure enough, as do all compressors, but that isn't the point. An
"optimal compressor" can be, obviously, only optimal for a given source,
it cannot compress all sources.
> Except if you specifically tailor it not to, which would be stupid as
> explained above.
>
> ) Depending on the definition of "failed", I would call a compressor that
> ) isn't able to reach the entropy limit "failing", yes. But that doesn't
> ) matter really for the discussion.
>
> This has nothing to do with reaching the entropy limit.
Sure it does. If a compressor isn't able to reach the limit of the model
source, it is not optimal.
> You can reach the entropy limit and still output compressible data.
Nope, because entropy is the lower limit to allow successful
reconstruction. Except for "stupid definitions of compressible" as in
"there are exceptional cases for which the output is compressible"
compared to "in average the output is compressible".
> Hell, even a row of all-zero bits is a possible valid output.
> Highly unlikely, yes, but not impossible.
That's exactly what I say. All these "optimality" definitions are of
course to be read "in the expectation". An exceptional case doesn't
matter. In the same sense, of course a Bernoulli source can have an
outcome that is compressible. It is just not very likely.
And this is what is claimed there, namely: The output *looks* like
Bernoulli for the right input, obviously. A finite subsequence of the
output may be compressible in exceptional cases, as much or as bad as a
finite substring of a Bernoulli source may be compressible in
exceptional cases, but that's what's always the case with probability
sources - statements only make sense in the limiting or average case.
> I know what you're trying to get at, but you really should be more
> careful in phrasing your arguments.
Right, exactly so. Words must be chosen very carefully, and that's also
why I gave reference.
So long,
Thomas
inconnu
> Actually your wrong since its a fact for a good bijective
> compressor its possible to get any file as an output. Since
> any file can either be thought of as a compressed file
> or an uncompressed file.
right, this was proved a few years ago:
http://arxiv.org/abs/cs.IT/0511074
there are several papers on the properties of the bijective compression
(known today as a property of Lindon words, if I well remember ; I also
saw some papers where they put your name, nice to see some scientists
are honest...)
I remember you were claiming this "bijection" for many years but
"scientists" didn't take into account your claims, because you didn't
write a paper in their own language (unreadable by those who don't get
use to write in a sophisticated language, even for writing simple things)
example:
normal language : let's take a binary string.
scientific language : let's take x , such as x belongs to { 0 1 } *
it doesn't matter, with a small effort, one can read what they say...
Ernst
wrote:
Oh I find this group a riot.
I come back and there we all are again..
LOL.. you nut cases!
Jules is still one hitch away from success..
And the rest are grumpy still for the most part!
Great stuff..
Hey Happy new Year..