information
Compress without knowing the source
It is 1977, and a maddening gap sits between theory and practice: the entropy bound tells you how few bits a source needs only if you already know its statistics — and in the real world of arbitrary files, you never do. Build a compressor that needs no model handed to it, that learns the structure of the data as it reads, and provably approaches the true entropy rate for any stationary source without being told what that source is. The method must be one pass, adaptive, and simple enough for modest hardware. Get it wrong and compression stays a bespoke craft, a different scheme for text and images and code — instead, this universal idea becomes the engine inside nearly every general-purpose compressor the world uses.
Who this problem belongs to
The two figures whose methods fit it best, out of 32 in contention.
Shannon's 1948 information theory established the entropy rate as the fundamental limit on compression for any source, and it was his own 1948 and 1951 papers that first posed the gap this problem exploits: entropy tells you the limit only if you know the source's statistics, and in practice you never do. His rigorous formalization of what a source, a code, and an entropy rate even mean is the entire conceptual foundation the 1977 universal compression construction operationalizes and proves achievable. He did not build the specific adaptive, dictionary-based Lempel-Ziv algorithm himself, that belonging to Abraham Lempel and Jacob Ziv's later work, but every concept the problem's proof depends on is his invention.
Kolmogorov's algorithmic information theory, developed around 1965, defines the complexity of a string as the length of the shortest program producing it, and this notion of universal, model-free descriptive complexity is the deep theoretical foundation universal compression realizes practically: a compressor that needs no prior model and adapts to any source is approximating exactly the Kolmogorov-complexity ideal within computational limits. His broader program of putting information and randomness on rigorous mathematical footing gave the field precisely the conceptual apparatus this 1977 problem requires and anticipates. He did not build the specific one-pass, adaptive Lempel-Ziv construction himself, but its entire theoretical justification rests on ideas substantially his. He remains the deep theoretical justification behind this result rather than the author of its concrete algorithm.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
32 figures are scored on this problem. Draw it in a battle to see where you land.