# Compression technique exploiting common similarities

I asked this on StackOverflow, but it was determined more appropriate to post here.

So it goes like this..

For people concerned about users having slow connections and timeout issues, it is known that it can't be just always solved with minification, latency reduction etc..

I'll try to keep this question as short as possible, however retaining clarity where possible.

I've thought about a technique to further reduce uncompressable files (like mp3 and mp4), bear with me please.

What if we could skip chunks/bits/frames of a file being similar and rebuild them locally? Ok, let's explain it with a short example.

Assume you have many files in your computer, and that 3 of them are videos with a knife and a guy with blue eyes non-evenly spread over many frames. You go to this site and there's a post.. this post features a video of a serial killer's life. It is totally unrelated to the videos you have on your pc, except for the killer's knife, and the victim he kills having blue eyes.

What we could do here, is, remotely and locally make the videos (in this case) have "metadata blocks" about the most frequent frames and do a bidirectional check. If the two happen to have the same/similar blocks, the remote server just sends the new blocks, and, we rebuild the missing ones locally.

Like this:

Remote file =
MetadataBlock:
knife:
from (minute 3.12) to (minute 3.59)
and from (minute 4.40) to (minute 5.20)
blue eyes:
from (minute 0.06) to (minute 0.60)
and from (minute 1.20) to (minute 1.30)
and from (minute 6.50) to (minute 6.58)

Local file =
MetadataBlock:
knife:
from (minute 8.00) to (minute 8.20)
and from (minute 40.00) to (minute 40.02)
and from (minute 42.00) to (minute 42.50)
blue eyes:
from (minute 3.05) to (minute 3.15)
and from (minute 6.08) to (minute 7.40)

Local file.knife.total = 1.12 minutes

Local file.blue_eyes.total = 1.42 minutes

FileTotal = Local file.knife.total + Local file.blue_eyes.total

FileTotal (2.54) * 3 / 1.5 = 5.08 minutes


Remote server remove the blue eyes and knife bits/frames, appending instructions to build them locally from MetadataBlock.

As soon as the file is received, the os reads the instructions and execute them like:

"Replace MetadataBlock(from(knife.minutes)) with local file 1 MetadataBlock(from(knife.minutes))"

, the same goes for other metadata blocks such as blue eyes, black hair, shirt color etc..

Is a technique like, or similar to this feasible, or just pure utopia?

## 1 Answer

Of course it is possible.
For example, you could define the trailer of a movie as the sequence of movie sequences it shows plus the trailer-specific overhead it uses. If the movie itself is at hand when you want to watch the trailer, then everything goes well.

Yet in general...either you would have to add tons of metadata to each file (e.g. "contains sequences in which blue-eyed guy fiddles around with a knife"), thus increasing all files significantly, or you would have to run some pattern-matching algorithms over all your movie database. And your file will be very context-dependent, i.e. if one of the files you rely on changes, then all hell breaks loose. That does not sound practical to me.

Note that most lossless compression techniques also share patterns that appear across different files. So if you gzip a set of very similar mp3s, then some notable compression should happen.