1. A method for scalable data deduplication working with small data chunks, the method comprising: for each of the small data chunks, generating a signature based on a combination of a representation of characters that appear in the small data chunks with a representation of frequencies of the small data chunks, wherein the signature is used to help in selecting the data to be deduplicated.