Re: Just for fun...

Sorry about the delayed response. I just have too much one my mind...

On Mar 23, 8:18 am, Mauricio Fernandez <m...@xxxxxxx> wrote:

Ah I see, you were surprised at deflate being so bad... I was surprised at
your surprise :)

Truly surprised. Makes me wonder why other formats like 7z aren't more
widely used. Is decompression speed really that much more important
than size?

Regarding your remark on the choice of the universal machine and some choices
not being "general compression", you could add that even if descriptive
complexity relative to two different universal machines differs at most by a
constant term, the latter does matter when we're approximating the algorithmic
complexity in practical scenarios...

I'm sorry. Would you care to put that in layman's terms? I did not
have the good fortunate of academic education in the field (oh, if
only!), so I cannot readily address your statement (assuming of course
you are using academic terms in good faith, and notjustbeing
intentionally obscure).

Sorry, I assumed you were familiar with Kolmogorov complexity and tried to
remove some redundancy [1] from my message based on that premise ;-) (you said
you had been thinking deeply about this so it wasn't too unreasonable :)
[although this is all redundant ultimately and could be replaced by a pointer
into e.g. Cover&Thomas' Elements of information theory; BTW IIRC there's a new
edition in the works?]

I will have to look for that book. Thanks.

What you hinted at in your prev. message is known as the
Kolmogorov(-Chaitin)/descriptive complexity, corresponding to the length of
the minimal description of a string using a program in a given Turing
machine/programming language. It is therefore relative to the universal
machine/language you choose, but if you pick two different ones the
corresponding complexities for a given string can differ at most by a constant
amount, the length of the string that emulates one machine on the other.

In theory, you often ignore such constant factors (just choose a string long
enough :), but in the example you gave, the machine included a full copy of
the KJV bible, allowing it to replicate it with a single instruction... and as
you said the description of the machine itself made all the difference and it
only worked for that particular string, making it of little interest. There's
a sort of trade-off between the complexity of the machine and that of the
programs you feed into it and both parts matter in practice: a machine able to
compress any English text to 1/1000th of its original size wouldn't help
residential users if it included/required a (mildly compressed?) copy of
Google's archive.

Thanks. Makes perfect sense and now I know what to call it. Which is
always good. :)

I probably wasn't 100% intellectually honest in my prev. message, I apologize
for that. I wasn't as much giving new information as trying to drag this
thread into a more information-theoretic OT, hoping some terminology would
trigger interesting replies.

Sounds like you know more about it than anyone else here. So I'm not
sure if I can hold your interest at all. But I might entertain you a
bit with a related story.

When I first learned about the concept of compression, I did some
experimentation. Now, at this point, I had no idea how it was done, or
anything about Huffman coding, or anything like that. But I generally
learn best by experimenting, and that usually means thought
experiments which, aside, also accounts a bit for my lack of "book
smarts". But in any case, I thought about how one might compress data
by algebraic means. I imagined the data as one giant number, and then
considered formula to rapidly approach that number. Exponents of
course grew rapidly, But I figured I needed to grow even faster, so I
"invented" the operation subsequent to "power". I called it, for no
apparent reason: "milk". So

3 milk 3 = 3 ** (3 ** 3)

And I then postulated the next operation as well, which I called
"cheese".

3 cheese 3 = 3 milk (3 milk 3)

Needles to say, 3 cheese 3 is a huge number. I took the final step and
abstracted the set of all such operation starting with addition (O0),
to multiplication (O1), to power (O2), milk (O3), etc. And so I
figured any large number could be represented as a vector Xi, such
that:

Number = Sum(i..0) Oi(Xi+1, Xi)

At that point the problem became trying to salve for this equation
with a given number. I must have filled up every chalk board at my
school working on that. My fellow students thought I had lost my mind!
And I did to as I found myself trying to perform Integration on this
beast! That in fact turned out to be impossible.

Pretty nuts, eh? Of course, I later realized, after solving the
equation manually a number of times, the solutions would be no more
compressed than the original figure. My original idea of "rapid
growth" was flawed. And so it was that I got my first hint of what I
now learn is called "Kolmogorov(-Chaitin)/descriptive complexity".


[1] I'm sensitive to redundancy (as an EE, I've also learned a bit about
it...;). This why I rarely post to ruby-talk anymore; there's very little
surprise in the questions/issues being discussed, and the responses to
new-but-actually-old questions I could give would hardly convey new
information. If everybody killed his messages when they don't pass the
"entropy criterion" the way I do, this ML would have a small fraction of its
current traffic; I cannot ask people to only post things of interest to me
(why would anybody consent to, and how would they know anyway), but I can try
to only post messages that would have interested me. For instance, I was going
to reply "inverse BWT!" to the OP when nobody had responded yet, but I
anticipated somebody would do eventually, so I killed my msg. I don't respond
to questions which are likely to be answered by somebody else (you can call it
proactive global redundancy control by local self-censoring ;).

A nice consequence of this is that it also filters out most unreasonable
content (would I be interested in some ad hominem argumentation? No, so I
should not post any either. The temptation to do so is strong, as some people,
including well-known/knowledgeable posters, use emotionally loaded language
and sometimes defend their positions vehemently.)

sorry again

No need for apologies. No doubt you know that I am far from exemplary
in these affairs, but I believe (or at least hope) that I have gotten
better with time. But with you, well, it almost sounds like you are
playing a game of Prisoner's Dilemma with your posts. And in that
case, I wonder who's winning? ;)


Thanks for the details, btw!
T.


.

Relevant Pages

  • =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>> erm, if your string is minimum, then it is compressed for the reference ... The sequence of an otherwise functional string may be ... >> compressed without regard to its function, but this compression will ... When Sean says that his definition of functional complexity includes ...
    (talk.origins)
  • Re: Just for fun...
    ... compression method we come up with is going to perform worse than the optimum ... of surprise that BWT improved deflate, which I believe says more about ... complexity in practical scenarios... ... corresponding complexities for a given string can differ at most by a constant ...
    (comp.lang.ruby)
  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>>of the string. ... >> universal computing device, say an universal Turing machine, which IS ... K.C. is defined to require an universal computer, ... >These are different forms of potential compression. ...
    (talk.origins)
  • =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>of the string. ... These are different forms of potential compression. ... >>functional system may not be able to sustain such sequence compression ... Chaos theory is about DETERMINISTIC systems which amplify small ...
    (talk.origins)
  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>>As far as Kolmogorov Complexity, let's look at the basic definition one ... When discussion a string of characters. ... >>>the degree of a string's compressibility. ... >>>plays an important role in the concept of chaos. ...
    (talk.origins)
Loading