How Stanford Engineers Created a Fictitious Compression For HBO

← Back to Stories (view on slashdot.org)

How Stanford Engineers Created a Fictitious Compression For HBO

Posted by timothy on Friday July 25, 2014 @07:50PM from the buzzword-bingo dept.

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.

47 of 90 comments (clear)

Min score:

Reason:

Sort:

Stanford as a buzzword factory by hax4bux · 2014-07-25 20:04 · Score: 3, Funny

Now they can admit it.
Meh by ShakaUVM · 2014-07-25 20:08 · Score: 3, 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.
1. Re:Meh by Carewolf · 2014-07-25 20:35 · Score: 3
  
  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.
2. Re:Meh by hankwang · 2014-07-25 20:56 · Score: 4, 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.
  
  --
  Avantslash: low-bandwidth mobile slashdot.
3. Re:Meh by Anonymous Coward · 2014-07-25 21:17 · Score: 2, Funny
  
  You do the same thing you did the first time: two algorithms, write down the order. ;)
4. Re:Meh by AYeomans · 2014-07-25 21:44 · Score: 3, Funny
  
  Metadata? You just let the NSA store it for you.
  
  --
  Andrew Yeomans
5. Re:Meh by StripedCow · 2014-07-25 21:57 · Score: 2
  
  Meh. You only need the basic rules of physics to compute the universe from scratch, including all possible movies.
  
  --
  If Pandora's box is destined to be opened, *I* want to be the one to open it.
6. Re:Meh by WoOS · 2014-07-25 23:16 · Score: 2
  
  > 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.
7. Re: Meh by toxcspdrmn · 2014-07-25 23:23 · Score: 2
  
  You mean 1 (you forgot the parity bit).
  
  --
  "E pur si muove!" - attributed to Galileo Galilei, 1564-1642
8. Re:Meh by serviscope_minor · 2014-07-26 00:29 · Score: 3, 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.
  
  --
  SJW n. One who posts facts.
9. Re:Meh by TeknoHog · 2014-07-26 00:49 · Score: 3, Interesting
  
  Or if you're into math, you invoke the pigeonhole principle.
  
  --
  Escher was the first MC and Giger invented the HR department.
10. Re:Meh by pla · 2014-07-26 01:23 · Score: 5, Insightful
  
  Or if you're into math, you invoke the pigeonhole principle
  
  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. :)
11. Re:Meh by tepples · 2014-07-26 01:49 · Score: 1
  
  I'm not sure you understand. Prepending the order to the compressed data would still increase the length of some files.
  (In before whoosh.)
12. Re:Meh by MightyYar · 2014-07-26 01:52 · Score: 1
  
  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".
  
  --
  W..w..W - Willy Waterloo washes Warren Wiggins who is washing Waldo Woo.
13. Re:Meh by TeknoHog · 2014-07-26 02:09 · Score: 1
  
  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. 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, and I enjoy "lightening up" my brain cells.
  
  --
  Escher was the first MC and Giger invented the HR department.
14. Re:Meh by tepples · 2014-07-26 02:18 · Score: 1
  
  The algorithm you describe is not compression, as there does not exist an input for which choice-of-algorithm metadata plus compressed data is smaller than the input data.
15. Re:Meh by Nemyst · 2014-07-26 02:44 · Score: 1
  
  If we "someday" discover that radioactive decay is not inherently random and unpredictable to an atomic level, it'd mean we suddenly contradict a hundred years of scientific research, models and theories. While not impossible, your post implies that there's a model and we just don't know it; the truth is that it's extremely unlikely to be the case.
