关于增量传输算法的问题
我e文不是很好，所以看不太明白原文，那位能告诉我这个算法到底是怎么回事！
原文地址如下：http://samba.anu.edu.au/rsync/tech_report/
[解决办法]
呵呵，大致看了一下，不算高明。和我这个回帖里想的办法差不多：
http://community.csdn.net/Expert/topic/5346/5346719.xml?temp=.1825373
都是为了解决低速网络上备份文件问题；采用的办法也基本相同。
区别就是：
1、他能保证备份文件完全等同于待备份文件，而我的算法备份文件只能由自己的程序读；
不过，他似乎没有考虑到，在文件中间改写一些数据的话，或者必须由对端启动一个客户端负责改写；或者只能用我那个“续写到文件尾”的方法。
否则的话，文件改写点往后的一切内容，还是必须通过网络传输。
毕竟，没有任何系统给你提供“在文件中间某点插入数据”的接口；所以最终必须像数组插入一样，拷贝并移动插入点后面的所有数据——远端访问的话，这会造成双倍的网络流量！
同样，他计算远端B文件的做法，如果不使用远端代理程序的话，仍然会导致B的内容被完全通过网络传输过来！（这部分内容原本是不需要传来的）
当然，我的想法如果实现不当，也会有类似上面一段的问题。但只要设计备份文件格式者有一定的经验，就完全可以避免多余数据的传输（比如，只要在文件头指示每个域的开始点）；而他的算法必须要求远端起动一个服务程序。
当然，从后面可见，他是在linux下做的，可以利用系统已有的各种工具。在linux众多小工具的支持下，或许可以绕过这个问题（但我没有看到通过实际网络传输的结果报告；仅从前面他的论述看来，情况不妙）。
2、搜索正确块的算法，他用的是生成速度快且短小的32位循环校验码，而我用的办法是直接搜索每块开头的若干个字符（如前8个字符）。
相比之下，我的算法搜索速度更快，但查找块时误识别率可能稍高；他的算法搜索速度要慢得多；并且使用了hash，内存占用也大。
但，由于无论如何，搜索到“疑似”数据块后，都要计算该块的MD5。所以，极端情况下（比如，文件内容总是若干字节的重复），我的算法会比他的慢；但可以少传一些东西（这就是我所谓的“压缩”）。
（最终计算效率，对普通文本文档，我估计是自己算法的要快得多；一般的二进制文件，由于里面经常会被填充大量00H或FFH的原因，可能对我的搜索算法会更多一些影响。但由于不用反复计算32位校验码，性能还是会高一些。）
另外，他把每块的32位校验码通过hash去查找正确块的想法不错。可惜被逐个计算每S字节内容的校验码这个算法给拖累了。（似乎也没法移植到我的想法上？）
----------------
Once has received the list of checksums of the blocks of B, it must search A for any blocks at any offset that match the checksum of some block of B. The basic strategy is to compute the 32-bit rolling checksum for a block of length S starting at each byte of A in turn, and for each checksum, search the list for a match. To do this our implementation uses a simple 3 level searching scheme.
就是这个算法……把他的搜索速度XX了~~~~
-------------------------------
这个东西应该是澳大利亚国立大学一个学生的论文吧？学生时代能写出这样的东西，很不错了。
尤其是测试数据极其详尽，更值得肯定（不过，貌似没有看到网络传输试验结果啊？）
