[学习]huffman压缩

初识Huffman

简单说明Huffman编码的原理 　　实现霍夫曼编码的方式主要是创建一个二叉树和其节点。这些树的节点可以存储在数组里，数组的大小为符号（symbols）数的大小n，而节点分别是终端节点（叶节点）与非终端节点（内部节点）。

　　一开始，所有的节点都是终端节点，节点内有三个字段：

　　1.符号（Symbol）

　　2.权重（Weight、Probabilities、Frequency）

　　3.指向父节点的链接（Link to its parent node）

　　而非终端节点内有四个字段：

　　1.权重（Weight、Probabilities、Frequency）

　　2.指向两个子节点的 链接（Links to two child node）

　　3.指向父节点的链接（Link to its parent node）

　　基本上，我们用’0’与’1’分别代表指向左子节点与右子节点，最后为完成的二叉树共有n个终端节点与n-1个非终端节点，去除了不必要的符号并产生最佳的编码长度。

　　过程中，每个终端节点都包含着一个权重（Weight、Probabilities、Frequency），两两终端节点结合会产生一个新节点，新节点的权重是由两个权重最小的终端节点权重之总和，并持续进行此过程直到只剩下一个节点为止。

　　实现霍夫曼树的方式有很多种，可以使用优先队列（Priority Queue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：

　　⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n

　　⒉如果队列内的节点数>1，则：

　　　⑴从队列中移除两个最小的Pi节点，即连续做两次remove（min（Pi）, Priority_Queue) 　　　⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和 　　　⑶把（2）产生之节点加入优先队列中 　　⒊最后在优先队列里的点为树的根节点（root） 　　 　　而此算法的时间复杂度（ Time Complexity）为O（n log n）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log n）。

　　此外，有一个更快的方式使时间复杂度降至线性时间（Linear Time）O（n），就是使用两个队列（Queue）创件霍夫曼树。第一个队列用来存储n个符号（即n个终端节点）的权重，第二个队列用来存储两两权重的合（即非终端节点）。此法可保证第二个队列的前端（Front）权重永远都是最小值，且方法如下：

　　⒈把n个终端节点加入第一个队列（依照权重大小排列，最小在前端） 　 　　⒉如果队列内的节点数>1，则：

　　　⑴从队列前端移除两个最低权重的节点 　　　⑵将（1）中移除的两个节点权重相加合成一个新节点 　　　⑶加入第二个队列 　　⒊最后在第一个队列的节点为根节点

　　虽然使用此方法比使用优先队列的时间复杂度还低，但是注意此法的第1项，节点必须依照权重大小加入队列中，如果节点加入顺序不按大小，则需要经过排序，则至少花了O（n log n）的时间复杂度计算。

　　但是在不同的状况考量下，时间复杂度并非是最重要的，如果我们今天考虑英文字母的出现频率，变量n就是英文字母的26个字母，则使用哪一种算法时间复杂度都不会影响很大，因为n不是一个庞大的数字。

实现方法

话不多说，直接上具体代码，这里仅展现部分核心代码。

Huffman节点的定义

1
2
3
4
5
6
7
8
9
struct Hufnode{
	struct Hufnode *lc;		//左右子树
    struct Hufnode *rc;
    unsigned int pow;		//当前节点的权重
    unsigned char Data;		//这个节点如果是叶子结点，那么存储编码对应的字符
    bool leaf;				//标记是否是字符
    string code;			//存储对应的Huffman编码
    Hufnode() : lc(NULL), rc(NULL), leaf(true){}	//初始化节点
}

Huffman树的构建

根据开头介绍的两种方法，各有千秋，其中我们使用比较容易理解的方法，此处不使用优先队列等等优化性的算法，转向使用冒泡排序，因为排序的内容不算多，而且在第一次排序完成之后不会有较多的排序要求，我们可以通过对冒泡优化加快速度（使其变成一个插入算法）。

此处建立一个class类，实现Huffman树的构建和相关功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Hufman{
	private:
    	Hufnode * root	//记录下Huffman树的根节点
        map<unsigned char, string> code_map	//用来快速访问字符对应的Huffman编码
    public:
        Hufman();	//构造函数，初始化Huffman树
        Hufnode *return_root();  				//获得当前Huffman树的根节点
        unsigned int pow_len();				    //返回文件拥有的字符数量  
        string return_code(unsigned char c);	//根据字符返回对应的Huffman编码  
        void destroy(Hufnode *root);	    	//递归调用，解构函数
        void build_huf(Hufnode data[], int size);	//构建Huffman树，输入的是节点数量和节点  
        void update_code(Hufnode *root, string fa, const char *c);	//根据建立的Huffman树，递归给每一个字符生成Huffman编码  
        void bob_sort(Hufnode data[], int size);	//优化过的冒泡排序  
}

