이 간단한 예에서 rsync는 어떻게 작동합니까?

예를 들어:

• a임의의 바이트를 포함하는 256MB 파일입니다.
• b~이다같은 파일추가 선행 바이트가 있다는 점만 제외하면0

이것 덕분에답변rsync, 다음 두 파일 사이의 "바이너리 diff 패치"를 계산하는 기능을 발견했습니다 .

rsync --only-write-batch=patch b a

이 예에서 patch파일은... 65KB에 불과하므로 꽤 좋습니다.

간단히 말해서, rsync변경된 작문이 거의 없다는 것을 어떻게 감지합니까?처음에는 다음과 비교할 것이라고 생각했습니다.

• a[0:k] 및 b[0:k]
• a[k+1:2k] 및 b[k+1:2k]
• a[2k+1:3k] 및 b[2k+1:3k]
• ...
• a[Nk:N] 및 b[Nk:N]

k의 다른 값에 대해 가능한 가장 높은 2의 거듭제곱(2^j)을 말하고, 일치하지 않으면 2^(j-1), 다음으로 2^(j-2) 등입니다.

그러나 이러한 파일 a및 의 경우 1바이트 만 이동되므로 유사한 블록이 전혀 없기 b때문에 완전히 실패합니다 ! 그렇다면 우리는 그것이 256MB가 될 것으로 예상합니다.bapatch

b하지만 여기서는 더 스마트한 방식으로 작동합니다. 이 간단한 예 (바이트가 내용과 연결됨) 에서 알고리즘은 어떻게 작동합니까 a?