Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

First Hutter Prize Awarded

Posted by kdawson on Sun Oct 29, 2006 09:07 PM
from the compress-this dept.
Science
stefanb writes, "The Hutter Prize for Lossless Compression of Human Knowledge, an ongoing challenge to compress a 100-MB excerpt of the Wikipedia, has been awarded for the first time. Alexander Ratushnyak managed to improve the compression factor to 5.86 and will receive a 3,416-Euro award. Being able to compress knowledge well is believed to be related to acting intelligently." The Usenet announcement notes that at Ratushnyak's request, part of the prize will go to Przemyslaw Skibinski of the University of Wroclaw Institute of Computer Science, for his early contributions to the PAQ compression algorithm.
+ -
story
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

First Hutter Prize Awarded 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • Seems like a strange contest (Score:5, Interesting)

    by Salvance (1014001) * on Sunday October 29 2006, @09:17PM (#16637656) Homepage Journal
    It turns out that Alexander Ratushnyak was the only person to even meet the challenge's guidelines, and one of only 3 people who submitted entries. Seems like a strange thing to award up to 50,000 Euro for ... his compression was only 20% smaller than what I just quickly did with gzip. I'm rather surprised that more people didn't try though ... it's not like people are throwing money at data compression researchers.

    • Re: (Score:3, Informative)

      by Barny (103770)
      20% of a few petabytes is.... a lot :)

      And yes, offering cash in this way is a great incentive for programers.

      Also, if its a cpu friendly (read: reasonable cpu useage or even able to be offloaded on a processing card) method it could potentially add 20% onto your bandwidth :)

    • Re: (Score:3, Interesting)

      by Raul654 (453029)
      There aren't many Wikipedia related things I don't know about (I'm a Wikipedia administrator, arbitrator, and bureacrat, featured article director, and I'm on the Wikimedia Foundation's Press Committee), and this is the first time I've ever heard of this contest. I think it's fair to say it's been relatively low-profile.

      • Re:Seems like a strange contest (Score:4, Insightful)

        by rbarreira (836272) on Monday October 30 2006, @04:23AM (#16639817) Homepage
        There aren't many women related things I don't know about (I have a girlfriend, I've had sex, my mother and my sisters are all women), and this is the first time I've ever heard of the "women's olympic weighlifting" contest. I think it's fair to say it's been relatively low-profile.
        • Why use Wikipedia then? There must be dozens (if not hundreds or thousands) of free sources of regular text out there.
    • It turns out that Alexander Ratushnyak was the only person to even meet the challenge's guidelines

      Wow, that makes me really wish I had entered. There are some great multipass lossless text compression systems that would work well for Wikipedia...
        • Does anyone know if WinRK [wikipedia.org] has been submitted? It's probably pretty slow, and may go over the 10 hour time limit.
          • WinRK uses PAQ technology. Since the winner in this story used a tweaked PAQ engine, I doubt that WinRK would perform better. Better than the WinZip, et al, examples people have been posting, but not better than the winning entry.
    • Keep in mind that the rule was that the file had to be a self executable. If you just did default gziping, you'd have to include the overhead of a self executable in the total.
      • The overhead for both compression and decompression on my box anyway looks to be about 50k (the size of my /bin/gzip).

        No clue whether it requires more code to compress than to decompress, but I would guess your overhead would be less than 30k. On an order of maybe 20MB of compressed data, that's not much.

        GZIP is a bad example because it also works with binary data; it's too much. If you only have to worry about encountering 128 possible values, compression can get real interesting, and there are a lot mor
        • The only problem is that if your heuristics are designed for this specific chunk of data, it'll end up being largely useless for a full database crunching. Mind you, they could still be useful, but you don't want them to be sample-specific when you're talking about orders of magnitude more data that will need to get compressed.

          I really don't know jack about how compression is done, but I can toss out an idea. Scan article text for all of the used characters... expect to find your A-Z a-z 0-9 and some char
    • Finding a way to compress just a little bit more, becomes an increasingly harder problem. You begin to hit entropy limits, and have to use methods that are only relevant to the type of data being compressed. For example, a good lossless audio compressor won't handle text data very well, and vice versa.
      Most compressors in this space use a prediction algorithm to generate a signal, and then only compress the differences between the generated signal and the actual data. To get the best possible compression, yo

    • Re: (Score:2, Informative)

      by CryoPenguin (242131)
      Since the criteria for entry say that any new submission must beat the current record, it's no surprise that only 3 people are listed. You're not seeing any of the people who didn't win.

  • Lossless from Lossy? (Score:2, Funny)

    by Anonymous Coward
    "The Hutter Prize for Lossless Compression of Human Knowledge, an ongoing challenge to compress a 100-MB excerpt of the Wikipedia"

    Wikipedia? Knowledge? Isn't that already a lossy compression mechanism?

  • Hmm... (Score:4, Funny)

    by Cinder6 (894572) on Sunday October 29 2006, @09:25PM (#16637732)
    Am I the only one who finds it slightly ironic that (as of this writing), there is no entry for the Hutter Prize on Wikipedia?

  • For comparison .... (Score:4, Informative)

    by Ignorant Aardvark (632408) <cydeweys.gmail@com> on Sunday October 29 2006, @09:26PM (#16637738) Homepage Journal
    For comparison purposes, WinRAR on its best setting only gets this down to 24MB. Doubtless 7zip could get even lower, but I don't think either could crack the 17MB mark. And certainly neither of those would be self-extracting, which this contest requires.
  • How slow this code is. Usually when you are trying to squeak out another 1% of space in a file your algorythm triples in size and quadruples in runtime to get that improvement. I wonder how practical this new algorythm really is. Probably not so much an issue nowadays but I also wonder how big the compression program is. This used to be a really big deal many years ago when the compression programs could easily be larger than the data they were compressing.
    • Accoring to somebody who posted above (he probably read it in the article, but i'm not about to look there), the program took, 5 hours and 900MB of RAM. I find it's interesting that he only got down to 17MB, while consuming all those resources. It makes it seem like it isn't even worth it. I'm sure you could find some pretty small program that would compute pi to some very large number of digits, and find the wikipedia excerpt in the results, but It would take a very long time to run.

      • Re: (Score:3, Informative)

        by AxelBoldt (1490)

        I'm sure you could find some pretty small program that would compute pi to some very large number of digits, and find the wikipedia excerpt in the results, but It would take a very long time to run.

        In all likelihood, that trick won't work: your program would need to know the start index of the Wikipedia text in the digit sequence of pi, and that index would be so astronomically huge that writing it down would be about as long as writing down Wikipedia itself. As a little example of the effect, think about

        • Re:makes one wonder (Score:5, Funny)

          by Henry V .009 (518000) on Sunday October 29 2006, @10:58PM (#16638307) Journal
          Assuming a random distribution of digits in pi (and why does everyone assume this? -- there is certainly no proof), the odds are that you'll see one sequence of 4 zeros every 10,000 (decimal) digits. On the other hand, you'd expect to see 4 zeros once every 16 binary digits. Wikipedia, at 100MBs would be expected to be found once every 2^800,000,000 binary digits of pi.

          Then again, maybe we're lucky, and this universe is God's way of storing the universal encyclopedia in the digits of pi. Wikipedia might be up near the front somewhere.
        • Tangentially related and mildly amusing trivia:

          Feynman Point [wikipedia.org]. From the Wikipedia article: "The Feynman point comprises the 762nd through 767th decimal places of pi ... The name refers to a remark made by the physicist Richard Feynman, expressing a wish to memorise the digits of as far as that point so that when reciting them, he would be able to end with '... nine, nine, nine, nine, nine, nine, and so on.'"

          So, I dunno about "0000," but for some interesting sequences we may get lucky :).
    • FTFA:
      Restrictions: Must run in less than 10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD.
      If someone's program takes close to 10 hours to compress 100MB it better get considerably more than just an additional 1% out of it!

      • If someone's program takes close to 10 hours to compress 100MB it better get considerably more than just an additional 1% out of it!

        Indeed. Who in their right mind would spend 10 hours compressing instead of simply moving the entire dataset in a fraction of the time?

        Oh, and for a good compression scheme:

        uuencode filename filename | mail external@stora.ge

        Then all the decompresser needs to do is fetch the mail and uudecode it.

        Regards,
        --
        *Art

    • If you'd RTFA you'd find the running times ranged from 30 minutes to 5 hours. They have a whole table and everything.



      The whole point of the challenge was to create a self-executing compression program that made a perfect copy of their 100MB file. Final file sizes were in the 16MB range. Geeze, seriously RTFA.

  • compress knowledge = intelligence (Score:3, Insightful)

    by Profound (50789) on Sunday October 29 2006, @09:56PM (#16637998) Homepage
    Being able to compress knowledge well is believed to be related to acting intelligently. - IHNPTTT (I Have Not Passed The Turing Test), but while my brain is good at remember the gist of knowlege, but really bad at losslessly recalling it.
  • ... by Douglas Adams. Wonder what rate of compression is putting the meaning of life, universe and everything in just the number 42.
  • is what you get when you run the new compression backwards!

    This reminds me of the cryptographer paid to crypto-compress datastreams into musical notation. The work laid the foundation to real time packet sniffing of the Internet

    Cryptographer? Got atta boys

  • Done on 9/25/06? (Score:3, Interesting)

    by SillySnake (727102) on Monday October 30 2006, @12:02AM (#16638629)
    According to http://prize.hutter1.net/ [hutter1.net] this happened on Sept 25 of 2006.

    The site also gives some of the requirements..
    Create a compressed version (self-extracting archive) of the 100MB file enwik8 of less than 17MB. More precisely:

            * Create a Linux or Windows executable of size S L := 17'073'018 = previous record.
            * If run, it produces (without input from other sources) a 108 byte file that is identical to enwik8.
            * If we can verify your claim, you are eligible for a prize of 50'000×(1-S/L). Minimum claim is 500.
            * Restrictions: Must run in 10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD.
  • http://www.cs.fit.edu/~mmahoney/compression/text.h tml [fit.edu]

    Info about contenders and results of common compression programs on the testset. (All the "just use gzip/rar/winrk/..." fools can stop jabbering now...)

    • Re:what the hell? (Score:4, Funny)

      by Barny (103770) <bakadamage-slashdot@yahoo.com> on Sunday October 29 2006, @09:25PM (#16637728) Journal
      Hehe, and remember the study a few months back that found that the order of letters within a word is unimportant, so long as the first and last are correct? Potentially big words could be listed merely by how many of each letter they have, then randomly mix them up inside, order doesn't matter :)
          • It took me 10 minutes to figure out "ioiretnr" :-/
            Presumably this was after you had already figured out "reversing" and still drew a blank.
    • Read the website. (Oh wait, this is /., nobody does that).

      A system that understands the text it is compressing will compress better than one that doesn't.

      The winner improved upon previous compression programs by adding semantic modelling. Improving the modeling further would improve the results. You're heading towards language understanding.

    • Re:Compression related to acting intelligently? (Score:5, Interesting)

      by adrianmonk (890071) on Monday October 30 2006, @01:58AM (#16639191)
      How does a computer algorithm for compression relate to the idea that human compression of knowledge corresponds to intelligent action? I think the summary is making a mistake in terminology. An intelligent person is able to compress information and access it quickly, but that doesn't really have much to do with a more efficient compression algorithm, unless we're talking some seriously advanced AI. I just really don't understand the correlation or what the summary is trying to imply...

      Nope, I had heard about the contest before seeing it today on Slashdot. The summary is fine. That is in fact the thesis that the contest is designed to investigate.

      As for why this is the case, I spent some time studying compression two or three years ago, and one of the things that you quickly realize is that there is no such thing as a truly general-purpose compression algorithm. Compression algorithms work on the principle that there is some underlying pattern or structure to your data. Once the structure is understood, the data can be transformed into a smaller format. Think of compressed files as a set of parameters to a magic function which generates a larger file. The real art is in finding the function.

      To give a concrete example, one of the simplest forms of compression is Huffman coding. You analyze your stream of symbols, and you realize that some occur more often than others. You then assign shorter bit strings to more frequently-occurring symbols and longer ones to less frequent symbols. This gives you a net gain. You were able to do this because you had the insight that in human language, some letters (like "e") occur more frequently than others (like "q").

      There are, of course, other patterns that can be exploited. You can take the frequency distribution trick above up to another level by noting that the frequency of a symbol is not really independent of the symbol before it. For example, the most likely symbol after a "q" is "u". Sure, you could have other things. But "u" is the most likely. You can exploit that to get better compression.

      But of course, you might be compressing something other than English text. There are different techniques for whatever kind of data you're trying to compress. A row of pixels in a faxed (1-bit) image tends to be very close to the same as the previous row. Each pixel is a bit. If you represent a row of pixels not as on or off directly but instead represent it as its bit value XORed with the pixel above it, you end up with 0 bits for every pixel that hasn't changed and 1 bits for every value that hasn't. Presto, you have just managed to skew the probability distribution radically towards 0 bits, and you can use further tricks to gain compression from that.

      The point of all this is that to come up with these tricks, you have to understand something about the data. One of the better definitions I've ever heard for data compression was simply "applied modeling".

      Given that, you have to ask a question: have we reached the point today where compression algorithms are as good as they're going to get at compressing English text based on its surface-level characteristics such as character frequencies and repeated strings? Have we exhausted the low-level modeling that is possible? There has been a lot of work on this, so it's possible that we may have. And if so, then any further gains in the compression ratio could very well be the result of some sort of higher-level modeling. Maybe even modeling the knowledge rather than just the language. And that is what this contest is about, as I understand it.

      It's not for sure that a winning contest entry necessarily requires the submitter to have developed some kind of machine intelligence. But it's an intriguing enough idea that it might be worthwhile to run the contest just to see if something interesting does happen.

      By the way, for some interesting reading on this subject, look up Kolmogorov Complexity. The wikipedia seems to have a pretty decent article [wikipedia.org] on it (although I haven't read the whole thing).

    • They were certainly not, and they are right.

      The contest produces a hard, verifiable result with a hard restriction on resources that you can use to attain it.

      If you look at the state of AI research, then you will understand that introducing some cold hard numbers wont hurt.

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.