Skip to content

Latest commit

 

History

History
50 lines (34 loc) · 2.39 KB

ex12.md

File metadata and controls

50 lines (34 loc) · 2.39 KB

Exercise 12

Part A

Implement a class HuffmanIso that extends Huffman. In such class, override the methods writeTrie and readTrie. When writing/reading a char for a given leaf node, use the charset ISO-8859-1 instead of the current UTF-16 in Huffman.

Note 0: you would lose Unicode support by doing it.

Note 1: for coding/decoding, you can use the method getBytes in String with charset StandardCharsets.ISO_8859_1.

Write a test class HuffmanIsoTest with the following two tests:

  • testCompareOnShortNorwegianSentence in which you compare both HuffmanIso and Huffman on the text string "Jeg ønsker å få en god karakter i denne eksamenen" encoded in UTF-8. Verify that HuffmanIso can compress it, whereas Huffman actually makes it bigger. Explain why.

  • testCompareOnBook in which you compare both HuffmanIso and Huffman on the text of the Odyssey book encoded in UTF-8. Verify that both HuffmanIso and Huffman do compress it, but their difference in compression ratio is minimal (i.e., less than 0.001). Explain why.

Part B

Consider a string representation for exam grades, in the format of <id><grade>, where id is a number starting from 0 (can assume NO MORE than 500 students in an exam, and there can be exams with just a couple of students), and grades in the range A-F. A valid string would be for example: 0A1F2F3C12F13B14B27A201B497A. You can assume that the ids are sorted, but there can be holes in the sequence (e.g., representing students that did not submit).

Write a class GradeCompressorImp that implements the given GradeCompressor interface.

You MUST come up with an efficient compression algorithm which is specialized and customized for this problem domain (i.e., do not use either Huffman nor LZW, but rather use DnaCompressor as inspiration). For example, if there is just 1 student, you should not use more than 2 bytes in total for the compression. If there are 100 students, should not use more than 150 bytes. In your implementation, you can rely on and use the classes BitWriter and BitReader.

Write a test class GradeCompressorTest that extends the given GradeCompressorTestTemplate test suite. If your implementation of GradeCompressorImp is correct, all tests should pass.

Solutions

Solutions to this exercise can be found in the solutions module, under the org.pg4200.sol12 package.