霍夫曼编码原理

在数据通信时，可以用0，1码的不同排列来表示字符。例如给定一段报文CAST CAST SAT AT A TASA，在报文中出现的字符集合是｛C，A，S，T｝，各个字符出现的频度是｛2，7，4，5｝。若给每个字符一个等长的二进制表示，例如 C:00 A:01 S:10 T:11，则所发的报文将是00011011 00011011 100111 0111 01 11011001，共计(2＋7＋5＋4)*2＝36个码。若按字符出现的频度不同给予不同长度的编码，出现频度较大的字符采用为数较少的编码，出现频度较小的字符采用位书较多的编码，可以是报文的码数降到最小，这就是所谓的最小冗余编码问题。霍夫曼编码就能实现这种最小冗余编码。上例中按字符出现的频度进行编码，A:0 T:10 S:110C:111，则最终的报文只有35个码，节省了传输中使用的单元。因而霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术。

二．编码实现

一般情况下，霍夫曼编码的工作主要分为三步。

第一步是准备工作，对于需要编码的字符（一般存在于文件里）进行扫描，统计每个字符出现的频次，得到一个整数数组。

第二步根据这个频次数组构造一棵霍夫曼树，这步是霍夫曼编码的核心内容。

第三步，再次扫描一遍待编码的字符，对每个字符，在霍夫曼树里搜索该字符，得到它的编码。

这里通过C#软件实现，便于可视化的界面及操作方便性

// 学习小结 吴新强于2013年3月20日16:58:11 桂电 2507
//
//
//


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;


namespace HuffmanCoding
{
    public partial class Form1 : Form
    {


        public Form1()
        {
            InitializeComponent();
        }
        
        public struct Node//定义节点结构
        {
            public int weight; //定义权重
            public int parent, lchild, rchild;//定义父亲，孩子 
        };
        public struct Min//定义最小两位数结构
        {
            public int s1;
            public int s2;
        };
        Node[] HTN = new Node[500];
        Min Getmin(int n) //寻找最小的两位权值
        {
            int min1, min2, i;
            Min code; //定义结构体Min
            code.s1 = 1;
            code.s2 = 1;
            min1 = 256;
            min2 = 256;
            for (i = 0; i < n; i++)//寻找最小值 
            {
                if (HTN[i].weight <= min1 && HTN[i].parent == 0)
                {
                    min1 = HTN[i].weight;
                    code.s1 = i;


                }
            }


            for (i = 0; i <= n; i++)//寻找次最小