Re: Is Diff/Delta Cache Digest Implemented ?

Alex Rousskov wrote:

> Make sure you read "Subject: Cache Digest Diffs" and related threads
> on squid-dev mailing list! A few diff-ing algorithms have been
> discussed and compared there.

And I still haven't made up my mind on which is the best one. It varies
too much depending on the amount of data in the diff. Different
algorithms are best at different scales of the diff density spectrum. I
suspect a combination of different algorithms will be needed for
efficient transfers. It is not very easy to do efficient lossless
compression of random information.

My algorithm with huffman encoding of bit change distances works quite
well at some ranges, the simple "changed bytes" approach made by Alex
works better at some ranges. By using a pre-calculated huffman tree the
bit change distance approach can operate in a slightly wider range with
a reduction in space efficiency at the best ranges..

--
Henrik Nordstrom
Squid Hacker