Huffman coding experiment report

Two . Experimental content ：

subject ： Huffman code / decoding

Problem description ：

Using Huffman coding for communication can greatly improve the channel utilization , Shorten information transmission time , Reduce transmission costs . however , This requires precoding of the data to be transmitted through an encoding system at the transmitting end , Decode the transmitted data at the receiving end （ Restore ）. For duplex channels （ That is, the channel that can transmit information in both directions ）, Each end needs a complete edit / Decoding system . Try to write a Huffman code for such information sending and receiving / Decoding system .

The basic requirements ：

1. Receiving raw data （ message ）： Input the message from the terminal （ The message is a string , Assume only by 26 Lowercase English letters ）.

（2） code ： Use the built Huffman tree , Code the message .

（3） Print coding rules ： That is, the one-to-one correspondence between characters and codes .

（4） Print and display the message and its corresponding Huffman code .

（5） Receiving raw data （ Huffman code ）： Input a string of binary Huffman codes from the terminal （ from

0 and 1 constitute ）.

（6） decoding ： The binary code is decoded by using the built Huffman tree .

（7） Print the decoding content ： Display the decoding result on the terminal .

3、 ... and . Experimental scheme

（ One ） Algorithm design ideas ：

    1. To realize Huffman coding, we first need to build an optimal binary tree , The larger the weight, the closer the leaf node is to the root node , Its algorithm is ： The length of the string entered by the keyboard determines the number of nodes of the optimal binary tree , Traverse the length of this string , Create with character length n Single node tree of . Select the two root nodes with the smallest weight and the second smallest weight to form a tree , Repeat the process —— Combine the minimum and sub minimum root nodes until each node appears on the optimal binary tree .

  2． Construct Huffman code ：

The left branch is 0, The right branch is 1, The binary code corresponding to each node is the Huffman code of the node . Adopt the method of leaf node upward backtracking , Record a number every time you return one . Save the obtained code into code[].

 3. code ：

   Compare the strings according to the obtained Huffman tree , According to the left branch is 0 The right branch is 1 Output its corresponding code .

 4. decode ： According to Huffman tree backtracking coding .

（ Two ） Description of using modules and variables （ For example, the definition and meaning of structure ）

  Huffmancode To calculate the coding function according to Huffman coding .

Maxval Is the maximum .

typedef struct

{

    int weight;

    int lchild, rchild;

    int parent;

}HTNode, * HuffmanTree; The node structure of the tree

void Select(HuffmanTree& ht, inti, int& s1, int& s2) Building the optimal binary tree

void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, intn);// According to the Huffman tree, the Huffman code

void decode(hufmtree tree[]);// Read the messages in turn , Decoding according to Huffman tree

Huffman（） To build Huffman tree function .

Four . Experimental steps or procedures （ After debugging, the correct source program ）

#pragma warning(disable:4996)

#include <iostream>

#include<string>

#include <iomanip>

using namespace  std;

typedef struct

{

    int weight;

    int lchild, rchild;

    int parent;

}HTNode, * HuffmanTree;

typedef char** HuffmanCode;

void Select(HuffmanTree& ht, int i, int& s1, int& s2)

{

    int j, k;

    k = s1;

    for (j = 1; j < i + 1; j++)

        if (s1 != j && j != s2 && ht[j].parent == 0)

        {

            s1 = j; break;

        }

    for (j = 1; j < i + 1; j++)

        if (s2 != j && s1 != j && j != k && ht[j].parent == 0)

        {

            s2 = j; break;

        }

    for (j = 1; j <= i; j++)

        if (ht[j].weight < ht[s1].weight && ht[j].parent == 0)s1 = j;

    if (s1 == s2)

    {

        for (j = 1; j < i + 1; j++)

            if (s2 != j && s1 != j && j != k && ht[j].parent == 0)

            {

                s2 = j; break;

            }

    }

    for (j = 1; j <= i; j++)

        if (ht[j].weight < ht[s2].weight && ht[j].parent == 0 && j != s1)

            s2 = j;

}

