Patent ID: 8108353

Claim:
A method of determining sizing of chunk portions in data de-duplication, comprising: employing a hardware processor for: chunking input data into a first plurality of data segments each having a first size; assigning an identifier to each of the first plurality of data segments; assigning an index to each of said identifiers; creating a suffix array structure and a longest common prefix array structure from the indexes; based on the suffix array structure and the longest common prefix array structure, encoding each segment using an index, wherein indexes are generated for a largest sequence of repeated indexes (LRC) and non-repeated (NR) indexes; detecting repeated sequences of indexes and non-repeated indexes from the suffix array structure and the longest common prefix array structure; determining a second size based on said detected repeated sequences and non-repeated indexes, wherein said determining comprises detecting occurrences of repeated indexes in each LRC for overlap, and reducing each LRC having overlapped occurrences of repeated indexes to a non-overlapped index portion for reducing LRC size, wherein repeated indexes are left-diverse if associated left Identifications (IDs) are different, repeated indexes that are left-diverse comprise an LRC, and repeated indexes that are not left-diverse belong to an LRC; and chunking the input data into a second plurality of data segments each having the second size, wherein said detecting repeated sequences of indexes comprises: analyzing the suffix array structure to assign the indexes into groups, wherein the second size is further based on the size of the groups, and the indexes comprise a sequence of distinct integers.