Patent ID: 7454431

Claim:
A method for matching target file windows of a target file with source file windows of a source file used in a delta compression in delta compressors, said method comprising: partitioning the source file into a plurality of source file windows; partitioning the target file into a plurality of target file windows; and matching one of said plurality of source file windows with one of said target file windows based upon a distance function, wherein said distance function is as follows: Δ ⁡ ( S 1 , S 2 ) = ∑ i = 0 A - 1 ⁢  F S 1 ⁡ [ i ] - F S 2 ⁡ [ i ]  ∑ i = 0 A - 1 ⁢ max ⁡ ( F S 1 ⁡ [ i ] , F S 2 ⁡ [ i ] ) where, Δ(S 1 , S 2 ) is computed and stored as the distance function between two non-empty data segments, S 1 and S 2 , as a measure of similarity between the two data segments, where A comprises a size of an n-gram frequency array, and F S 1 and F S 2 are corresponding n-gram frequency arrays for data segments S 1 and S 2 respectively.