FILE COMPARISON FOR DATA BACKUP AND FILE SYNCHRONIZATION

摘要

File comparison employs a single function F (28) to calculate a digital signature (32) from data in a sliding window (58, 56). The digital signature (32) is both incrementally computable and position sensitive. In particular, F is computable without reprocessing each byte in the array when the window is advanced and facilitates detection of such changes as transposed bytes of data. The function F is defined by two qualities. First, for F(A+B), where A is an array, F(A+B) = F(A) + F(B). Second, given a concatenation operator "!" such that "0!A" indicates an array A with 0 inserted before A, the function F has the property that there is a function G such that F(0!A) = G(F(0!A)). Both polynomials and cyclic redundancy checks ("CRC") may be used as that class of function.