I have trimmed down the memory usable a little but, but not
reduce the space complexity. (Reduced by 80 % on
32-bit machines, and 88.(8) % on 64-bit machines, as
the supreium.)
If I understood that algorithm correct, I do not think it
will produce the optimal result (I have not look in to it
tough.) But it would its time complexity would be favourable
for ridiculously large files.
Some UNIX-like systems have bdiff, comparing really large
files. Perhaps sbase should have diff using the algorithm
based on the Wagner–Fischer algorithm for optimal result,
and bdiff using the algorithm you described for optimal
complexities.
Received on Thu Jan 28 2016 - 18:12:47 CET