Digamos:
aé um arquivo de 256 MB contendo bytes aleatóriosbé o mesmo arquivo exceto que tem um byte inicial adicional0
Graças a esta resposta , descobri que rsyncé capaz de calcular um "patch binário diff" entre esses dois arquivos:
rsync --only-write-batch=patch b a
Neste exemplo, o patcharquivo tem... apenas 65 KB, então é muito bom.
Em suma, como rsyncdetectar tão poucos byes foram alterados? Inicialmente pensei que iria comparar:
- a[0:k] e b[0:k]
- a[k+1:2k] e b[k+1:2k]
- a[2k+1:3k] e b[2k+1:3k]
- ...
- a[Nk:N] e b[Nk:N]
para vários valores de k, por exemplo, a maior potência de 2 possível (2^j), então se não houver correspondência, 2^(j-1), então 2^(j-2), etc.
Mas para esses arquivos ae b, ele falharia totalmente porque, como bé apenas adeslocado de um byte, não haveria pedaços semelhantes! Então esperaríamos patchque fosse... 256 MB.
Mas aqui funciona de uma maneira mais inteligente, como o algoritmo funcionou neste exemplo simples b= um byte concatenado com o conteúdo de a?
Talvez alguém que saiba isso melhor possa postar outra resposta, mas após mais pesquisas, a chave no algoritmo rsync parece ser detalhada no parágrafo "Determinando quais partes de um arquivo foram alteradas" : Rolling hash .
Outra leitura útil: https://moinakg.wordpress.com/tag/rolling-hash/
contra:
Outro recurso útil: http://tutorials.jenkov.com/rsync/overview.html