Click here to Skip to main content
14,925,595 members
Articles / Programming Languages / C++
Article
Posted 11 Nov 2002

Stats

59.4K views
21 bookmarked

n-ary Huffman Template Algorithm

Rate me:
Please Sign up or sign in to vote.
2.40/5 (8 votes)
12 Nov 20021 min read
The algorithm allows any kind of weights (costs, frequencies), including non-numerical ones

Introduction

Web page :
http://alexvn.freeservers.com/s1/huffman_template_algorithm.html

Download :
http://www.simtel.net/pub/pd/60300.shtml
http://home.barak-online.net/alexvn/s2/hf/hufnta22.zip



The algorithm allows any kind of weights (costs, frequencies), including non-numerical ones. The {0, 1, ..., n-1} alphabet is used to encode message. Built tree is n-ary one.

The algorithm is based on a set of template classes :
- Cell(SYMBOL, WEIGHT),
- Node(SYMBOL, WEIGHT),
- InternalNode(SYMBOL, WEIGHT),
- TerminalNode(SYMBOL, WEIGHT),
- BasicHuffmanTree(SYMBOL, WEIGHT, ARY),
- LoadedHuffmanTree(SYMBOL, WEIGHT, ARITY),
- DriedHuffmanTree(WEIGHT, ARITY).
The user should use only LoadedHuffmanTree and/or DriedHuffmanTree classes.
LoadedHuffmanTree requires (as input data) the symbols and their weights.
DriedHuffmanTree requires (as input data) only the weights.

The program contains the following tests :
* Creating Loaded 5-ary Huffman Tree from data vector with char-symbols and int-weights;
* Creating Loaded 24-ary Huffman Tree from data vector with char-symbols and int-weights;
* Creating Loaded Binary Huffman Tree from data vector with char-symbols and int-weights;
* Creating Dried (Unloaded) Binary Huffman Tree from data vector with int-weights (Fibonacci sequence);
* Creating Dried (Unloaded) Binary Huffman Tree from data file with int-weights;
* Creating Loaded Binary Huffman Tree from data file with char-symbols and int-weights;
* Creating Loaded Binary Huffman Tree from data vector with string-symbols and float-weights;
* Creating Loaded Binary Huffman Tree from data vector with AAA-symbols and BBB-weights;
* Encoding and Decoding vector-message using 5-ary Huffman Tree;
* Encoding and Decoding string-message using 5-ary Huffman Tree;
* Encoding and Decoding vector-message using Binary Huffman Tree;
* Encoding and Decoding string-message using Binary Huffman Tree



Source :
http://groups.google.com/groups?th=f9bb13f7426e888c

Raw run log (Demo) :
http://groups.google.com/groups?th=7daf90d4f66a47ad

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Alex Vinokur
Web Developer
Israel Israel
No Biography provided

Comments and Discussions

 
Questiondownload link Pin
Member 1222483324-Dec-15 11:57
MemberMember 1222483324-Dec-15 11:57 
GeneralMy vote of 1 Pin
_darksake_22-Jan-09 4:13
Member_darksake_22-Jan-09 4:13 
GeneralIt would be nice Pin
Jörgen Sigvardsson13-Nov-02 9:51
MemberJörgen Sigvardsson13-Nov-02 9:51 
GeneralRe: It would be nice Pin
Alex Vinokur13-Nov-02 18:28
MemberAlex Vinokur13-Nov-02 18:28 
GeneralThis is a link... Pin
Daniel Turini12-Nov-02 23:07
MemberDaniel Turini12-Nov-02 23:07 
GeneralRe: This is a link... Pin
Alex Vinokur13-Nov-02 6:07
MemberAlex Vinokur13-Nov-02 6:07 
GeneralRe: This is a link... Pin
robinds14-Nov-02 3:33
Memberrobinds14-Nov-02 3:33 
GeneralRe: This is a link... Pin
Alex Vinokur14-Nov-02 5:51
MemberAlex Vinokur14-Nov-02 5:51 
GeneralRe: This is a link... Pin
SimonR21-Jan-04 21:28
MemberSimonR21-Jan-04 21:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.