How Stanford Engineers Created a Fictitious Compression For HBO 90
Tekla Perry (3034735) writes Professor Tsachy Weissman and Ph.D student Vinith Misra came up with (almost) believable compression algorithms for HBO's Silicon Valley. Some constraints -- they had to seem plausible, look good when illustrated on a whiteboard, and work with the punchline, "middle out." Next season the engineers may encourage producers to tackle the challenge of local decodability.
Stanford as a buzzword factory (Score:4, Funny)
Now they can admit it.
Re: (Score:2)
Re: The cast (Score:1)
I concur, the directors don't extract the essence or haven't coached the actors to make it believeable enough to make it funny. Like I once worked with an RF guru from Quebec who instead of putting serial numbers on each aluminum casting he designed/tested for a CATV WAN to the curb with T1 in be 80's put names of a different girlfriend in his life for each Pole mounted unit.
Another who knew how to tweak another 0.1 less loss in a microwave 3.4dB splitter and also how to transmit a burst that coul
Meh (Score:4, Insightful)
Anyone who knows anything about compression knows that universal lossless compression is impossible to always do, because if such an algorithm existed, you could run it repeatedly on a data source until you were down to a single bit. And uncompresing a single bit that could be literally anything is problematic.
I sort of wish they'd picked some other sort of woo.
Re:Meh (Score:4)
I don't think they mean univeral that way, I believe they mean universal lossless compression as gzip, bzip2 or 7zip. They will work on almost any data, but not all kinds of data. The idea here is that the show has a new way to do this that is supposed to be even better. The method they use remind me though of FLAC.
Regarding compression (Score:1)
Some 20 years ago when there were some choices of compression software I remember I ran some tests - and found that a utility called "Winace" is the only compression utility that produces a smaller compressed file than the original if compressing .avi, .mov, and .jpg files
All the rest produced larger "compressed" files than the original
Recompress the coefficients (Score:3)
JPEG is a lossy compression and it's impossible for an archiving utility using a lossless compression to best that.
Of course it's possible. JPEG encoding has three steps: cosine transform of each block (DCT), then quantization (where the loss happens), then coding. In JPEG, the coding involves a zig-zag order and a Huffman/RLE structure, and this isn't necessarily optimal. A lossless compressor specially tuned for JPEG files could decode the quantized coefficients and losslessly encode them in a more efficient manner, producing a file that saves a few percent compared to the equivalent JPEG bitstream. Then on decompress
Mod parent up - applicable to gzip/deflate (Score:1)
Sometimes you don't even need to change the file format - optimization can be applied to already compressed gzip/deflate files (which PNG uses) which can be used to create a more optimal deflate/gzip file. See tools like DeflOpt [encode.ru] and defluff [encode.ru] (DeflOpt can sometimes make even zopfli encoded files smaller [google.com]).
JPEG recompression (Score:2)
ACT has a JPEG recompression test [compression.ca] which clearly shows a bunch of compressors making a JPEG smaller. Even better - there's a great paper by the author of packJPG talking about how to compress a JPEG losslessly [htw-aalen.de] using the technique teppples described...
Re: (Score:2)
Of course it's possible. JPEG encoding has three steps: cosine transform of each block (DCT), then quantization (where the loss happens), then coding. In JPEG, the coding involves a zig-zag order and a Huffman/RLE structure, and this isn't necessarily optimal. A lossless compressor specially tuned for JPEG files could decode the quantized coefficients and losslessly encode them in a more efficient manner, producing a file that saves a few percent compared to the equivalent JPEG bitstream. Then on decompression, it would decode these coefficients and reencode them back into a JPEG file.
I believe what they meant was that you would not be able to apply a lossless algorithm to the original data stream and achieve greater compression than applying a lossy algorithm. Your composite algorithm is just a more efficient lossy algorithm.
If we look at the original statement from an information theoretic point of view, the GP's statement should be easily understood. With a lossless algorithm, you have to encode all of the original information and restore it. Assuming an optimal encoding, it will
Re: (Score:2, Interesting)
I haven't seen the show, but I have experience in dinking around with lossless compression, and suffice it to say, the problem would be solved if time travel existed, because then we could compress data that doesn't yet exist.
Basically to do lossless, you have to compress data linearly. You can't compress the chunk of data it will get to in 10 seconds now on another core, because the precursor symbols do not yet exist. Now there is one way around this, but it's even more horribly inefficient, and that is by
Re: (Score:2)
The method they use remind me though of FLAC.
FLAC is actually in the first episode for a few seconds; it was the baseline they were comparing against.
Re: (Score:2)
Exactly. The first step in ANY compression algorithm is:
Know Thy Data
Your mention of FLAC is a perfect example.
Re:Meh (Score:5, Funny)
"you could run it repeatedly on a data source until you were down to a single bit."
That's why you need two distinct compression algorithms. Sometimes one will work better, sometimes the other. While repeatedly compressing, don't forget to write down in which sequence you need to apply the decompression. I believe this can compress abitrary data down to zero bits, if you are patient enough.
Re: (Score:2, Funny)
You do the same thing you did the first time: two algorithms, write down the order. ;)
Re: (Score:2)
I'm not sure you understand. Prepending the order to the compressed data would still increase the length of some files.
(In before whoosh.)
Re: (Score:2)
Re:Meh (Score:4, Funny)
Metadata? You just let the NSA store it for you.
Re:Meh (Score:4, Funny)
While repeatedly compressing, don't forget to write down in which sequence you need to apply the decompression.
Pretty much. I've found that I can do this. Essentially for N bits, I've got a large family (2^N) of compression algorithms. I pick the best one and write down it's number. The resulting data is 0 bits long, but there's a little metadata to store.
Re: (Score:3)
Meh. You only need the basic rules of physics to compute the universe from scratch, including all possible movies.
Re: (Score:2)
are probabilistic
I'm sorry, but that can't be right. If we relied on probability, even in an infinite universe we'd never see the likes of Mariah Carey's "Glitter".
Re: (Score:2)
physics is a manmade endeavor, the "laws of physics" are inventions of man. Reality may work another way, not according to any model that man's mind could devise.
Re: Meh (Score:3)
You mean 1 (you forgot the parity bit).
Re: (Score:3)
> if such an algorithm existed, you could run it repeatedly on a data source until you were down to a single bit.
Ah, but you are not describing universal lossless compression but universal lossless compression with a guaranteed compression ratio of better than 1:1.
That indeed isn't possible but I can't see it claimed in TFA.
Re: (Score:2)
It may not have been claimed in the article, but it was claimed on the show itself.
Re:Meh (Score:4, Interesting)
Re:Meh (Score:5, Insightful)
Though technically true, in fairness we need to differentiate between meaningful data and noise. Yes, a universal compressor doesn't care. Human users of compression algorithms, for the most part, do care.
So the limit of useful compression (Shannon aside) comes down to how well we can model the data. As a simple example, I can give you two 64 bit floats as parameters to a quadratic iterator, and you can fill your latest 6TB HDD with conventionally "incompressible" data as the output. If, however, you know the right model, you can recreate that data with a mere 16 bytes of input. Now extend that to more complex functions - Our entire understanding of "random" means nothing more than "more complex than we know how to model". As another example, the delay between decays in a sample of radioactive material - We currently consider that "random", but someday may discover that god doesn't play dice with the universe, and an entirely deterministic process underlies every blip on the ol' Geiger counter.
So while I agree with you technically, for the purposes of a TV show? Lighten up.
Re: (Score:2)
Or if you're into math, you invoke the pigeonhole principle So the limit of useful compression (Shannon aside) comes down to how well we can model the data. As a simple example, I can give you two 64 bit floats as parameters to a quadratic iterator, and you can fill your latest 6TB HDD with conventionally "incompressible" data as the output. If, however, you know the right model, you can recreate that data with a mere 16 bytes of input. Now extend that to more complex functions - Our entire understanding of "random" means nothing more than "more complex than we know how to model". As another example, the delay between decays in a sample of radioactive material - We currently consider that "random", but someday may discover that god doesn't play dice with the universe, and an entirely deterministic process underlies every blip on the ol' Geiger counter.
IOW, Kolmogorov complexity [wikipedia.org]. For example, tracker and MIDI files are a great way to "compress" music, as they contain the actual notation/composition rather than the resulting sound. Of course, that doesn't account for all the redundancy in instruments/samples.
So while I agree with you technically, for the purposes of a TV show? Lighten up. :)
IMHO, half the fun of such TV shows is exactly in discussions like this -- what it got right, where it went wrong, how could we use the ideas in some real-world innovation. I find that deeper understanding only makes me enjoy things more, not less, an
Re: (Score:2)
Re: (Score:3)
16 bytes plus the model.
Re: (Score:2)
Re: (Score:2)
Anyone who knows anything about compression knows that universal lossless compression is impossible to always do, because if such an algorithm existed, you could run it repeatedly on a data source until you were down to a single bit. And uncompresing a single bit that could be literally anything is problematic.
Actually, anyone who knows anything about compression knows that universal lossless compression is always possible to do. Sometimes you get good compression, sometimes you get shitty compression, and sometimes you get 0% compression. Note that 0% compression is still compression — it's just a degenerate case.
You are right, of course, that you can't repeatedly compress something down to a single bit — there is always a point of diminishing returns. But just because you can't compress something do
Shannon's source coding theorem (Score:3)
Re: (Score:2)
1
Apparently the /. crapfilter doesn't like my compressed comment.
Re: (Score:2)
Troll? Joke? Fundamental mis-understanding regarding the nature of information?
Insufficient information to tell.
Re: (Score:3, Interesting)
Professional Engineer here (Score:1)
I am a PE in California..
one can do engineering in California without a license under the "industrial exemption", and even be called an engineer on your business card.
What you can't do is hang up a shingle and run your own business as Joe Bloggs, Engineer, unless you have a license.
A lot of companies have an HR policy that to be an "engineer" requires a 4 year degree, otherwise you are a "technician". To a certain extent, this is a "exempt" vs "non-exempt" (overtime) distinction. Engineers are exempt from
Re: (Score:2)
What you can't do is hang up a shingle and run your own business as Joe Bloggs, Engineer, unless you have a license.
true but I've seen non-licensed people who call themelves consulting engineers instead of consultants. Though many of these people use "engineer" but whaddaya gonna do, place them under citizen's arrest? However, civil engineers are very strict on licensing unlike vast number of silicon valley engineers.
Engineers are exempt from overtime because they are "professional" (having conducted a course of advanced study), Technicians are not.
reminds me of Dilbert cartoon where he is working lot of unpaid overtime where the hardhat maintenance technician either gets to go home at end of day or gets 1.5 or 2 times normal wage.
Re: (Score:2)
I don't think that's true. Fully 50% of Silicon Valley job postings are for "XXX Engineer" and most of those are programming positions.
You want believability? (Score:1)
Re: (Score:2)
Re: (Score:2)
Future troubles (Score:2)
Now let's just hope that no aliens listening in to our broadcasting and no far future humans actually believe this and try to recreate the "groundbreaking compression algorithm" the whiz humans of the digital age came up with.
Re: (Score:2)
Aren't you thinking of encryption?
Pilot signal and FEC (Score:2)
He just described how MPEG works (sort of) (Score:1)
He came up with the idea of using lossy compression techniques to compress the original file, then calculating the difference between the approximate reconstruction and the original file and compressing that data; by combining the two pieces, you have a lossless compressor.
This type of approach can work, Misra said, but, in most cases, would not be more efficient than a standard lossless compression algorithm, because coding the error usually isn’t any easier than coding the data.
Well, this is almost how MPEG movie compresion works - and it really does work! MPEG works by partly describing the next picture from the previous using motion vectors. These vectors described how the next picture will look based on movements of small-ish macroblocks on the original picture. Now, if that was the only element of the algorithm movies would look kind of strange (like paper-doll characters being moved about)! So the secret to make it work is to send extra information allowing the client to calc
Re: (Score:1)