# US 9,882,768 B1 · Methods and apparatus for file synchronization over a computer network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,882,768 B1 - Document ID: US9882768B1 - Status: Granted - Kind: B1 - Application number: 13/419,271 - Filed: 2012-03-13 - Granted: 2018-01-30 - Earliest claimed: 2012-03-13 - Assignees: Trend Micro Incorporated - Applicants: Jian-Ying Chen; Liwei Ren - Inventors: Jian-Ying Chen; Liwei Ren - Web page: https://patentgrep.com/patent/US9882768B1 ## CPC - H04L 67/06: specially adapted for file transfer, e.g. file transfer protocol [FTP] - H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A system includes a sender computer and a recipient computer. The sender computer starts the chunking process by splitting a target file into chunks and providing signatures of the chunks of the target file to the recipient computer. After and in response to receiving the signatures of the chunks of the target file, the recipient computer splits the reference file into chunks, generates signatures of the chunks of the reference file, and identifies chunks that are common between the target file and the reference file. The recipient computer combines adjacent common chunks into larger chunks and creates, for example, MD5 signatures accordingly. The sender computer receives from the recipient computer information on chunks common between the target file and the reference file and provides a sequence of edit operations to the recipient computer to allow the recipient computer to reconstruct the target file. ## Claims ### Claim 1 A method comprising: a sender computer splitting a target file into a plurality of chunks, generating first signatures of chunks of the target file, and providing the first signatures of the chunks of the target file to a recipient computer; the recipient computer receiving the first signatures of the chunks of the target file over a computer network, generating first signatures of chunks of a reference file, comparing the first signatures of the chunks of the target file to the first signatures of the chunks of the reference file to identify chunks that are common between the target file and the reference file, and providing information on the chunks that are common between the target file and the reference file to the sender computer; the sender computer using the information on the chunks that are common between the target file and the reference file to identify chunks of the target file that are not in the reference file, creating a sequence of string edit operations to reconstruct the target file from the reference file, and sending the sequence of string edit operations to the recipient computer; and the recipient computer following the sequence of string edit operations to reconstruct the target file from the reference file. ### Claim 2 (depends on 1) The method of claim 1 further comprising: the recipient computer combining successive chunks that are common between the target file and the reference file into a single chunk having a chunk length that is longer than a chunk length of the chunks of the target file provided by the sender computer to the recipient computer. ### Claim 3 (depends on 1) The method of claim 1 wherein the information on the chunks that are common between the target file and the reference file provided by the recipient computer to the sender computer includes second signatures of chunks of the reference file that are common with chunks of the target file. ### Claim 4 (depends on 3) The method of claim 3 further comprising: the sender computer generating second signatures of chunks of the target file that are common with chunks of the reference file, and comparing the second signatures of chunks of the target file that are common with chunks of the reference file to the second signatures of chunks of the reference file that are common with chunks of the target file to identify chunks of the target file that are not in the reference file. ### Claim 5 (depends on 4) The method of claim 4 wherein the first signatures of the chunks of the target file comprise hash values of a first hash function and the second signatures of chunks of the target file that are common with chunks of the reference file comprise hash values of a second hash function different from the first hash function. ### Claim 6 (depends on 5) The method of claim 5 wherein the first hash function is a rolling hash function. ### Claim 7 (depends on 5) The method of claim 5 wherein the first hash function is a rolling hash function and the second hash function is an MD5 hash function. ### Claim 8 A system comprising: a sender computer comprising a processor and memory, the sender computer being configured to split a target file into a plurality of chunks, to generate signatures of the chunks of the target file, to provide the signatures of the chunks of the target file to a recipient computer, and to provide the recipient computer a sequence of string edit operations to reconstruct the target file in the recipient computer; and the recipient computer comprising a processor and memory, the sender computer being configured to split the reference file into a plurality of chunks after receiving the first signatures of the chunks of the target file from the sender computer, to provide the sender computer information on chunks common between the target file and the reference file, and to reconstruct the target file using the sequence of string edit operations, wherein the sequence of string edit operations comprises an edit operation to copy a chunk of the reference file into a reconstructed target file in the recipient computer and an edit operation to add a chunk that is in the target file but not in the reference file into the reconstructed target file. ### Claim 9 (depends on 8) The system of claim 8 wherein the recipient computer is configured to combine chunks common between the target file and the reference file into a chunk having a chunk length longer than a chunk length of chunks of the target file. ### Claim 10 (depends on 8) The system of claim 8 wherein the sender computer generates the signatures of the chunks of the target file using a rolling hash function. ### Claim 11 (depends on 8) The system of claim 8 wherein the recipient computer is configured to generate signatures of chunks of the reference file and to compare the signatures of the chunks of the reference file to the signatures of the chunks of the target file to identify chunks common between the target file and the reference file. ### Claim 12 (depends on 8) The system of claim 8 further comprising: another recipient computer configured to receive another sequence of string edit operations from the sender computer to reconstruct the target file locally in the other recipient computer. ### Claim 13 A method comprising: splitting a target file of a sender computer into a plurality of chunks; providing signatures of chunks of the target file to a recipient computer over a computer network; in response to receiving the signatures of the chunks of the target file in the recipient computer, splitting a reference file into a plurality of chunks and generating signatures of chunks of the reference file; identifying chunks common to both the target file and the reference file; and reconstructing the target file from the reference file in the recipient computer based at least on the identified chunks common to both the target file and the reference file, wherein reconstructing the target file from the reference file in the recipient computer comprises receiving a sequence of string edit operations in the recipient computer and following the sequence of string edit operations to reconstruct the target file from the reference file in the recipient computer, wherein the sequence of string edit operations includes an edit operation to copy a chunk of the reference file into a reconstructed target file in the recipient computer and an edit operation to add a chunk present in the target file but not in the reference file into the reconstructed target file. ### Claim 14 (depends on 13) The method of claim 13 further comprising: combining consecutive chunks common to both the target file and the reference file into another chunk having a chunk length longer than a chunk length of chunks of the target file. ### Claim 15 (depends on 13) The method of claim 13 wherein the signatures of the chunks of the target file are hash values. ### Claim 16 (depends on 15) The method of claim 15 wherein the hash values are rolling hash values. ### Claim 17 (depends on 13) The method of claim 13 further comprising: comparing the signatures of the chunks of the target file to the signatures of the chunks of the reference file to identify chunks common to both the target file and the reference file.