Patent ID: 7487169

Claim:
A method for differential file compression, comprising: calculating hash values for blocks of at least one reference file and storing them in a hash value array; computing a suffix array on the block hash values; and processing at least one version file by staffing at zero offset and calculating hash values at every offset until all unique matches between the hash values of the at least one reference file and the hash values of the at least one version file are found, and returning the best match, further comprising the use of specific data structures to reduce the cost of searching the hash value array, wherein the data structures include a block hash table, wherein reference file hash values are organized for efficient matching, wherein block hash table values include one bit to denote whether an entry is unique or a duplicate, and the remaining bits denote an address in a reference file, wherein if the hash value is unique then odd locations contain its location in the hash value array, else if the hash value is not unique then the first odd location contains a count of the number of occurrences of the hash value in the suffix array.