?? huffman_template_algorithm.html
字號:
<HTML>
<HEAD>
<meta name="Keywords" content="Compression, Algorithm, Data Compession, Data Coding, Huffman Algorithm, Template Algorithm, non-numerical costs, non-numerical weights, non-numerical frequencies, Fibonacci, C++, STL, UNIX, Solaris, Vinokur">
<meta name="Description" content="Using this program you can build Huffman codes with non-numerical weights">
<TITLE> n-ary Huffman Template Algorithm </TITLE>
</HEAD>
<BODY>
<PRE>
[ Last Modification : 2001/09/11]
---------------------------------
Hi,
Here is <font color="red"><b>n-ary Huffman Template Algorithm</b></font>.
The algorithm has been written by Alex Vinokur.
Programming Language : C++.
Any and all comments would be appreciated.
<a href="http://up.to/alexvn">Alex </a><a href="http://go.to/alexv_math">Vinokur</a>
-----------------------------------
<a href="mailto:alexvn@bigfoot.com">alexvn@bigfoot.com</a>, <a href="mailto:alexvn@dr.com">alexvn@dr.com</a>
<a href="mailto:alexv@hitechclub.com">alexv@hitechclub.com</a>
<a href="http://up.to/alexvn">http://up.to/alexvn</a>
<a href="http://go.to/alexv_math">http://go.to/alexv_math</a>
<a href="http:huffman_template_algorithm.html">http://alexvn.freeservers.com/s1/huffman_template_algorithm.html</a>
<a href="http:huffman_template_algorithm.zip">http://alexvn.freeservers.com/s1/huffman_template_algorithm.zip</a>
-----------------------------------
Previous version :
<a href="http:hta_1_1.html">http://alexvn.freeservers.com/s1/hta_1_1.html</a>
<a href="http:hta_1_1.zip">http://alexvn.freeservers.com/s1/hta_1_1.zip</a>
-----------------------------------
<TABLE cellpadding=20><TR><TD bgcolor="#FFBBBB"><PRE>
<font size=+1>
<b>Content</b>.
1. <a href="#label_Algorithm"><b>Algorithm</b></a>
2. <a href="#label_Classes_List"><b>Classes</b></A>
3. <a href="#label_Program_List"><b>Program Files</b> (<i>Description</i>)</A>
4. <a href="#label_Tests_and_Data"><b>Tests</b> (<i>Description and Input Data Files</i>)</A>
5. <a href="#label_Program"><b>Program Files</b> (<i>Headers & Source</i>)</A>
6. <a href="#label_Compiling"><b>Compiling</b></A>
7. <a href="#label_Running"><b>Running</b> (<i>Tests</i>)</A>
8. <a href="http:huffman_template_algorithm.zip"><b>Download</b></A>
</font>
</PRE></TD></TR></TABLE>
<a NAME="label_Algorithm"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#DDDDEE"><PRE>
====================================================
=================== 1. <font color="FF0055"><b>Algorithm</b></font> ===================
1. n-ary Huffman algorithm uses
the {0, 1, ..., n-1} alphabet to encode message.
Built tree is n-ary one.
2. Huffman template algorithm enables
to use non-numerical weights (costs, frequences).
For more details see the discussion titled
"<font color="#FF5555"><b>Huffman codes with non-numerical cost?</b></font>"
started 1999/02/22 in
* <a href="http://groups.google.com/groups?hl=en&lr=&safe=off&ic=1&th=4bbe4ee455ca554e,8&seekm=7b08cs%24vo2%241%40nnrp1.dejanews.com">comp.dsp</a>
* <a href="http://groups.google.com/groups?hl=en&lr=&safe=off&ic=1&th=4607aa3f5f2b8c6b,3&seekm=7au9ab%247ot%241%40nnrp1.dejanews.com">comp.theory</a>
* <a href="http://forum.swarthmore.edu/epigone/sci.math/gloigrinthoo">sci.math</a>
====================================================
</PRE></TD></TR></TABLE>
<a NAME="label_Classes_List"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#FFEEBB"><PRE>
====================================================
================ 2. <font color="FF0055"><b>List Of Classes</b></font> ================
Main template classes used in the algorithm are as following :
1. <a href="#label_Cell_class">Cell</a><SYMBOL, WEIGHT>
2. <a href="#label_Node_class">Node</a><SYMBOL, WEIGHT>
3. <a href="#label_InternalNode_class">InternalNode</a><SYMBOL, WEIGHT>
4. <a href="#label_TerminalNode_class">TerminalNode</a><SYMBOL, WEIGHT>
5. <a href="#label_BasicHuffmanTree_class">BasicHuffmanTree</a><SYMBOL, WEIGHT, ARY>
------------------------------------------
6. <a href="#label_LoadedHuffmanTree_class">LoadedHuffmanTree</a><SYMBOL, WEIGHT, ARY>
7. <a href="#label_DriedHuffmanTree_class">DriedHuffmanTree</a><WEIGHT, ARY>
------------------------------------------
The user should use only
<a href="#label_LoadedHuffmanTree_class"><b>LoadedHuffmanTree</b></a> and/or
<a href="#label_DriedHuffmanTree_class"><b>DriedHuffmanTree</b></a> classes.
<b><font color=red>LoadedHuffmanTree</font></b> requires (as input data) the <u>symbols</u> and <u>their weights</u>.
<b><font color=red>DriedHuffmanTree</font></b> requires (as input data) <i><u>only</u></i> the <u>weights</u>.
====================================================
</PRE></TD></TR></TABLE>
<a NAME="label_Program_List"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#DDEEDD"><PRE>
====================================================
============= 3. <font color="FF0055"><b>List Of Program Files</b></font> =============
The algorithm contains the following files :
1. <a href="#label_huf_service">huf_service.H</a> auxiliary functions
2. <a href="#label_huf_class">huf_class.H</a> template classes definition
3. <a href="#label_huf_methods">huf_methods.H</a> template methods description
4. <a href="#label_huf_main">huf_main.C</a> tests; includes
4.1. Two test classes definition:
- <a href="#label_AAA">AAA ("symbol")</a>
- <a href="#label_BBB">BBB ("weight")</a>
4.2. <a href="#label_main">Main program</a>
====================================================
</PRE></TD></TR></TABLE>
<a NAME="label_Tests_and_Data"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#DDEEFF"><PRE>
====================================================
==== 4. <font color="FF0055"><b>Tests : Description and Input Data Files</b></font> ===
The main program contains the following tests :
<a href="#label_test_1_1_a">Test#1.1</a>. Creating Loaded 5-ary Huffman Tree
from data vector
with <b><font color="#00AA00">char</font>-symbols</b> and <b><font color="#00AA00">int</font>-weights</b>
<a href="#label_test_1_2_a">Test#1.2</a>. Encoding and Decoding vector-message
using 5-ary Huffman Tree
<a href="#label_test_1_3_a">Test#1.3</a>. Encoding and Decoding string-message
using 5-ary Huffman Tree
<a href="#label_test_2_a">Test#2</a>. Creating Loaded 24-ary Huffman Tree
from data vector
with <b><font color="#00AA00">char</font>-symbols</b> and <b><font color="#00AA00">int</font>-weights</b>
<a href="#label_test_3_1_a">Test#3.1</a>. Creating Loaded Binary Huffman Tree
from data vector
with <b><font color="#00AA00">char</font>-symbols</b> and <b><font color="#00AA00">int</font>-weights</b>
<a href="#label_test_3_2_a">Test#3.2</a>. Encoding and Decoding vector-message
using Binary Huffman Tree
<a href="#label_test_3_3_a">Test#3.3</a>. Encoding and Decoding string-message
using Binary Huffman Tree
<a href="#label_test_4_a">Test#4</a>. Creating Dried (Unloaded) Binary Huffman Tree
from data vector
with <b><font color="#00AA00">int</font>-weights</b>
Note. This vector contains Fibonacci sequence.
For more details about connection
between Huffman codes and Fibonacci numbers
see the message titled
"<font color="#FF5555"><b>Huffman codes and Fibonacci numbers</b></font>"
published 1999/04/28 in
* sci.math (<a href="http://forum.swarthmore.edu/epigone/sci.math/twalgixskay/">http://forum.swarthmore.edu/epigone/sci.math/twalgixskay/</a>)
* <a href="http://groups.google.com/groups?q=+%22Alex+Vinokur%22+group:sci.math+insubject:Huffman+insubject:Fibonacci+author:Vinokur&lr=&safe=off&scoring=date&as_drrb=quick&as_qdr=&as_mind=29&as_minm=3&as_miny=1995&as_maxd=29&as_maxm=4&as_maxy=2001&rnum=1&ic=1&selm=7g6jc7%24m0i%241%40nnrp1.dejanews.com">sci.crypt</a>
* <a href="http://groups.google.com/groups?lr=&safe=off&ic=1&th=64f3c1104ffbc92e&seekm=7g6j9k%24lur%241%40nnrp1.dejanews.com">comp.compression</a>
<a href="#label_test_5_a">Test#5</a>. Creating Dried (Unloaded) Binary Huffman Tree
from data file
with <b><font color="#00AA00">int</font>-weights</b>
File name is "<a href="#label_weights_file">weights_file_01</a>"
<a href="#label_test_6_a">Test#6</a>. Creating Loaded Binary Huffman Tree
from data file
with <b><font color="#00AA00">char</font>-symbols</b> and <b><font color="#00AA00">int</font>-weights</b>
File name is "<a href="#label_data_file">data_file_01</a>"
<a href="#label_test_7_a">Test#7</a>. Creating Loaded Binary Huffman Tree
from data vector
with <b><font color="red">string</font>-symbols</b> and <b><font color="#00AA00">float</font>-weights</b>
<a href="#label_test_8_a">Test#8</a>. Creating Loaded Binary Huffman Tree
from data vector
with <b><font color="red">AAA</font>-symbols</b> and <b><font color="red">BBB</font>-weights</b>
<a NAME="label_weights_file"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#DDDDFF"><PRE>
----- Test Data File "weights_file_01" -----
3
3
20
9
2
9
100
11
17
--------------------------------------------
</PRE></TD></TR></TABLE>
<a NAME="label_data_file"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#DDDDFF"><PRE>
----- Test Data File "data_file_01" --------
a 3
b 3
c 20
d 9
e 2
f 9
h 100
x 11
y 17
--------------------------------------------
</PRE></TD></TR></TABLE>
====================================================
</PRE></TD></TR></TABLE>
<a NAME="label_Program"></a>
<TABLE cellpadding=20><TR><TD bgcolor="#EEDDEE"><PRE>
====================================================
================== 5. <font color="FF0055"><b>Program Files</b></font> ================
<a NAME="label_huf_service"></a>
#########################################################
=== File <font color="blue"><b>#1</b></font> <a href="#label_huf_class">of 4</a> : <font color="blue"><b>huf_service.H</b></font> ========================
------------------- C++ code : BEGIN --------------------
<TABLE><TR><TD bgcolor="#DEEEDD"><PRE>
// ==============================================================
//
// Copyright (c) 1999-2001 by Alex Vinokur. This work and all works
// derived from it may be copied and modified without any
// restrictions other than that a copy of this copyright notice
// must be included in any copy of this work or any derived work.
//
// ==============================================================
///////////////////////////////////////
#ifndef huf_service_H
#define huf_service_H
///////////////////////////////////////
static char id_huf_service_H[] = "@(#)## n-ary Huffman Template Algorithm ## Author : Alex Vinokur ## "__FILE__;
// ##############################################################
// =============================
// n-ary Huffman Template Algorithm
// The algorithm (program) contains the following files :
// - huf_service.H
// - huf_class.H
// - huf_methods.H
// - huf_main.C
// =============================
//
// FILE : <font color="blue"><b>huf_service.H</b></font>
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION :
// <font color="#FF00FF"><b>Definition and implementation</b></font>
// <font color="#FF00FF"><b>of the following auxiliary template functions : </b></font>
// ----------------------------------------------
// - string to_str (...)
// - void add_to_vector (...)
// - void fill_vector (...)
// - unsigned int get_width (...)
// - string gstr_vect_ptrs (...)
// - string gstr_vector (...) // two functions
// - string gstr_path (...)
// - string gstr_map (...)
// - ostream& operator<< (...) // two operators
// ----------------------------------------------
//
// DATE VERSION
// ---- -------
// Aug-26-1999 NHTA 1.0
// Jul-05-2001 NHTA 1.1
// Sep-11-2001 NHTA 1.2
//
// ##############################################################
#include <strstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <algo.h>
#include <functional>
#include <iostream>
#include <fstream.h>
#include <typeinfo>
#include <iomanip.h>
#include <assert.h>
//#######################################################
//##### PART : DEFINES & CONSTANTS ######################
//#######################################################
#define MIN_VALUE(x,y) ((x) < (y) ? (x) : (y))
#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x) if (!(x)) {cerr << endl << endl << "\t=== BUG IN PROGRAM ===" << endl;}; assert (x)
#define FATAL_TITLE "FATAL ERROR : "
#define FATAL_SHIFT " : "
#define FATAL_MSG(x) cerr << endl \
<< FATAL_TITLE \
<< x \
<< endl \
<< FATAL_SHIFT \
<< "File - " \
<< __FILE__ \
<< ", Line#" \
<< __LINE__ \
<< endl; \
exit (1)
#define ERROR_TITLE "ERROR : "
#define ERROR_SHIFT " : "
#define ERROR_MSG(x) cerr << endl \
<< ERROR_TITLE \
<< x \
<< endl \
<< ERROR_SHIFT \
<< "File - " \
<< __FILE__ \
<< ", Line#" \
<< __LINE__ \
<< endl;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -