2022-03-01

记得大一上的通信原理课提到了霍夫曼编码

目的：实现某段文本的编码压缩，以及对其的解压操作

分步骤：

1.进行构造霍夫曼树

 1 #include<iostream>
 2 using namespace std;
 3 #define maxn 3000
 4 typedef struct HUFFMANTREE {
 5     double pinlv;
 6     HUFFMANTREE* ltree;
 7     HUFFMANTREE* rtree;
 8 }htree;
 9 htree* forest[maxn];
10 htree* creathtree(double a[],int len)
11 {
12     for (int i = 1;i <= len;i++)
13     {
14         htree* temp = new htree;
15         temp->pinlv = a[i];
16         temp->ltree = NULL;
17         temp->rtree = NULL;
18         forest[i] = temp;
19         cout << forest[i]->pinlv << endl;
20     }
21     //把哈夫曼森林给初始化喽
22 
23     int minn1 = -1, minn2;
24     for (int i = 1;i <= len - 1;i++)
25     {
26         for (int j = 1;j <= len;j++)
27         {
28             if (forest[j] != NULL && minn1 == -1)
29                 minn1 = j;
30             else if (forest[j] != NULL)
31             {
32                 minn2 = j;
33                 break;
34             }
35         }
36         //挑选可选的初始值
37 
38         for (int j = 1;j <= len;j++)
39         {
40             if (forest[j]!=NULL&&forest[j]->pinlv < forest[minn1]->pinlv)
41             {
42                 minn2 = minn1;
43                 minn1 = j;
44             }
45             else if (forest[j] != NULL&& forest[j]->pinlv < forest[minn2]->pinlv)
46                 minn2 = j;
47         }
48         //寻找最小的两个结点
49 
50         
51         htree* root = new htree;
52         root->pinlv = forest[minn1]->pinlv + forest[minn2]->pinlv;
53         root->ltree = forest[minn1];
54         root->rtree = forest[minn2];
55         forest[minn1] = root;
56         forest[minn2] = NULL;
57         //将那两个最频率的结点给结合成新的树，并将树给存进哈夫曼森林中去，继续卷
58     }
59     return forest[minn1];
60 }

2.算wpl，即总字节数

 1 int wpl(htree* root,int deep)
 2 {
 3     if (root == NULL)
 4         return 0;
 5     if (root->ltree == NULL && root->rtree == NULL)
 6         return root->cost*deep;
 7     else 
 8     {
 9         int left = wpl(root->ltree, deep + 1);
10         int right = wpl(root->rtree, deep + 1);
11         return left + right;
12     }

3.编码的方式（自己搞的感觉很繁琐且拖沓迟钝）

  1 #include<iostream>
  2 #include<algorithm>
  3 using namespace std;
  4 #define maxn 3000
  5 typedef struct HUFFMANTREE {
  6     double pinlv;
  7     char ch;
  8     int bianma[maxn];
  9     HUFFMANTREE* ltree;
 10     HUFFMANTREE* rtree;
 11 }htree;
 12 htree* forest[maxn];
 13 void pinlv_count(htree* codes[],int len)
 14 {
 15     int book[53] = { 0 };
 16     for (int i = 1;i <= len;i++)
 17     {
 18 
 19         if (codes[i]->ch >= 'a' && codes[i]->ch <= 'z')
 20         {
 21             if (book[codes[i]->ch - 'a' + 1] == 0)
 22                 book[codes[i]->ch - 'a' + 1]++;
 23             else
 24             {
 25                 book[codes[i]->ch - 'a' + 1]++;
 26                 codes[i] = NULL;
 27             }
 28         }
 29         else if (codes[i]->ch >= 'A' && codes[i]->ch <= 'Z')
 30         {
 31             if (book[codes[i]->ch - 'A' + 27] == 0)
 32                 book[codes[i]->ch - 'A' + 27]++;
 33             else
 34             {
 35                 book[codes[i]->ch - 'A' + 27]++;
 36                 codes[i] = NULL;
 37             }
 38         }
 39     }
 40     for (int i = 1;i <= len;i++)
 41     {
 42         if (codes[i] != NULL)
 43         {
 44             if (codes[i]->ch >= 'a' && codes[i]->ch <= 'z')
 45                 codes[i]->pinlv = (double)book[codes[i]->ch - 'a' + 1] / len;
 46             else if (codes[i]->ch >= 'A' && codes[i]->ch <= 'Z')
 47                 codes[i]->pinlv = (double)book[codes[i]->ch - 'A' + 1] / len;
 48         }
 49     }
 50 }
 51 htree* creathtree(char a[],int len)
 52 {
 53     for (int i = 1;i <= len;i++)
 54     {
 55         htree* temp = new htree;
 56         temp->ch=a[i];
 57         temp->ltree = NULL;
 58         temp->rtree = NULL;
 59         forest[i] = temp;
 60     }
 61     //把哈夫曼森林给初始化喽
 62     pinlv_count(forest, len);
 63     int len_quchonghou=0;
 64     for (int i = 1;i <= len;i++)
 65         if (forest[i] != NULL)
 66             len_quchonghou++;
 67     len = len_quchonghou;
 68     int minn1 = -1, minn2;
 69     for (int i = 1;i <= len - 1;i++)
 70     {
 71         minn1 = -1;
 72         for (int j = 1;j <= len;j++)
 73         {
 74             if (forest[j] != NULL && minn1 == -1)
 75                 minn1 = j;
 76             else if (forest[j] != NULL)
 77             {
 78                 minn2 = j;
 79                 break;
 80             }
 81         }
 82         //挑选可选的初始值
 83 
 84         for (int j = 1;j <= len;j++)
 85         {
 86             if (forest[j]!=NULL&&forest[j]->pinlv < forest[minn1]->pinlv)
 87             {
 88                 minn2 = minn1;
 89                 minn1 = j;
 90             }
 91             else if (j!=minn1&&forest[j] != NULL&& forest[j]->pinlv < forest[minn2]->pinlv)
 92                 minn2 = j;
 93         }
 94         //寻找最小的两个结点
 95 
 96         
 97         htree* root = new htree;
 98         root->ltree = forest[minn1];
 99         root->rtree = forest[minn2];
100         root->pinlv = forest[minn1]->pinlv + forest[minn2]->pinlv;
101         forest[minn1] = root;
102         forest[minn2] = NULL;
103         //将那两个最频率的结点给结合成新的树，并将树给存进哈夫曼森林中去，继续卷
104     }
105     return forest[minn1];
106 }
107 void HUFFMANBIANMA(htree* root,int len,int a[])
108 {
109     if (root != NULL)
110     {
111         if (root->ltree == NULL && root->rtree == NULL)
112         {
113             cout << root->ch<<": ";
114             for (int i = 1;i < len;i++)
115             {
116                 root->bianma[i] = a[i];
117                 cout << root->bianma[i];
118             }
119             cout << endl;
120         }
121         else
122         {
123             a[len] = 0;
124             HUFFMANBIANMA(root->ltree, len + 1, a);
125             a[len] = 1;
126             HUFFMANBIANMA(root->rtree, len + 1, a);
127         }
128     }
129 }
130 int main(void)
131 {
132     char a[] = { 'x','a','b','c','d','e','f','a','a','a' };
133     htree* root = creathtree(a,9);
134     int bianma[maxn];
135     HUFFMANBIANMA(root, 1, bianma);
136     return 0;
137 }