home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / 2801 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  2.0 KB
  1. Path: sparky!uunet!mcsun!sun4nl!cwi.nl!dik
  2. From: dik@cwi.nl (Dik T. Winter)
  3. Newsgroups: comp.compression
  4. Subject: Re: more entropy
  5. Message-ID: <6775@charon.cwi.nl>
  6. Date: 24 Jul 92 22:31:02 GMT
  7. References: <1992Jul23.174740.14559@usenet.ins.cwru.edu> <1992Jul24.003709.21603@s1.gov>
  8. Sender: news@cwi.nl
  9. Organization: CWI, Amsterdam
  10. Lines: 41
  11.  
  12. In article <1992Jul24.003709.21603@s1.gov> lip@s1.gov (Loren I. Petrich) writes:
  13.  > In article <1992Jul23.174740.14559@usenet.ins.cwru.edu> daf10@po.CWRU.Edu (David A. Ferrance) writes:
  14.  > 
  15.  > >for (i=0;i<256;i++) for (j=0;j<256;j++)  {
  16.  > >    freq = count[i][j] / total;
  17.  > >    ent += freq * log10(1/freq) / 0.30103;
  18.  > >    }
  19.  > 
  20.  >     I presume that the code also included:
  21.  > 
  22.  >     ent = 0;
  23.  >     total = 0;
  24.  >     for (i=0;i<256;i++) for (j=0;j<256;j++)
  25.  >       total += count[i][j];
  26.  > 
  27.  > >I get values > 8.
  28.  >     The theoretical maximum value is log2(256*256) = 16.
  29.  > 
  30. Right.  And indeed the entropy can very well be larger than 8.  What creates
  31. the confusion is that you calculate the entropy of pairs of characters, and
  32. in that case an entropy of 8 means you can compress by at most 50% by encoding
  33. pairs of characters.  What you want is single character entropy with memory
  34. of one previous character.  I am not an expert in information theory etc.
  35. (and indeed never have read very much about it), but my offhand suggestion
  36. is: add an array count1 of 256 elements where you count the occurrences of
  37. individual characters.  Next change the statement:
  38.         freq = count[i][j] / total;
  39.         ent += freq * log10(1/freq) / 0.30103;
  40. to:
  41.     freq = (double)count[i][j] / (double)count1[i];
  42.         ent += (double)count1[i] / total * freq * log10(1/freq) / 0.30103;
  43. (perhaps including some of the other suggestions, like using log2, -log2(freq)
  44. etc.).  This way you calculate for each character the entropy when it is
  45. following a specific character and you weigh that by the relative frequency
  46. of that preceding character.
  47.  
  48. dik
  49. -- 
  50. dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
  51. home: bovenover 215, 1025 jn  amsterdam, nederland
  52. dik@cwi.nl
  53.