Java programming problem
In this problem, you will be losslessly compressing text in a scheme reminiscent of Lempel-Ziv compression. You will build a class that efficiently compresses plaintext into a list, which can be serialized and transmitted to a receiver. The receiver will then be able to uncompress this list to reproduce the plaintext. The main idea behind our efficient storage is to maintain a dictionary of common substrings, and refer to these substrings rather than reproduce them. As such, we encode a string into a sequence of Atom S, with each Atom pointing to an index in our dictionary and a string to follow it. Example For example, consider the string can you can a can as_a_canner_can_can_a_can?. Compression We could compress it with the following dictionary Index Entry 0 "can" ".you" "can_a" "can_as_" 6 "a" "canner_can_" "can_a_can?" 7 The string str can then be encoded with the following Atom S: [0, "can"], [0, "_you_"], [1, "_a"], [3, "5"], [0, "a"], [1, "ner_can_"], [3, "_can?"] Uncompression To uncompress the Atoms, you go atom by Atom, rebuilding the dictionary in the process. The dictionary starts with one entry, the empty string (i.e., "'). The first Atom is interpreted to mean taking index 0 in our dictionary (i.e. "") and appending the string "can". The result is entered as a dictionary entry at index 1. en appends a "you." to the dictionary item at index 0 (i.e. "'). The result is entered as a dictionary entry at index 2. The third Atom appends a "a" to the dictionary item at index 1 (i.e. "can"). The result is entered as a dictionary entry at index 3. Putting these three Atom s side by side, we get "can_you_can_a", which is a prefix of the string being compressed. It is essential that the dictionary be rebuilt identically to the dictionary that was used to compress, or else the index numbers will be mangled. The task You are tasked with developing a Compressor based on the code on the hw1p3 repository, with the following features: It should provide good compression ratio (original size / encoded size). It should computationally efficient (i.e. fast running time). It should have a modest memory utilization (i.e. space efficient). In this problem, you will be losslessly compressing text in a scheme reminiscent of Lempel-Ziv compression. You will build a class that efficiently compresses plaintext into a list, which can be serialized and transmitted to a receiver. The receiver will then be able to uncompress this list to reproduce the plaintext. The main idea behind our efficient storage is to maintain a dictionary of common substrings, and refer to these substrings rather than reproduce them. As such, we encode a string into a sequence of Atom S, with each Atom pointing to an index in our dictionary and a string to follow it. Example For example, consider the string can you can a can as_a_canner_can_can_a_can?. Compression We could compress it with the following dictionary Index Entry 0 "can" ".you" "can_a" "can_as_" 6 "a" "canner_can_" "can_a_can?" 7 The string str can then be encoded with the following Atom S: [0, "can"], [0, "_you_"], [1, "_a"], [3, "5"], [0, "a"], [1, "ner_can_"], [3, "_can?"] Uncompression To uncompress the Atoms, you go atom by Atom, rebuilding the dictionary in the process. The dictionary starts with one entry, the empty string (i.e., "'). The first Atom is interpreted to mean taking index 0 in our dictionary (i.e. "") and appending the string "can". The result is entered as a dictionary entry at index 1. en appends a "you." to the dictionary item at index 0 (i.e. "'). The result is entered as a dictionary entry at index 2. The third Atom appends a "a" to the dictionary item at index 1 (i.e. "can"). The result is entered as a dictionary entry at index 3. Putting these three Atom s side by side, we get "can_you_can_a", which is a prefix of the string being compressed. It is essential that the dictionary be rebuilt identically to the dictionary that was used to compress, or else the index numbers will be mangled. The task You are tasked with developing a Compressor based on the code on the hw1p3 repository, with the following features: It should provide good compression ratio (original size / encoded size). It should computationally efficient (i.e. fast running time). It should have a modest memory utilization (i.e. space efficient)