上述代码块展示的是 Huffman类的声明，声明的函数具体的实现自行完成。

压缩函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
void zip(char *input, char *output){
	FILE *fp = NULL, *outfile = NULL;	//文件输入和输出
    byte_fre array[256];	//用二进制方式读入文件，可以实现对所有格式文件兼容，开256个空间是因为只有256种不同的字节。
    Hufnode *data;		//Huffman建树的临时缓冲区
    unsigned char char_temp = 0;	//字节操作文件的缓冲区
    unsigned int code_len = 0;	//记录文件长度
    data = new Hufnode[256];
    for (int i = 0; i < 256; i++)
        array[i].data = i;
    unsigned int buffer[MAX_LINE]; // MAX_LINE 是一个宏定义，代表缓冲区的大小，此处为1024
    buffer[0] = 0;

在上面初始化zip压缩函数，然后开始读入文件，求解统计整个文件不同字节权值。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
while (!feof(fp) && fread(buffer, 1, 1, fp))
{
    int a = buffer[0];
    array[a].fre++;	//统计不同的字节权值
    buffer[0] = 0;
}

int len = 0;
for (int i = 0; i < 256; i++) //搜集权值用来构建hafuman树 
{
    if (array[i].fre > 0)
    {
        data[len].pow = array[i].fre;
        data[len].leaf = true;
        data[len++].Data = array[i].data;
    }
}
Hufman CODE;
CODE.build_huf(data, len); //此处调用hufman类里面的建树

len = 0;
for (int i = 0; i < 256; i++) // 为了在元数据写入不同字节权重
{
    if (array[i].fre > 0)
    {
        data[len].pow = array[i].fre;
        data[len].leaf = true;
        data[len++].Data = array[i].data;
    }
}

outfile = fopen(output, "wb+");
fwrite((unsigned int *)&len, sizeof(unsigned int), 1, outfile);
for (int i = 0; i < len; i++)
{
    fwrite((unsigned char *)&data[i].Data, sizeof(unsigned char), 1, outfile);
    fwrite((unsigned int *)&data[i].pow, sizeof(unsigned int), 1, outfile);
}

char code_buf[256] = "\0"; // 

rewind(fp);
int file_len = CODE.pow_len();
fwrite((unsigned long *)&file_len, sizeof(unsigned long), 1, outfile); // 读取文件的大小
fread((unsigned char *)&char_temp, sizeof(unsigned char), 1, fp);      // 按照字节读取8个bit
int temp = 0;
while (!feof(fp))
{

    strcat(code_buf, CODE.return_code(char_temp).data());

    while (strlen(code_buf) >= 8)
    {
        char_temp = '\0';
        for (int i = 0; i < 8; ++i)
        {
            char_temp <<= 1;
            if (code_buf[i] == '1')
            {
                char_temp |= 1;
            }
        }
        fwrite((unsigned char *)&char_temp, sizeof(unsigned char), 1, outfile); // 输出
        strcpy(code_buf, code_buf + 8);
    }
    if (feof(fp))
        break;
    fread((unsigned char *)&char_temp, sizeof(unsigned char), 1, fp); // 读入文件数据
}

// 处理最后不足8位的情况
code_len = strlen(code_buf);
if (code_len > 0)
{
    memset(&char_temp, 0, sizeof(char_temp));
    for (int i = 0; i < code_len; ++i)
    {
        char_temp <<= 1;
        if (code_buf[i] == '1')
            char_temp |= 1;
    }
    char_temp <<= 8 - code_len;                                            // 移动到高位
    fwrite((unsigned char *)&char_temp, sizeof(unsigned char), 1, outfile); // 
}
fclose(fp);
fclose(outfile); 
delete[] data;

解压函数

下面是需要使用的临时变量： 

1
2
3
4
5
6
7
8
9
10
11
void unzip(char *input, char *output){
	FILE *inputf=NULL, *outputf=NULL;
    unsigned int len=0;
    unsigned long file_len=0;	//读入的文件大小
    Hufnode *root = NULL;	//临时指针
    unsigned int node_num=0;
    unsigned char code_temp = 0; // 缓冲区
    byte_fre array[256];	//统计权重
    inputf = fopen(input, "rb");
    outputf = fopen(output, "wb+");

然后是正式读取压缩的文件开始解压。（代码并没有验证解压文件是否是上述压缩算法生成的，而且是以字节流读取文件内容，所以任何文件都可以被这个函数读取并尝试解压）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
if (inputf == NULL)
        return;
    fread((unsigned char *)&len, sizeof(unsigned int), 1, inputf);	//先读取字符种类
    for (int i; i < len; i++)
    {
        fread((unsigned char *)&array[i].data, sizeof(unsigned char), 1, inputf);
        fread((unsigned int *)&array[i].fre, sizeof(unsigned int), 1, inputf);
    }
    Hufnode data[256];
    for (int i = 0; i < len; i++) //collecting data to build huffman tree 
    {
        if (array[i].fre > 0)
        {
            data[i].pow = array[i].fre;
            data[i].leaf = true;
            data[i].Data = array[i].data;
        }
    }
    Hufman CODE;
    CODE.build_huf(data, len);	//根据读入的字节权重重建huffman树

    fread((unsigned char *)&file_len, sizeof(unsigned long), 1, inputf); //读取文件大小
    root = CODE.return_root();
    unsigned int writen_len = 0;
    while (1)
    {
    fread((unsigned char *)&code_temp, sizeof(unsigned char), 1, inputf); //每次一个字节进行解压
        for (int i = 0; i < 8; ++i)
        {
            if (code_temp & 128)
                root = root->rc;
            else
                root = root->lc;

            if (root->leaf == true)
            {
                fwrite((unsigned char *)&root->Data, sizeof(unsigned char), 1, outputf);
                ++writen_len;
                if (writen_len >= file_len)
                    break;                 // 跳出循环
                root = CODE.return_root(); // 恢复
            }
            code_temp <<= 1; // switch next bit to the highest
        }
        if (writen_len >= file_len)
            break;  // 文件大小检测
    }
    fread((unsigned char *)&code_temp, sizeof(unsigned char), 1, inputf);

    // close the file
    fclose(inputf);
    fclose(outputf);

main部分

这个东西就是需要根据实际情况编写，此处不再粘贴完整的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int main()
{
    char input[100] = {0}, output[100] = {0};
    int opcode = -1;
    while (true)
    {
        welcome();
        cin >> opcode;
        switch (opcode)//three cases
        {
        case 1://zip
            cout << "Your file name of input" << endl;
            cin >> input;
            while (file_name(input) == false)
            {
                cin >> input;
                if (input[0] == '0' && input[1] == 0)
                {
                    return 0;
                }
            }
            cout << "Your file name of output" << endl;
            cin >> output;
            zip(input, output);
            cout << "Zip behaviour is complete" << endl
                 << endl;
            break;
        case 2://unzip
            cout << "Your file name of input" << endl;
            cin >> input;
            while (file_name(input) == false)
            {
                cin >> input;
                if (input[0] == '0' && input[1] == 0)
                {
                    return 0;
                }
            }
            cout << "Your file name of output" << endl;
            cin >> output;
            unzip(input, output);
            cout << "Unzip behaviour is complete" << endl
                 << endl;
            break;
        case 3://exit
            return 0;
            break;
        default:
            cout << "Your Input is not allowed" << endl;
            break;
        }
    }
}

总结

目前的问题

在代码注释中提及过，解压缩是不能够验证压缩的文件是否是Huffman压缩算法生成的，如果直接解压一个正常的文件，会解压出来一个压缩炸弹或者一个啥也没有。与之配套的压缩算法中也没有加入相应的验证程序。没有对单一字节类型进行特化处理，比如说，压缩一个文本全部是“a”的文本文件会丢失数据，因为在建立哈夫曼树的时候没有特化考虑只有一种字节类型的情况，之后修改加入。

没了

作下此文，只是记一次被迫从零开始完成一个数据结构作业，~ diss一下qhy。应该不会有人认出来吧。如果恰巧也是这个老师教学的，~

#学习 #数据结构
[学习]huffman压缩
http://example.com/2020/11/01/学习/学习-huffman/
Author
peach-water
Posted on
November 1, 2020
Licensed under