A method for performing lossless data compression, in an environment that maintains a data structure that organizes prime data elements (305, 306), wherein each prime data element consists of a sequence of bytes and has a distinct name that includes all of the bytes of the prime data element, wherein prime data elements are organized into a tree that encompasses subtrees and leaves represented by nodes (302, 303, 304) based on the values of successive bytes from the name of each prime data element, wherein each node of the tree has a name comprised of the sequence of values of successive bytes that specify how to reach the node, wherein all prime data elements are leaves of the tree, wherein the name of each prime data element is constructed by (i) applying a method of fingerprinting to the prime data element to identify locations, wherein each location contains content that evaluates to a pre-determined fingerprint, (ii) extracting a certain number of bytes that is smaller than the number of bytes of the prime data element from the identified locations, (iii) concatenating the extracted number of bytes to form a leading portion of the name of the prime data element, and (iv) appending remaining bytes of the prime data element to the leading portion of the name of the prime data element, the method further comprising: identifying one or more of the prime data elements based on a data chunk, wherein said identifying comprises constructing a name of the data chunk using the same method that was used to construct names of prime data elements in the data structure, and using the name of the data chunk to navigate through the data structure; determining a sequence of transformations that derives the data chunk from the identified one or more prime data elements if the data chunk is not identical to any of the identified one or more prime data elements; and generating a losslessly compressed representation of the data chunk, wherein the losslessly compressed representation is selected from a group including: a reference to one prime data element in the identified one or more prime data elements if the referenced data element is a duplicate of the data chunk; and a reference to one or more prime data elements in the identified one or more prime data elements, and the sequence of transformations which, when applied to the one or more prime data elements, results in the data chunk. identifying one or more of the prime data elements based on a data chunk, wherein said identifying comprises constructing a name of the data chunk using the same method that was used to construct names of prime data elements in the data structure, and using the name of the data chunk to navigate through the data structure; determining a sequence of transformations that derives the data chunk from the identified one or more prime data elements if the data chunk is not identical to any of the identified one or more prime data elements; and generating a losslessly compressed representation of the data chunk, wherein the losslessly compressed representation is selected from a group including: a reference to one prime data element in the identified one or more prime data elements if the referenced data element is a duplicate of the data chunk; and a reference to one or more prime data elements in the identified one or more prime data elements, and the sequence of transformations which, when applied to the one or more prime data elements, results in the data chunk. a reference to one prime data element in the identified one or more prime data elements if the referenced data element is a duplicate of the data chunk; and a reference to one or more prime data elements in the identified one or more prime data elements, and the sequence of transformations which, when applied to the one or more prime data elements, results in the data chunk.