home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / compress / 2769 < prev    next >
Encoding:
Text File  |  1992-07-21  |  1.3 KB  |  36 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!overload.lbl.gov!s1.gov!lip
  3. From: lip@s1.gov (Loren I. Petrich)
  4. Subject: Re: sizing huffman trees
  5. Message-ID: <1992Jul22.003239.15971@s1.gov>
  6. Sender: usenet@s1.gov
  7. Nntp-Posting-Host: s1.gov
  8. Organization: LLNL
  9. References: <1992Jul21.220205.18507@math.waterloo.edu>
  10. Date: Wed, 22 Jul 1992 00:32:39 GMT
  11. Lines: 23
  12.  
  13. In article <1992Jul21.220205.18507@math.waterloo.edu> bbobak@math.waterloo.edu (Brad Bobak) writes:
  14. >  I was wondering if anyone has come up with an algorithm for determining
  15. > the size of an encoded huffman tree from just the frequencies of the
  16. > letters (sorted or unsorted, it doesn't matter).
  17. >  Right now, to size a tree, I'm basically building it, and this is time
  18. > consuming if I'm using alot of trees.
  19. >  Any pointers, suggestions, etc. would be appreciated.
  20.  
  21.     There are several algorithms for building Huffman trees.
  22. Perhaps the simplest is the original Huffman one.
  23.  
  24. Repeat to build all the nodes:
  25.  
  26.     Look through all the unconnected nodes and symbols to find
  27. the two with the two smallest frequencies.
  28.  
  29.     Connect these to the new node and make the node's frequency
  30. the sum of the two branches' frequencies.
  31.  
  32.  
  33.     I'm sure that this will be fairly efficient unless one has a
  34. terribly skewed distribution.
  35.  
  36.