Binary diff/patch for
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.
Compute a delta between two
patch old (diff old new) == Right new