File comparison for data backup and file synchronization

A method for calculating a position sensitive digital signature from data on a first storage medium for comparison with a digital signature that represents data on a second storage medium, comprising the steps of:

• selecting the data in the first system with an indexed sliding window;
• applying a function F to the data within the window to generate the incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature;
• and
• comparing the position sensitive digital signature with at least one digital signature representing data in the second system.

A method for providing an incremental backup of a first memory in a second memory wherein a set of different files have previously been stored in the second memory, comprising the steps of:

• selecting a file from the first memory for examination;
• generating a signature from a portion of the file defined by a sliding indexed window;
• comparing the generated signature with signatures generated from the set of previously stored files having different filenames;
• determining the closest matching previously stored file, relative to the file under examination, where the stored file and the file under examination have different filenames, by identifying at least some portions of the stored file and the file under examination which are different, wherein said determining comprises applying a function F to the data within said sliding indexed window to generate an incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature;
• and
• storing the portions of the file under examination identified as being different from the closest matching file in the second memory.

A method for determining a minimum set of data compression units for restoring a file from a base copy and a plurality of revision elements, comprising the steps of:

• selecting the base copy and revision elements required to build the file;
• sorting the selected base copy and revision elements into a list with the most recently generated revision element at the list head and the base copy at the list tail;
• reading information for each selected revision element into an array with five columns:
• chunk, operation, data offset, data length, and target offset;
• creating an output array indicative of the reconstructed file with five columns:
• revision element pointer, chunk, data offset, data length, and target offset;
• calling a recursive function for the most recent revision, requesting data offset 0 and the final file length, and passing in target offset 0, the recursive function iterating through the array columns and comparing the requested data offset and length with the target of offset and data length of each item, and in the case of a match, writing an entry into the output array if the array item is a data operation;
• optimizing, via a block filter, an optimal set of array elements wherein elements not affecting said output array are ignored;
• and
• sorting the output array by revision element and chunk;
• and
• transmitting the array followed by the transmission blocks for each data block.