From: Trans Date: 2007-03-26T09:18:04+09:00 Subject: Re: Just for fun... On Mar 23, 6:15 am, Clifford Heath wrote: > I don't think either existed in 1983 :-). But I expect that > the answer is "no". In any case, neither would suit, as the > compression existed to serve the purpose of full-text search > that had a separate compressed index for every word, and to > use the index, it was necessary to be able efficiently to > open the file at any word. Nowadays I'd open the file at any > disk block boundary, or bigger, since the CPU cost is > negligible next to the I/O cost. You'd probably use some > form of arithmetic coding these days anyhow. Wow. You did that back in 83? I was just learning to code in C64 BASIC :) > >>> "How it does it" is the interesting part. How does BWT improve > >>> deflate? Ie. What's that tell us about deflate? > >> It tells us that there's more to the compressing typical data sets > > That's a little belittling, don't you think? I mean, you've taken one > > connotation of one word I used and seemingly made it the centerpiece > > Ok, I'm sorry, I thought you meant literal repetition, I didn't > mean to unfairly latch on to that, I just needed to clarify that > Shannon's theorem doesn't imply such repetition. Thanks. I understand your take too. I should have been a little more thoughtful in my wording. > > Predictability is not the whole center piece of compression either. > > Hmm. I think perhaps we still disagree then... at least about the > definition of predictability... > > > Pretty predictable. That may seems silly, but there's a point. This is > > not general compression. It doesn't really matter that the process of > > decompression involves a remote machine -- locality is relative. > > Information is relative. Our language is the prime example; if my > words don't evoke symbols in your thoughts that map to a similar > symbolic morphology in you, then we can't communicate. So English > isn't just a set of words, it's a symbolic net whose parts connect > our shared experiences. > > In other words, you, as the "decompressor" of my sequence of words, > must have related context, experience, that forms a morphologically > similar mesh, the nodes of which are associated with words that we > share. > > Taking that as my context, I maintain that your "general" data > stream only has theoretical existence. All meaningful data streams > have structure. There are standard forms of mathematical pattern > search like finding repetition, using Fourier analysis, even > fractal analysis, but these cannot hope to find all possible > patterns - they can only find the kinds of structure they look > for. At some point, those structure types that are coded into the > de/compressors are encodings of human interpretations, not intrinsic > realities. The encoding of the human interpretation is "fair", even > the extreme one in your URL example. Fair enough. I guess I'm limiting my definition of predictability too much. My point was really just that we have to take into account the means of prediction along with the compressed data to measure effectiveness. > > I find this a very fascinating subject. I think ultimately it will > > turn out to be very important, not just for compressing data, but for > > understanding physics too. > > I agree, though I hadn't thought of the physics linkup. I think > that the very structure and nature of knowledge itself is hidden > here somewhere. So's most of our non-conscious learning too, like > learning to walk... though the compression of patterns of movement > in our cerebellum requires an approach to using the *time* domain > in a way I haven't seen a machine implement. Hmm... interesting point. Perhaps OT, but I recall reading some time ago about the discovery that out thoughts are not encoded by brain signals in themselves, but in the timing of those signals. That really threw me for a loop. > > It is interesting to consider that all conceivable data can be > > found somewhere in any transcendental number. > > Since a transcendental number is just an infinite stream of digits, > there exist an infinite number of them that can encode any given > infinite stream of information. I don't know how deep that insight > really is though. I can see that they can encode any "finite" stream. I don't know if they can encode nay infinite stream though. In any case, I agree, whether that's right or not, its probably a minor point. > > You might think, that > > being the case, an excellent compression algorithm would be to find > > the starting digit, say in Pi, for the data one is seeking. But > > curiously it would do you know good. On average the number for the > > starting digit would be just as long as the data itself. > > :-) Good one! I'm sure there's some deep theoretical studies behind > that. Actually it just occurs to me that is probably pretty simple to prove, if you assume that the sequence of numbers of a transcendental are effectively random (which I think is a safe bet). Don't know why that never occurred to me before. > > But I digress, if you think you are so sure about what you are saying, > > and that I am completely off-base, > > Now that you've explained yourself more clearly, I don't > think you're off-base at all. > > > I believe what they are trying to do is essentially impossible. > > I don't know. I wish I knew where I read that the human brain can > "learn" about the contents of 2 CDs - 1200MB, so even Einstein's > knowledge could be encoded into that, if we knew how. The sum of > all human knowledge would doubtless be bigger than that, but I > found it an interesting thought. Some recent neurological research > I read indicated that, contrary to previous thought, our brains > actually do have a limited capacity. The previous assumption of > almost unlimited was based on thoughts about the likely failure > modes when "full" - and those were based on incorrect theories > about how memory works. I could perhaps dig up those papers > somewhere. That's all? Wow. I would have expected at least 100 times that. Of course, that doesn't means it's readily accessible to our conscious mind. Then again, it's hard to judge such large sizes, so maybe 2CDs is about right. > > They should realize either the human brain is just that vast or > > that human knowledge uses lossy compression. > > I don't agree at all. There surely is a limit to the achievable > compression, but we're nowhere near it, and the search will tell > us much about the nature of knowledge. Maybe, but I think the idea that human knowledge is more (lossless) compressible just b/c it is human knowledge is flawed. I'm surprised to hear we are nowhere near the limit though. Not sure why, but I thought we were fairly close, say within 10-20% or so. > Anyhow, interesting stuff, but not about Ruby... continue offline > if you wish... Cool. Thanks for the discussion. Unfortunately I'm pretty busy and need to focus on work, but maybe down the road... T.