home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / 2773 < prev    next >
Encoding:
Text File  |  1992-07-22  |  1.8 KB  |  41 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!mips!sdd.hp.com!usc!cs.utexas.edu!torn!watserv1!watmath!bbobak
  3. From: bbobak@math.waterloo.edu (Brad Bobak)
  4. Subject: Re: sizing huffman trees
  5. Message-ID: <1992Jul22.142705.26970@math.waterloo.edu>
  6. Organization: University of Waterloo
  7. References: <1992Jul21.220205.18507@math.waterloo.edu> <1992Jul22.003239.15971@s1.gov>
  8. Date: Wed, 22 Jul 1992 14:27:05 GMT
  9. Lines: 30
  10.  
  11. In article <1992Jul22.003239.15971@s1.gov>, lip@s1.gov (Loren I. Petrich) writes:
  12. > In article <1992Jul21.220205.18507@math.waterloo.edu> bbobak@math.waterloo.edu (Brad Bobak) writes:
  13. > >  I was wondering if anyone has come up with an algorithm for determining
  14. > > the size of an encoded huffman tree from just the frequencies of the
  15. > > letters (sorted or unsorted, it doesn't matter).
  16. > >  Right now, to size a tree, I'm basically building it, and this is time
  17. > > consuming if I'm using alot of trees.
  18. > >  Any pointers, suggestions, etc. would be appreciated.
  19. > 
  20. >     There are several algorithms for building Huffman trees.
  21. > Perhaps the simplest is the original Huffman one.
  22. > 
  23. > Repeat to build all the nodes:
  24. > 
  25. >     Look through all the unconnected nodes and symbols to find
  26. > the two with the two smallest frequencies.
  27. > 
  28. >     Connect these to the new node and make the node's frequency
  29. > the sum of the two branches' frequencies.
  30. > 
  31. > 
  32. >     I'm sure that this will be fairly efficient unless one has a
  33. > terribly skewed distribution.
  34.  
  35.   Yes, I'm aware of this, and have an efficient algorithm for building
  36.  trees. What I want to be able to do, tho, is to find out how big an
  37.  output code a huffman tree will generate from just the frequencies.
  38.   Since I'm expecting to calculate the size alot (> 500 times), I can't
  39.  afford to psuedo-build the tree each time, just to find the output size.
  40.  
  41.