Patch/delta compression?

[cbloom]

What's the state of the art in patch/delta compression?

eg. you sent a large (100M-1G) archive previously, and you wish to update a few parts of that. You can use the previous archive as context for the patch compression.


Back in the day, most of the serious command line compressors had the option to precondition their model (eg. ACB, Rkive, PPMZ) but I just tried searching a bit and I don't see it as an option on any of the modern/mainstream things I checked (RAR, FreeArc, 7z).

The most obvious way to do a patch compress is to just use a dictionary coder and preload the dictionary from the previous archive. I'm very surprised that the mainstream archivers don't seem to offer this option, maybe I'm just missing it.

Any advice?

A related question : has there been any clever work on very large window matching? Say for example I wanted to find LZ77 string matches in a 1GB window, and I'm okay with a min match len of 16 or something big like that. Is there a better way to do that? How about out-of-core string matching for files larger than memory? eg. if you have two 1 TB files that are nearly identical and you wish to compress the differences.

[Shelwien]

See http://shelwien.googlepages.com/fma-diff_v0.rar and http://freearc.org/research/SREP.aspx and http://exdupe.com/
Also http://compression.ru/ds/ppmtrain.rar

The best actual diff is probably still bsdiff.

And imho prebuilt stats won't be of much use with that amount of data.
With 100M any CM/PPM would already have to flush its stats multiple times.

Also http://encode.su/threads/1147-A-new-...ression-target

[cbloom]

srep seems like the right thing but it oddly doesn't provide any "preload dictionary" option.

bsdiff seems okay.

Ideally it should be built into an archiver, because the archiver can decompress the data to build the patch. eg. what you want to be able to do is something like :

make archive of initial distribution (dist1.arc)
send dist1.arc to user
prepare a new distribution and archive the whole thing (dist2.arc)
create a delta archive from dist1.arc -> dist2.arc = dist1_2.arc

user can either either download dist2.arc or dist1_2.arc
archiver can do dist1.arc + dist1_2.src -> dist2.arc

[Shelwien]

exdupe does just that, also fma-diff in a way.
While bsdiff tries too hard and you won't be able to diff GBs of data with it.