算法与计算机科学patrickcraig.co.uk
5000 美元压缩挑战
The $5000 Compression Challenge
2012 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇页面记录了一场 5000 美元压缩挑战的经过：发起人 Mike Goldman 悬赏让人把文件压得更小，参赛者 Patrick 则利用规则漏洞，把文件拆成多个片段并去掉每段末尾的固定字符，解压时再拼回。双方随后围绕这算不算无损压缩、规则是否允许拆成多文件、奖金该不该支付展开争论。页面呈现的是这场关于规则、漏洞与“作弊还是创新”的经典纠纷。
为什么经久不衰：它把规则漏洞、专家傲慢和挑战赛的边界问题浓缩成一桩小公案，今天读来仍是理解“按字面规则玩游戏”与“按意图裁判”的绝佳案例。
HN 评论精选
挑战者认为发起人明知规则不可行，漏洞正是游戏的一部分，拒付并嘲讽参赛者不光彩。
我完全相信 Mike 应该把钱付给 Patrick。理由很简单：既然 Mike 设了一个他明知不可能达成的赌局（也就是说，无论如何他都不必付这 5000 美元），那么这个游戏唯一的意义就是找出漏洞。否则就只是 Mike 在猎取毫无戒心的受害者。如果你设计了一个不可能的游戏，别人唯一能做的就是攻破它。然后你再抱怨说那是作弊，那你就是个迂腐的蠢人——就像中学里那种输了赌局后想尽办法赖账的讨厌小孩。更火上浇油的是，他那些令人恼火的回复，比如“我试着运行了前两个文件，结果没成功”，让我血压升高，因为这明显是在贬低参赛者。
paulsecwhatt查看英文原文
I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it. If you then complain that THAT is cheating, you're a pedantic idiot - one of those annoying kids in middle school who loses a bet and then tries every possible way to weasel himself out. To add fuel to the fire, his obnoxious replies such as "I tried running the first two files and it didn't work", make my blood boil, as it's a clear attempt to try and belittle the contestant.
规则修改导致多文件方案可辩，但隐藏位置信息仍算作弊；发起人至少不能全对，应退款或付钱。
Mike Goldman 最初写挑战时要求的是一个文件和一个解压器。但后来被问到能否有多个文件时，他同意了；因此可以说他被套住了。他没有说“可以，但每多一个文件要罚 256 字节”，只是直接同意了。这意味着原公式仍然适用：只需把各文件大小相加。Goldman 应该承认自己草率修改原挑战并付钱。话虽如此，让归档格式或文件系统隐藏被删字节的位置信息，显然也是作弊！如果只产出一个文件，它必须包含一张表，说明把取出的字节插回哪里。如果产出多个文件，归档格式或文件系统会替你存储这些信息，代价不小。如果双方都错，应宣布比赛无效并退还 100 美元。如果只有 Goldman 错，他应付 5000 美元。无论怎么解释，都不是 Goldman 完全对、参赛者完全错。所以无论如何他都不该留着那 100 美元。
kazinator查看英文原文
Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes added together. Goldman should accept that he foolishly rushed into a careless amendment of his original challenge and pay the money. That said, it obviously is cheating to have the archive format or file system hide the representation of where the removed bytes are! If a single file is produced, it has to include a table of where to insert the bytes that were taken out. If multiple files are produced, the archive format or file system stores that information for you at considerable expense. If both people are wrong, the contest should be declared invalid and Goldman should return the $100. If only Goldman is wrong, he should pay $5000. Under no interpretation is Goldman strictly right and the contestant strictly wrong. So he is wrong to keep the $100 in any case.
该方案本质是利用 EOF 作为零成本分隔符的极端压缩技巧，介于作弊与创新之间。
引用 Mike 的话：“……你只是把文件拆成 218 个以字符‘5’结尾的部分，然后从每个部分去掉末尾那个字符。于是‘解压器’不过是个重组器，把各部分拼接起来，再在每个部分后面补回字符‘5’。”嗯，这正是无损压缩的定义。看看 js crunch 之类怎么做：建立常见序列的字典，递归地按这些序列切分文件，再反向拼接重组。Gzip、bzip2 等等都一样。按一个常见序列切分，再按它重组。Patrick 只是做了一个只深入一层的定制压缩器。通常你需要一个分隔符来分开这些块，而且该分隔符不能出现在块内，比如通过填充或转义。那会增加文件大小，于是你就麻烦了。Patrick 所做的，是把 EOF 当作一个全新的、哪里都不出现的“分隔符”，而且成本为零字节。这是作弊，还是 inventive？
nothrabannosir查看英文原文
Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common sequences, split the file on those sequences recursively and then reassemble it by joining in reverse. Gzip, bzip2, &c, &c, it's all the same thing. Split the file by a common sequence and reassemble it by that. Patrick just created a customized compressor that went only 1 level deep. Normally you'd need a delimiter to separate those chunks, a delimiter that doesn't occur in the chunks e.g. through padding or escaping. That, in turn, increases the filesize, and now you're in trouble. What Patrick did was to use EOF as a new fresh "delimiter" that doesn't occur anywhere, and at a cost of zero bytes, no less. Cheating, or inventive.
挑战带有引诱外行出丑的意味，专家应教学而非羞辱。
这个挑战的目的，是引诱那些不如 Mike 懂压缩的人跳出来，好让 Mike 嘲笑和羞辱他们。从这个角度看，我觉得它就是个陷阱。根据我的经验，设这种陷阱的人，通常在被反将一军时反应很差。世界上有些人，别人不像他们那样懂自己的专业领域，他们就觉得被冒犯。他们对天真的问题感到愤怒，想惩罚那些“白痴”。这会把一个有趣的话题搞坏，对所有人都不好。HN 文化最好的方面之一是，这里的专家更倾向于教学而不是训斥。跟 Usenet 相比，这是个不错的变化。
snowwrestler查看英文原文
The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't understand their area of expertise as well as they do. They get angry and offended at naive questions, and seek to punish the idiots. This is a great way to take an interesting subject and ruin it for everyone. One of the best aspects of the HN culture is that experts here tend to incline more toward teaching and less toward chastising. It's a nice change from Usenet.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选