home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1B / DATAFILE_PDCD1B.iso / _pocketbk / pocketbook / 004 / oplexamp_z / HUFFMAN.TXT < prev    next >
Text File  |  1994-05-07  |  3KB  |  54 lines
  1. >Ah, excellent. The text in question is the bible, 4.5M long
  2. >uncompressed. The dictionary derived from this is about 14000
  3. >words, the dictionary file is 112k.
  4.  
  5. >I understand a 4M flash is due soon, but it will still be 
  6. >more costly than the 2M one of course.
  7.  
  8. You should definitely consider huffman-coding.  For one thing, you need it.
  9. I'm afraid you won't get sufficient compression without it - to fit in the
  10. 2M flash.
  11. Secondly, it is very, very easy, because you have a known text.  That means
  12. you can hardwire the decoding tables, and the decoding logic will be
  13. extremely simple.
  14.  
  15. How to do this: (this is actually a simplified version of an algorithm which
  16. I think is in the comp.compression faq, the faq algorithm gives denser
  17. tables with slightly more complex code). 
  18.  
  19. Encode the most frequent x words, where x is the largest x for which the
  20. longest huffman-code will fit in 8 bits (or 9 bits, or 7 bits, whatever
  21. seems appropriate).  Include in the decoding program a table of length 256
  22. (2**8).  To decode a symbol, just index the table with the 8 next bits in
  23. input, to find in the table 1) The next symbol in input, and 2) The length
  24. of this symbol.  Advance input with the length, use the symbol, and repeat.
  25.  
  26. Writing the table: For each code c, eg. c=10111, representing a symbol s, do
  27.   for all possible values of xxx, let c' = xxxc = xxx11101
  28.     table[c'].length = length(c) = 5
  29.     table[c'].symbol = s
  30.  
  31. If I haven't said this already: Encode "letter-words" and "non-letters
  32. words" separately. - That means with separate huffman tables, too.
  33.  
  34. Probably the space character will be so frequent that it's information
  35. contents is a fraction of a bit, but spaces will still cost you 1 bit each
  36. with huffman coding.  Arithmetic coding would handle this, but is much more 
  37. complex.  You might handle this heuristically.
  38.  
  39. The characters in literals (eg. in the dictionary) might also be
  40. huffman-coded.  If you don't do that, at least pack the 52 letters in 6
  41. bits.
  42.  
  43. If you want your encoded text to include other things besides word indices,
  44. such as literal words or end-of-text markers, then don't use flag bits:
  45. This will be very wasteful, as word indices will be much more frequent than
  46. anything else: Instead include these possibilities as "special symbols" in
  47. the huffman code for word indices.
  48.  
  49. Hope this helps.  Please give me some feedback on how this works for you;
  50. frankly, I haven't implemented half of this myself.
  51.  
  52. Anders Munch        |  Department of Computer Science
  53. juul@diku.dk        |  University of Copenhagen, Denmark
  54.