void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)

{

    int i, s1, m, s2, start;

    char* cd;

    int c, f;

    if (n <= 1) return;

    m = 2 * n - 1;

    HT = new HTNode[m + 1];

    for (i = 1; i <= n; i++)

    {

        HT[i].weight = w[i - 1];

        HT[i].parent = 0;

        HT[i].lchild = 0;

        HT[i].rchild = 0;

    }

    for (i = n + 1; i <= m; i++)

    {

        HT[i].weight = 0;

        HT[i].parent = 0;

        HT[i].lchild = 0;

        HT[i].rchild = 0;

    }

    cout << "\n The construction process of Huffman tree is as follows ：" << endl;

   

   

    for (i = n + 1; i <= m; i++)

    {

        Select(HT, i - 1, s1, s2);

        HT[s1].parent = i;  HT[s2].parent = i;

        HT[i].lchild = s1;  HT[i].rchild = s2;

        HT[i].weight = HT[s1].weight + HT[s2].weight;

    }

    HC = new  char* [n + 1];

    cd = new  char[n];

    cd[n - 1] = '\0';

    for (i = 1; i <= n; ++i)

    {

        start = n - 1;

        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)

            if (HT[f].lchild == c) cd[--start] = '0';

            else cd[--start] = '1';

        HC[i] = new  char[n - start];

        strcpy(HC[i], &cd[start]);

    }

    delete cd;

}

int main()

{

    HuffmanTree HT;

    HuffmanCode HC;

    char s[50], s2[20];  int i = 0, count = 0;  int  w[50] = { 0 };

   

    cout << " Please enter the string to be encoded :" << endl;

    cin >> s;

    while (s[i] != '\0')

    {

        int j;

        for (j = 0; j < count; j++)

            if (s[i] == s2[j])

            {

                w[j]++; i++; break;

            }

        if (j == count)

        {

            s2[count] = s[i];

            w[count]++;

            i++; count++;

        }

    }

    HuffmanCoding(HT, HC, w, count);

    cout << " character \t\t  frequency \t\t code " << endl;

    for (i = 0; i < count; i++)

        cout << s2[i] << "\t\t" << w[i] << "\t\t" << HC[i + 1] << endl;

    string s1, s3;

    cout << " Enter the English you want to encode :" << endl;

    cin >> s1;

    cout << " code :" << endl;

    for (i = 0; i < s1.length(); i++)

    {

        for (int j = 0; j < count; j++)

        {

            if (s1[i] == s2[j])

            {

                cout << HC[j + 1];

                break;

            }

        }

    }

    cout << endl;

    cout << " Enter the Huffman code to be decoded :" << endl;

    cin >> s3;

    char h[10];

    int k = 0, l, j;

    cout << " decode :" << endl;

    while (k <= s3.length())

    {

        for (int i = 1; i <= count; i++)

        {

            l = k;

            for (j = 0; j < strlen(HC[i]); j++, l++)

            {

                h[j] = s3[l];

            }

            h[j] = '\0';

            if (strcmp(HC[i], h) == 0)

            {

                cout << s2[i - 1];

                k = k + strlen(HC[i]);

                break;

            }

        }

    }

    cout << endl;

    return 0;

}

5、 ... and ． Program run results （ Some screenshots of program running results ）

6、 ... and ． Summary of the experiment （ What problems are encountered during debugging , How? ）

   This experiment is a comprehensive application of trees , The process is basically to construct the optimal binary tree according to the string entered by the keyboard , Construct the Huffman code corresponding to the string , Realize the operation of decoding and encoding . This operation is about transforming data into a tree , It involves the construction and processing of trees . There are many problems in algorithm and unfamiliar with software experiments . For example, encountered c4996 The problem is that I haven't encountered it , After inquiry, we know that... Is added to the header file #pragmawarning(disable:4996) But ignore this mistake . I have done this experiment for a long time , The main reason is that the knowledge of trees is not detailed enough , Many problems need to be paused to check , I hope to study harder in the future , Strive to do better .