Data.ByteString.Delta

Binary diff/patch for ByteStrings.

The diff function takes two ByteStrings, and produces a "patch" that can later be applied with the patch function to the first string to produce the second string. It exploits common subsequences between the two strings, and can be used to save bandwidth and disk space when many strings differing by a small number of bytes need to be transmitted or stored.

Deltas produced by this version of the library can be applied using current or future versions, but may not be compatible with past versions.

bytestring-delta implements the algorithm described in An O(ND) Difference Algorithm and Its Variations by Eugene W. Myers. Because its memory usage and expected running time are O(N + D^2), it works well only when the strings differ by a small number of bytes. This implementation stops trying when the strings differ by more than 1000 bytes, and falls back to producing a patch that simply emits the new string.

Thus, bytestring-delta does not save any space when given two strings that differ by more than 1000 bytes. This may be improved in a future version of the library.

Documentation

diff :: ByteString -> ByteString -> ByteString

Compute a delta between two ByteStrings.

 patch old (diff old new) == Right new

patch :: ByteString -> ByteString -> Either String ByteString

Apply a delta produced by diff.

If the patch cannot be applied, this function returns Left errmsg, where errmsg is a string describing the error.