16. Re:Meh by Anonymous Coward · 2014-07-26 02:54 · 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 compressing from each end (or in the case of HBO's codec... the middle) so instead of a single "dictionary" for the compressor to operate from, it uses two. At the end could then throw away the duplicate dictionary entries on a second pass. That's why it's inefficient. In order to split compression accross cores, you have to do some inefficient compression by duplicating efforts.
  If I have a 16 core processor and I want to compress it using all 16 cores, I'd be doing it putting each scanline of an image on a separate core, so effectively every 16 pixels, wrap around to another core. At the end of the the compression scheme, a second pass is run over the dictionary to remove duplicates. In video, this won't really exist, because video doesn't have a lot of duplication unless it's animation (eg Anime, Video games) This is why lossy compression is always used for video/still captures from CMOS/CCD cameras. That data has data that can be lost because there is inherent noise in the capture process.
  That second pass is still going to be stuck to one core.
  The ideal way to solve lossless compression problems is by not trying to make the algorithm more efficient, but by intentionally trading off efficiency for speed. So to go back to the previous example. Instead of having 1 progressive stream, you instead have 16 progressive streams divided horizontally. This will work fine for compression, but decompression will have a synchronization problem. You may have seen this when you watch h.264 videos and some parts of the I frames aren't rendered, resulting in "colorful tiles" in the missing spaces if your CPU is too slow. This is because the 16 parts of the frame won't all decompress at the same speed, because they will have different complexity. So the end result is you end up having to buffer enough for two I frames, so that you can still seek the video. At UHD resolution, this means 33554432 bytes per frame. So if you have a 120fps video, you need 4GB of RAM just to buffer 1 second. Our current technology can't even read data off a SSD this fast. The fastest you can get is 1500MB/sec and even then it costs you 4000$. Hence why we use lossy compression, so the disk can keep up.
17. Re:Meh by iggymanz · 2014-07-26 03:24 · Score: 1
  
  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.
18. Re:Meh by AmiMoJo · 2014-07-26 04:03 · Score: 2
  
  16 bytes plus the model.
  
  --
  const int one = 65536; (Silvermoon, Texture.cs)
  SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
19. Re:Meh by JeffAtl · 2014-07-26 04:23 · Score: 1
  
  It may not have been claimed in the article, but it was claimed on the show itself.
20. Re:Meh by Josh+Coalson · 2014-07-26 05:47 · Score: 1
  
  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.
  
  --
  FLAC - Free Lossless Audio Codec
21. Re:Meh by UnknownSoldier · 2014-07-26 06:17 · Score: 1
  
  Exactly. The first step in ANY compression algorithm is:
  Know Thy Data
  Your mention of FLAC is a perfect example.
22. Re:Meh by flargleblarg · 2014-07-26 06:30 · Score: 1
  
  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 down to a single bit doesn't mean that no universal lossless compression algorithm exists. For example, f(x) = x is a universal lossless compression algorithm. It's a shitty algorithm, but it is lossless and it does compress.
23. Re:Meh by Junior+J.+Junior+III · 2014-07-26 15:43 · Score: 1
  
  1
  Apparently the /. crapfilter doesn't like my compressed comment.
  
  --
  You see? You see? Your stupid minds! Stupid! Stupid!
24. Re:Meh by brantondaveperson · 2014-07-28 12:30 · Score: 1
  
  Troll? Joke? Fundamental mis-understanding regarding the nature of information?
  Insufficient information to tell.
25. Re:Meh by werepants · 2014-08-01 08:22 · Score: 1
  
  Your definition of "random" and your understanding of quantum mechanics isn't quite right, although the rest of your post was quite interesting. A thought experiment known as EPR (Einstein-Podolsky-Rosen), followed up by the Stern-Gerlach apparatus and Bell's theorem, actually proved that certain attributes of particles in no way persist between measurements, and that they "choose" outcomes based on a mechanism that is not only unknown, but proven by experiment to be non-describable by deterministic theories.
  
  I was going to spend a while typing up an explanation, but this is a very thorough discussion of all the possibilities that is much better than I could hope to do myself: http://www.scienceclarified.co...
Re:Why call them "engineers"? by Horshu · 2014-07-25 22:03 · Score: 3, Interesting

I wasn't even aware that programmers in Cali could even legally call themselves "engineers". I worked for a company out of college HQed in California, and I was told coming in that we used the term "Programmer/Analyst" because California required "engineers" to have a true engineering degree (with the requisite certifications et al)
Regarding compression by Anonymous Coward · 2014-07-25 22:28 · 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
You want believability? by stonedead · 2014-07-25 22:29 · Score: 1

Ask CSI. GUI interface using visual basic to track the killer --> http://www.youtube.com/watch?v... Seriously, the average joe that watches TV doesn't care about what algorithm is used, let alone know what an algorithm is.
1. Re:You want believability? by jones_supa · 2014-07-25 22:45 · Score: 1
  
  I disagree. We should not be dumbing down the GUIs just because some Average Joe does not get extra enjoyment from seeing a realistic one. I greatly appreciated the whiteboards showing some believable discrete cosine mathematics in Silicon Valley.
Future troubles by WoOS · 2014-07-25 23:29 · Score: 1

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.
1. Re:Future troubles by MightyYar · 2014-07-26 01:56 · Score: 1
  
  Aren't you thinking of encryption?
  
  --
  W..w..W - Willy Waterloo washes Warren Wiggins who is washing Waldo Woo.
Re:Universal? by barlevg · 2014-07-26 00:25 · Score: 1

Presumably there's a general compression algorithm that works on all data types, but Richard wrote specific optimizations for certain media types (the original goal of the project was to process music, so he probably started there).
Re:The cast by thrillseeker · 2014-07-26 01:28 · Score: 1

It doesn't have to be totally accurate - only humorous to a sufficiently large audience.
Recompress the coefficients by tepples · 2014-07-26 01:47 · Score: 2

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 decompression, it would decode these coefficients and reencode them back into a JPEG file.
1. Re:Recompress the coefficients by Fnord666 · 2014-07-26 12:04 · Score: 1
  
  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 still take a minimum number of bits to fully realize all of the original data on decompression. With a lossy encoding scheme, I can reduce the number of bits in the original stream before using the same optimal encoding. With fewer bits to represent it should be obvious that the encoded bitstream will always be smaller.
  
  --
  'The tyrant will always find pretext for his tyranny.' - Aesop's Fables
Pilot signal and FEC by tepples · 2014-07-26 02:02 · Score: 1

Any digital broadcast will include two things that are recognizable as a broadcast. One is a pilot signal, used to communicate the existence of a signal to the receiver. Another is forward error correction, used to reconstruct a signal partially obscured by noise. Analog television included both: the pilot signal was the sync pulses during horizontal and vertical blanking, and the error correction was the presence of a double sideband in the bottom 1 MHz of the video.
Professional Engineer here by Anonymous Coward · 2014-07-26 02:06 · 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 overtime because they are "professional" (having conducted a course of advanced study), Technicians are not.
Tecently, most places treat "fresh out of college" engineers as non-exempt (e.g. get overtime), because the Dept of Labor is looking at other factors: independent work, etc. and the "bar" for advanced study has moved up. Back when the Fair Labor Standards Act was written, a high school diploma and some on the job work was "advanced study".
1. Re:Professional Engineer here by k6mfw · 2014-07-26 02:37 · Score: 1
  
  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.
  
  --
  mfwright@batnet.com
Mod parent up - applicable to gzip/deflate by Sits · 2014-07-26 06:28 · 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 and defluff (DeflOpt can sometimes make even zopfli encoded files smaller).
JPEG recompression by Sits · 2014-07-26 08:08 · Score: 2

ACT has a JPEG recompression test 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 using the technique teppples described...
He just described how MPEG works (sort of) by paradigm82 · 2014-07-26 09:30 · 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 calculate the final picture. This is done by subracted the predicted picture from the actual next frame. This difference-picture will (if the difference between the two frames was indeed mostly due to movement) be mostly black but it will contain some information due to noise, things that have become visible due to the movement, rotation etc. So MPEG also contains an algorithm that can very efficiently encode this "difference picture". Basically an algorithm that is very efficient for encoding an almost black picture.

So there you have it - MPEG works by applying a very crude, lossy compression (only describing the picture difference in terms of motion vectors) and in addition transmitting the information required to correct the errors and allow reconstruction of the actual frame.

The only part where the comparison breaks down is that MPEG is not lossless. Even when transmitting the difference picture, further compression and reduction takes place (depending on bandwidth) so that the actual frame can not be reconstructed 100%. Still MPEG is evidence that the basic principle of using a crude lossy compressor combined with sending a compensation, works.
1. Re:He just described how MPEG works (sort of) by paradigm82 · 2014-07-27 01:25 · Score: 1
  
  I don't think any of what you wrote goes against what I wrote. I have the exact same distinction that some components of MPEG movie compression (and my post applies to MPEG-2 also btw) are lossy, that is compensated for by other steps, but other steps yet again makes it lossy.
Shannon's source coding theorem by eyebits · 2014-07-26 10:47 · Score: 2

http://en.wikipedia.org/wiki/S... "In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy."
Re:Why call them "engineers"? by Quirkz · 2014-07-28 02:52 · Score: 1

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.

--
The Quirkz Handbook of Self-Improvement for People Who Are Already Pretty Okay
Re: The cast by Anonymous Coward · 2014-07-28 06:32 · 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 could burn out the front end of any cop radar in range of ticketing him, who was also a potato farmer and expert in Celtic and Scottish history in Canada.
Another who would never violate his religious rules of working overtime past sunset or weekends yet could design a fully automated self test on a motherboard in a few days and have it work, 1st time, but was studying to be a Rabbi.
Another software manager who was so humble at managing a 100 tasks with 20 developers and then at lunch would make me a graphical analysis data entry program before excel, Multiplan and Visicalc were even invented, but some of staff woud play tricks on his boss, who forced him to accept super aggresive schedules, like drilling a hole in his often closed door. .
Or a couple guys were forced to ship product before it was ready, so the Texan boss coud send an invoice early and get paid immediately, then redirect the shipment back to finish it and then sometimes issue rubber paycheques, so the guys would play golf , putting in his office until he paid them.