From: Mauricio Fernandez Date: 2007-03-23T21:18:10+09:00 Subject: Re: Just for fun... On Fri, Mar 23, 2007 at 07:38:28PM +0900, Trans wrote: > On Mar 23, 5:59 am, Mauricio Fernandez wrote: > > I don't see the intention behind your remarks: surely, any practical > > compression method we come up with is going to perform worse than the optimum > > one (whose performance we can only estimate... using inferior compression > > methods!), so what? The existence of an uncomputable lower bound on the length > > of the description of a message is no more of a deterrent to research on > > better (practical) compression methods than e.g. Shannon's theorem is to > > channel coding. > > When did I say otherwise? I believe my original point was simply one > of surprise that BWT improved deflate, which I believe says more about > deflate's deficiencies than BWT's use as a means of compression. I've > only been trying to explain my reasoning for that thought ever since. Ah I see, you were surprised at deflate being so bad... I was surprised at your surprise :) > > 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 not just being > 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?] 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. 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. [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 -- Mauricio Fernandez - http://eigenclass.org - singular Ruby ** Latest postings ** Rich exception hierarchies, multiple inheritance in Ruby http://eigenclass.org/hiki/exception-hierarchies Towards compatibility with Ruby 1.9: Rails, Rake, RubyGems... http://eigenclass.org/hiki/porting-rails-to-ruby-1.9