title: Choosing a compression algorithm to implement
body: <p>I've been given some coursework to implement a compression algorithm of my choice. It can be any language, however the languages I know best would be Java, followed by C. It will be evaluated based on -</p>
  
  <ol>
  <li><p>The decompressed output must match the original input, so I can only look at loss less algorithms. </p></li>
  <li><p>The run time must be proportional to the length of the message. </p></li>
  <li><p>The memory requirement must be independent of the length of the message. </p></li>
  </ol>
  
  <p>Our implementations will be tested as follows - </p>
  
  <ol>
  <li><p>A standard text file</p></li>
  <li><p>A binary file with byte values from 0-255</p></li>
  <li><p>A large file ~10mb of unspecified content. </p></li>
  </ol>
  
  <p>My initial thought is to use dynamic arithmetic coding, but I'm wondering if there is an algorithm better suited to the constraints above? 
  Secondly, is it a better idea to do it in C rather than Java? I ask this because I think C will have a smaller memory foot print but I'm unsure if that's actually the case. </p>
  
  <p>I've spent some time Googling this question, and a few sites mention LZW coding combined with dynamic  Huffman coding. Would this be a sensible avenue to pursue? Our lecturer did warn us that 90% of the submissions that tried dynamic Huffman coding over the years were not correctly implemented. </p>
  
  <p>That said, I'm not afraid to give it a try, but I would value some opinions before I begin. </p>
  
  <p>Any feedback would be much appreciated. </p>