Zip It! - Finding File Similarity Using Compression Utilities - Computerphile

Key Takeaways

All right. So, I want to tell you about one of my one of my favorite little computer science thingies. Uh, so the question is suppose you want to find the phoggenetic tree uh of a bunch of different types of animals and or different plants given their genomes and all you have is file compression utilities. All right. So, what's a file compression utility? So, you might be familiar with zip files. Um, like zip is the classic file compression utility. So zip files are lossless compression by which I mean when you unzip you get exactly the same file that you had on the way in. So this is in in contrast to for example JPEG which is a lossy compression format where the JPEG file it looks pretty good but it's lost a lot of data and it's not going to look exactly the same as the original. To use a demonstration this is a flower picture that I took and this picture on the right has had the chronence components down sampled by a factor of 10 in both directions. There's 100 times less color in this picture than there is in this one. But for zip files because they're trying to be completely generic, you can't just throw away data. And basically what zip does is it gives us this function C which takes a bunch of content in a file and you know maps that into a into a bunch of bitst string you know a compressed form. And how does it do this? Uh well what it does is it looks for repeated patterns in this bit sequence. it uses a pointer and in that composite pointer it points back to where the phrase first occurred >> and then when it sees repeated patterns uh instead of having to write it out again it can just write a reference to the previous place where it had that pattern and say oh yeah we do that part again. So there's a lot of compression algorithms with a lot of them end up being very complicated because it's very important to have good compression algorithms. But you can basically you can sort of use uh the length of a compressed file as a measure of the complexity of the file. So if a file is really long but most of it is just repetitive uh its compressed form is going to be very short. So the ratio between the length of the compressed file and the original file is telling you something about how complicated the file is. So here's a second thing we can do. If I have two files X and Y, for example, the human genome and the chimpanzeee genome, one thing we can do is we could consider uh the length of compress X uh and the length of compress Y. So this is saying we take the human genome and compress it and take its length and add that to the length of the compressed chimp genome and that's going to give us some length. Now here's something else we can do. If we can consider the length of the compression of the human genome plus the chimp genome. So when I say plus on genomes I just mean literally you concatenate the text files like you have a text file on your computer containing the human genome and a text file on your computer containing the chimpanzeee genome and you just copy paste one into the end of the other and now you have a new text file and you can compress it and see what its length is. So here's the idea. Suppose an x and y were literally the same. the length of the compression of x + y is going to be almost the same as the length of the compression of just x because when you get to the second file, you're just going to write down like and then do all of that again. >> Yes. >> Uh and if x and y are completely unrelated, then there's going to be no reduction. C of x plus y is going to have the same length as these these two different compressed files compressed separately. Mhm. >> So you can use this idea to basically get a metric of similarity on arbitrary data uh just by compressing concatenated versions of the files and comparing that to the length if you compress them separately. And this is just an extremely generic method. You can do it to a bunch of different things. This here is a phoggenetic tree of how CO compares to a bunch of different virus variants. I have uh some different methods of applying this to different kinds of animals and you can basically see the evolutionary history of all these animals just using the off-the-shelf compression algorithms. When I did this um when I was in college, I think I just used whatever compression algorithm was on the Linux machine I was using. It it it just works like pretty reliably. Another thing you can do suppose you want to know uh you know languages come in families and languages have these family trees. So one thing you can do is just take the UN declaration of human rights which has been translated to many different languages and take all the ones that use you know um the western alphabet the Roman alphabet uh and just apply this method directly uh and you get a not perfect but pretty reasonable depiction of the the history of all these languages. So I just think this is a super cute method in practice. I don't think this is very important for anything because if you actually care about any domain you might as well write a better similarity metric than gzipping them. But it's uh it's fun that it is so general and and works reasonably well. A partition like this. Four bits here, 12 bits here. 2 to the^ 12 is 4,096. Note to those of you that keep writing in on comments saying, "Hey, professor, what should I do? I'm just So if we look at B, we've already been to S, so we ignore it. We can go to D.