🚀 go-pugleaf

]>> Once apon a time, about five years ago, a UK company called DJAI, (the
]>> authors of The Last One - a 4GL program generator) said that they had an
]>> algorithm which would (reversibly) compress arbitrary text into 40-80 bytes.

]> This is a facinating story...  Anyone else ever hear about this?

] Or maybe it's a hoax.  What was the date on the original article? 4-1-87
] maybe :-)

No, Mar-30-87.  But think: when was "about five years ago"?

-- 

Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl

In article <528@savax.UUCP> pitaro@savax.UUCP (Michael Pitaro) writes:
>compresses is arbitrary as long as it's in the database.  Or maybe
>it's a hoax.  What was the date on the original article? 4-1-87 maybe :-)

As far as I remember it wasnt a hoax but a con and I dont think it was
to do with the Last One people either. I recollect that someone was
touring the country charging 500 pounds for a seminar on this technique.
Several people paid him "just in case". The man I am thinking of
subsequently vanished with a large sum of money.....


Lindsay

-- 
Lindsay F. Marshall, Computing Lab., U of Newcastle upon Tyne, Tyne & Wear, UK
JANET: lindsay@uk.ac.newcastle.cheviot  ARPA: lindsay%cheviot.newcastle@ucl-cs
PHONE: +44-91-2329233                   UUCP: <UK>!ukc!cheviot!lindsay
"How can you be in two places at once when you're not anywhere at all?"

>> Once apon a time, about five years ago, a UK company called DJAI, (the
>> authors of The Last One - a 4GL program generator) said that they had an
>> algorithm which would (reversibly) compress arbitrary text into 40-80 bytes.
>> They even had a demonstration system which claimed to show the algorithm in
>> operation.
>>
>> They planned to demonstrate the system by compressing the complete source
>> text of The Last One, copying the <80 bytes to a hand-held micro with a
>> printer, then decompressing and producing the total listing from the micro.

> Anyone know -anything- (or have any guesses) about the algorithm?

There are algorithms that can do this, though whether they could be
implemented on a micro is problematical.  The one that comes to mind is
converting the arbitrary text into one _very_ large number and then
representing that number as a combination of powers of smaller numbers.

E.g.:  1234^5678 + 456^123 + 90^20 - 8^2 - 3

Note the above amount probably couldn't be contained in the known universe
if you attempted to write it out in full, but the above representation is
highly compact.  Sorry, I'm not aware of the details of how the text
conversion and restoration is done.  I think Kurt Goedel (as in _Goedel,
Escher, Bach: an Eternal Golden Braid_) first proposed the technique
(occasionally referred to as "Goedelizing").

-- 
The Polymath (aka: Jerry Hollombe, hollombe@TTI.COM)
Citicorp(+)TTI
3100 Ocean Park Blvd.   (213) 450-9111, x2483
Santa Monica, CA  90405 {csun|philabs|psivax|trwrb}!ttidca!hollombe

In article <4542@columbia.UUCP> metzger@garfield.columbia.edu.UUCP (Perry Metzger) writes:
>Look folks, as we all know from being cryptographers (you do actually
>know a bit about the subject, don't you?) that the redundancy of
>english is NEVER estimated by anyone in his right mind at more than
>75%, so thus it is impossible to compress it beyond that in general.

Unless you take symbolic representation into account.  Say you
numbered the (2^14)-1 words, and used that to replace just the
absolute matches (forgetting about endings etc), you would already be
elimintating more than you claim, before even implementing redundancy
techniques.  If you read a little more on the subject, you would
realize there is more than one way to skin a cat.

-- 

Paul Guthrie
ihnp4!ihdev!pdg			This Brain left intentionally blank.

In article <1323@ihdev.ATT.COM> pdg@ihdev.UUCP (Joe Isuzu) writes:
>Unless you take symbolic representation into account.  Say you
>numbered the (2^14)-1 words, and used that to replace just the
>absolute matches (forgetting about endings etc), you would already be
>elimintating more than you claim, before even implementing redundancy
>techniques.  If you read a little more on the subject, you would
>realize there is more than one way to skin a cat.

Sorry, you still lose. If you do that, you are not compressing an
ARBITRARY text that much. For instance, if I have 256 books in my
library, and each one of them contains say a million words (I know
that is big) you can then compress any book in the library down to 8
bits, provided that you know that the text you are transmitting is in
the library. But then, you see, you are not compressing an ARBITRARY
text, only a text you can find in that limited library. If I pick
completely random text I can't do that.

Enough of this.

.pm

In a previous article Perry Metzger writes:
+  Joe Isuzu writes:
+>Unless you take symbolic representation into account.  Say you
+>numbered the (2^14)-1 words, and used that to replace just the
+>absolute matches (forgetting about endings etc), you would already be
+>elimintating more than you claim, before even implementing redundancy
+>techniques.  If you read a little more on the subject, you would
+>realize there is more than one way to skin a cat.

+Sorry, you still lose. If you do that, you are not compressing an
+ARBITRARY text that much. For instance, if I have 256 books in my
+library, and each one of them contains say a million words (I know
+that is big) you can then compress any book in the library down to 8
+bits, provided that you know that the text you are transmitting is in
+the library. But then, you see, you are not compressing an ARBITRARY
+text, only a text you can find in that limited library. If I pick
+completely random text I can't do that.

  The subject was English text.  Last time I checked, English was not
completely arbitrary.  Illogical, perhaps, but not *completely* arbitrary.
The above described technique would work fairly well on most text,
although I'm not sure whether it would allow you to break the 75% barrier
you previously referred to.  Maybe.


-- 
Robert Bickford         {hplabs, ucbvax, lll-lcc, ptsfa}!well!rab
terrorist cryptography DES drugs cipher secret decode NSA CIA NRO IRS
coke crack pot LSD russian missile atom nuclear assassinate libyan RSA

In article <1323@ihdev.ATT.COM>, pdg@ihdev.ATT.COM (Joe Isuzu) writes:
> In article <4542@columbia.UUCP> metzger@garfield.columbia.edu.UUCP (Perry Metzger) writes:
>> Look folks, as we all know from being cryptographers [...] that the
>> redundancy of english is NEVER estimated [...] at more than 75%, so
>> thus it is impossible to compress it beyond that in general.

> Unless you take symbolic representation into account.  Say you
> numbered the (2^14)-1 words, and used that to replace just the
> absolute matches (forgetting about endings etc),

What you appear to be suggesting is not just compressing English text
but representing it at a higher level.  If you "compress" beyond the
point of discarding all redundancy you are losing information; in other
words, there will be distinct input texts which compress to the same
compressed text, which means it will be impossible to correctly
regenerate both of them from the compressed text.  For example, in
English there are often two (or more) ways to represent the same
concept.  We are not interested in merely storing ideas (or if we are,
we should be explicit in admitting it), we want to compress text and
then uncompress to the exact same sequence of bytes.

Alternatively, your posting could be taken to mean that you believe
there is more than 75% redundancy in English.  In the case of Usenet
postings I fear you are correct - maybe your software would improve
netnews performance! -- what's that?  You don't have this implemented?
Then how do you know it works?  Go ahead and try it; I suspect you will
find it doesn't compress by as much as you think it will.

					der Mouse

				(mouse@mcgill-vision.uucp)