THE NIGHTLIGHT CHALLENGE
David A. Scott
posts about how great his stuff is and how arithemtic sucks
and is so full of gaps that his stuff will always compress
better. That is not true and I am sure that no matter how dumb
he pretends to be that he knows its not true. After all how
can he quote so much stuff yet not seem to have even a simple
grasp of what arithmetic coding can do.
I am stating this contest. Use QI or whatever you call it
let anyone here create a series of files containing only the
letters "A" "B" and "C" and pretend they come from a source
where any of the 3 symbols equally likely. I can write code to
compress this arithmetically. Let Mr Nightlight write his version.
If he is correct and I know he is not. Then there should be a file
length made of any combination of the 3 letters where his code
will always compress better than the arithmetic due to all the code
gaps and errors he claimes the arithmetic would build up.
He can't do this even though this is really the example he
was proposing to show arithmetic is poor choice when compressing
compared to his stuff. As he rants on refer back to this contest
and ask why he can't do it. If arithemtic is half as bad as
he claims it to be it should be childs play.
This test is really easy to do. Simple file in of only ABC's
and a single file out. Note also he would have to the decompressor
we get enough thinking they have a compressor yet its not real
unless it goes both ways.
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 not sure about all of you, but I get tired of all his
> posts about how great his stuff is and how arithemtic sucks
> and is so full of gaps that his stuff will always compress
> better. That is not true and I am sure that no matter how dumb
> he pretends to be that he knows its not true. After all how
> can he quote so much stuff yet not seem to have even a simple
> grasp of what arithmetic coding can do.
I don't think that's quite correct. Furthermore, I don't think either
that anyone says that "AC sucks". The mentioned coding gaps are, as I
understand it, an "artifact" of a finite- precision
implementation. Without additional tricks, AC cannot keep (zero-order)
probabilities correctly except in special cases, and even then, it
cannot perform the "upscaling" operation common to all AC coders to
infinite precision. The result is a "coding loss" because all these
operations are carried out with finite precision, and that's a coding
loss *per symbol*, not a loss that stays bounded for message size ->
inf.
> I am stating this contest. Use QI or whatever you call it
> let anyone here create a series of files containing only the
> letters "A" "B" and "C" and pretend they come from a source
> where any of the 3 symbols equally likely. I can write code to
> compress this arithmetically. Let Mr Nightlight write his version.
> If he is correct and I know he is not. Then there should be a file
> length made of any combination of the 3 letters where his code
> will always compress better than the arithmetic due to all the code
> gaps and errors he claimes the arithmetic would build up.
Well, one should possibly go for something else than equally likely
symbols, there's no compression here. But pick an order-0 markov
source with probabilities pre-defined, and let us further assume that
the encoder is aware of these probabilities, and they do not need to be
included in the model. Under that constraints, I would be interested
in a comparison. Unfortunately, the mentioned code does not compile
here, but as soon as it does, I'm interested in trying it.
Go for more complicated models later, I first want to understand it in
the simplest possible context. I *do* see that he might have a point,
but I do not yet understand fully how this point is really resolved.
> This test is really easy to do. Simple file in of only ABC's
> and a single file out. Note also he would have to the decompressor
> we get enough thinking they have a compressor yet its not real
> unless it goes both ways.
Yes, a decompressor is a must-have.
So long,
Thomas
Willem
) I don't think that's quite correct. Furthermore, I don't think either
) that anyone says that "AC sucks". The mentioned coding gaps are, as I
) understand it, an "artifact" of a finite- precision
) implementation. Without additional tricks, AC cannot keep (zero-order)
) probabilities correctly except in special cases, and even then, it
) cannot perform the "upscaling" operation common to all AC coders to
) infinite precision. The result is a "coding loss" because all these
) operations are carried out with finite precision, and that's a coding
) loss *per symbol*, not a loss that stays bounded for message size ->
) inf.
Yes. But they're *not* *gaps*. What actually happens is that the
probabilities get quantised, so that some symbols get assigned too many
bits (or too much code space), and others get assigned too few/little.
This will, cause the output size to grow in some cases, and to shrink
in others. It's just that it averages out as a loss.
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
Phil Carmody
> Thomas wrote:
> ) I don't think that's quite correct. Furthermore, I don't think either
> ) that anyone says that "AC sucks". The mentioned coding gaps are, as I
> ) understand it, an "artifact" of a finite- precision
> ) implementation. Without additional tricks, AC cannot keep (zero-order)
> ) probabilities correctly except in special cases, and even then, it
> ) cannot perform the "upscaling" operation common to all AC coders to
> ) infinite precision. The result is a "coding loss" because all these
> ) operations are carried out with finite precision, and that's a coding
> ) loss *per symbol*, not a loss that stays bounded for message size ->
> ) inf.
>
> Yes. But they're *not* *gaps*. What actually happens is that the
> probabilities get quantised, so that some symbols get assigned too many
> bits (or too much code space), and others get assigned too few/little.
Is it not the case that, effectively, with each input symbol the model
behaves as if it's been quantised with deviations specific to the state
of the encoder? I.e. this quantisation almost acts like a quantum noise
on the distribution.
I appreciate I'm not explaining this at all well. I know in my mind what
I'm thinking, but the words aren't taking shape properly.
> This will, cause the output size to grow in some cases, and to shrink
> in others. It's just that it averages out as a loss.
I think we're all agreed on that.
Phil
--
What is it: is man only a blunder of God, or God only a blunder of man?
-- Friedrich Nietzsche (1844-1900), The Twilight of the Gods
Willem
) Is the quatisation actaully a constant one?
I don't think so, no.
) Is it not the case that, effectively, with each input symbol the model
) behaves as if it's been quantised with deviations specific to the state
) of the encoder? I.e. this quantisation almost acts like a quantum noise
) on the distribution.
Yes, quite true.
) I appreciate I'm not explaining this at all well. I know in my mind what
) I'm thinking, but the words aren't taking shape properly.
I know what you mean.
At each stage of the encoding, the range has a different size, and the
quantisation that takes place is dependent on the size of the range.
)> This will, cause the output size to grow in some cases, and to shrink
)> in others. It's just that it averages out as a loss.
)
) I think we're all agreed on that.
Well, yeah. It is the 'always compresses better' that he keeps harping on
about that just simply isn't true. And in his discussions, he keeps on
demonstrating this misunderstanding of his.
Thomas Richter
> ) I don't think that's quite correct. Furthermore, I don't think either
> ) that anyone says that "AC sucks". The mentioned coding gaps are, as I
> ) understand it, an "artifact" of a finite- precision
> ) implementation. Without additional tricks, AC cannot keep (zero-order)
> ) probabilities correctly except in special cases, and even then, it
> ) cannot perform the "upscaling" operation common to all AC coders to
> ) infinite precision. The result is a "coding loss" because all these
> ) operations are carried out with finite precision, and that's a coding
> ) loss *per symbol*, not a loss that stays bounded for message size ->
> ) inf.
> Yes. But they're *not* *gaps*. What actually happens is that the
> probabilities get quantised, so that some symbols get assigned too many
> bits (or too much code space), and others get assigned too few/little.
Ok, agreed, it's not a gap, but a quantization.
> This will, cause the output size to grow in some cases, and to shrink
> in others. It's just that it averages out as a loss.
No, I don't think so. Because you quantize probabilities, the intervals
used by the actual code do not fit to the model any longer, and thus you
code sub-optimal. It would only shrink the output if the model wouldn't
fit to the data. In realistic scenarious, i.e. where the coder has to
guess the model parameters from the input, this might happen. But in an
idealized situation, this is always a loss.
So long,
Thomas
Willem
) No, I don't think so. Because you quantize probabilities, the intervals
) used by the actual code do not fit to the model any longer, and thus you
) code sub-optimal. It would only shrink the output if the model wouldn't
) fit to the data. In realistic scenarious, i.e. where the coder has to
) guess the model parameters from the input, this might happen. But in an
) idealized situation, this is always a loss.
I disagree. In information theory, a model is ideal for a *set* of inputs,
not for a single input. For some items of that set, the quantization
will fit the data better than the ideal model. It's just that the ideal
model will have the optimal average over the set.
Thomas Richter
> ) No, I don't think so. Because you quantize probabilities, the intervals
> ) used by the actual code do not fit to the model any longer, and thus you
> ) code sub-optimal. It would only shrink the output if the model wouldn't
> ) fit to the data. In realistic scenarious, i.e. where the coder has to
> ) guess the model parameters from the input, this might happen. But in an
> ) idealized situation, this is always a loss.
> I disagree. In information theory, a model is ideal for a *set* of inputs,
> not for a single input. For some items of that set, the quantization
> will fit the data better than the ideal model. It's just that the ideal
> model will have the optimal average over the set.
Yes, but I don't think how this invalidates my argument. If I have a
zero-order, non-adaptive AC coder, the update step will always perform
the same update given the same symbol to compress. And it will
consistently do the same error: One interval will be too large, the
other too small, i.e. the size of the interval will not match the
probabilities of the source p_i, but will match the probabilities of
*another* source with probabilities q_i, where q_i is a suitably
rounded/quantized p_i. For example, for a 32 bit precision AC coder,
q_i = p_i rounded to 32 bits. Thus by construction, the resulting
coder would compress a 0-order source with probability distribution
q_i better than a source with probability distribution p_i, and thus
it is not the ideal coder for the given source. All that of course in
the limit symbolcount -> infinity.
So long,
Thomas
Willem
) Yes, but I don't think how this invalidates my argument. If I have a
) zero-order, non-adaptive AC coder, the update step will always perform
) the same update given the same symbol to compress. And it will
) consistently do the same error: One interval will be too large, the
) other too small, i.e. the size of the interval will not match the
) probabilities of the source p_i, but will match the probabilities of
) *another* source with probabilities q_i, where q_i is a suitably
) rounded/quantized p_i. For example, for a 32 bit precision AC coder,
) q_i = p_i rounded to 32 bits. Thus by construction, the resulting
) coder would compress a 0-order source with probability distribution
) q_i better than a source with probability distribution p_i, and thus
) it is not the ideal coder for the given source. All that of course in
) the limit symbolcount -> infinity.
True. If the limit symbolcount -> infinity, then the probability that
the source p_i will produce a sequence with probabilities that are closer
to q_i will tend to zero.
By the way, the roundoff error is different at each AC step, dictated by
the size of the current range, so q_i is actually not a 0-order source.
Sachin Garg
I also feel that he has a valid point, but its no good unless it can be
provably implemented in code. Keeping it to simplest possible models is
also necessary.
Moreover, he said that QI's modelling scheme is conceptually different
from AC's modelling scheme. And adapting any coder to other's modelling
scheme my unfairly tax that coder. So we have two options,
1) If nightlight feels that it is fair to compare QI and AC both
applied to AC style order zero modelling, we can do this.
2) Else, we can compare ...
AC+ "order zero model"
VS
QI + "QI's equivalent of order zero model"
Time comparisons should include total time of coder+modelling. If any
one modelling scheme is more complex than the other, than it is a
"fair" disadvantage for that coder.
Also, the comparison will have to be source level, as we dont want the
time-complexity analysis to get distorted by compiler optimizations (he
has been claiming faster speed too). Both the code-sets should be built
with same compiler with same optimization switches. Of course, in any
one of them is more cache friendly or more prediction-pipeline friendly
etc... , then its a "fair" advantage that we are getting from that
coder.
If nightlight wins this challenge, then it will ofcourse be "good" for
all of us (apart from the fact that QI is, unfortunately, patent
pending). Anyway, best wishes to him :-)
Sachin Garg [India]
http://www.sachingarg.com
Thomas Richter
> True. If the limit symbolcount -> infinity, then the probability that
> the source p_i will produce a sequence with probabilities that are closer
> to q_i will tend to zero.
> By the way, the roundoff error is different at each AC step, dictated by
> the size of the current range, so q_i is actually not a 0-order source.
Yup, exactly. Thanks for pointing that out.
Anyhow, seems the major flaw in nightlight's argueing has been found,
see the thread above. He doesn't understand the update step in AC coding
as it seems. (-;
So long,
Thomas
Thomas Richter
> > I don't think that's quite correct. Furthermore, I don't think either
> > that anyone says that "AC sucks". The mentioned coding gaps are, as I
> > understand it, an "artifact" of a finite- precision
> > implementation. Without additional tricks, AC cannot keep (zero-order)
> > probabilities correctly except in special cases, and even then, it
> > cannot perform the "upscaling" operation common to all AC coders to
> > infinite precision. The result is a "coding loss" because all these
> > operations are carried out with finite precision, and that's a coding
> > loss *per symbol*, not a loss that stays bounded for message size ->
> > inf.
I stand corrected, there are no "gaps", see also above.
> > Go for more complicated models later, I first want to understand it in
> > the simplest possible context. I *do* see that he might have a point,
> > but I do not yet understand fully how this point is really resolved.
> I also feel that he has a valid point, but its no good unless it can be
> provably implemented in code. Keeping it to simplest possible models is
> also necessary.
> Moreover, he said that QI's modelling scheme is conceptually different
> from AC's modelling scheme. And adapting any coder to other's modelling
> scheme my unfairly tax that coder. So we have two options,
> 1) If nightlight feels that it is fair to compare QI and AC both
> applied to AC style order zero modelling, we can do this.
I don't think it should matter. If the mentioned "coding gaps" exist,
then the file size difference between an AC coded file and a QI coded
file should not stay bounded for symbol count -> infinity, and thus QI
would prove its efficency. The same holds for finite precision AC
which should have a coding efficency problem if we pick probabilities
in a way such that the interval size is not divisible by the update
factors. For long runs, the estimated probabilities QI use converge
to the exact probabilities of the source, and it should catch up with
AC and its "finite precision loss". If QI can avoid this finite precision
loss, then the code itself might be interesting.
> 2) Else, we can compare ...
> AC+ "order zero model"
> VS
> QI + "QI's equivalent of order zero model"
That would be already "adaptive" AC. An AC with the right choice for
the adaption rule should generate the probabilities than QI, but
I admit I'm currently too lazy to think about them. (-;
> Time comparisons should include total time of coder+modelling. If any
> one modelling scheme is more complex than the other, than it is a
> "fair" disadvantage for that coder.
Well, I currently *do not care* about timing. A LIFO coder has too many
practical constraints for me right away. It might be an interesting
coding style to begin with, *if* it can prove its effiency.
> Also, the comparison will have to be source level, as we dont want the
> time-complexity analysis to get distorted by compiler optimizations (he
> has been claiming faster speed too). Both the code-sets should be built
> with same compiler with same optimization switches. Of course, in any
> one of them is more cache friendly or more prediction-pipeline friendly
> etc... , then its a "fair" advantage that we are getting from that
> coder.
Yes.
> If nightlight wins this challenge, then it will ofcourse be "good" for
> all of us (apart from the fact that QI is, unfortunately, patent
> pending). Anyway, best wishes to him :-)
From my side as well.
So long,
Thomas
davvid_...@email.com
http://bijective.dogma.net/nitelite.zip
You see the series of files actually compress to
198121 bytes which is exactly the number of bytes
to express the combination for the file. Bijective
arithmetic coders are good at that. If files of
a bit granuilarity instead of 8 bit chuncks you would
use less space. But it looks like I don't really
need to use less space to beat the QI best.
Or should I say current best.
It appears at least at one million symbols for a file the
arithmetic coder uses rounded up to the next whole
byte. What QI would write if written to a file
yet it appears he needs to add other information
thats not needed in the arithmetic coder. But at this
point the finished arithmetic already matches
the QI number of whole byte. Clearly it seems nightlight
overlooked something. Where is this growing error that
is in all arithmetic coders. Where are the gaps that he
seems to think are there? I leave it to the reader. I
have given code that the readers can check. No
old references that may or may not have any real
meaning only real working code.
I think people here after looking at this source code
we quickly see its bijective and meets the requitement
of the challenge. This means he can not beat this compression
for most files. In fact he can't come close unless he bijectifies
has code. But I don't think even though it a "old" method that
he will find any good references on it. Hey its my two cents
worth.
David Scott
PS I may be drunk Take it for what its worht trust no one
who can't test with real code. Don't even trust me
test it. Remember I am an idoit who know belives
I think some one drugged me. Take it with a grain
of salt.
David A. Scott
news:1137129246.0...@o13g2000cwo.googlegroups.com:
I stopped posting on the other thread it was obvious to
me it was going no where But here for those that gave up
that long thread it was obvious my code could do the contest
his could not. Nightlight in his reponse clearly has no
idea what a static order zero compressor does. Some where in
his long posts he realizes that for 3 symbols it should code
roughly log(3) bits per symbol. When I included the extreme test
files like the all A's which is as likely as any of the others
he seemed to think the compressor should have done better than
pkzip. He failed to understand the nature of the problem. The
solution was clearly for this example to compress all files of
3 symbols A B C to the same length except for one byte difference
due to the counting theorm. He failed to realize that even
changing the registers to 32 bits got the same length results.
Though I prefer the 64 bits since most machines can easily handle
this. He then went to rant something about a AC not being able
to handle "the 32 bit alphabet size A32=3,133,061,822". Well this
is more nonsense. First of all what good would it do me to code
for this alphabet when its obvious he doesn't have a real grip
on just what the A=3 compress is suspose to do. If Mr Nightlight
could actually formulate a real compression contest that experts
agree on as valid it might be worth doing. But since he could
not even code the A=3 contest with files I see no reason to write
code for the larger case when it seems clear he most likely would
not. I suggest that he 1) define the contest so several people
here agree its valid. 2) He writes actaully test code to compress
the files. If not I don't see why anyone would code it if he can't
handle coding for the case of 3 it would seem doubtful he could
handle the larger case. Only time will tell. Till then trust not
what you read when you can write simple code to test what others
say is gospel.