# 2 霍夫曼编码

## 2.1 统计字符频率

A A C B C A A D D B B A D D A A B B

A 7
B 5
C 2
D 4

## 2.2 构造霍夫曼树

### 2.2.2 构造过程

（1）选取权值最小和次小的节点作为左右子树，构造一棵二叉树。
（2）将步骤1构造的二叉树的根节点的权值设置为，左右子树之和。
（3）去除步骤1中已经选过的节点，将新的二叉树的根节点加入至待选集合
（4）继续重复步骤1，直至仅剩一个元素未选中。

## 2.3 编码

A 0
B 10
C 111
D 110

A A C B C A A D D B B A D D A A B B 编码后的数据长度为：
0 0 111 10 111 0 0 110 110 10 10 0 110 110 0 0 10 10 编码长度为35。

A 00
B 01
C 10
D 11

00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01

## 2.4 代码实现

#include<iostream>
#include<string>
using namespace std;

struct Node
{
double weight;  //存储权值
string ch;  //存储字符
string code; //编码
int lchild, rchild, parent;//分别存储左孩子、右孩子、父节点位置
};

void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b
{
int i;
double weight = 0; //找最小的数
for (i = 0; i <n; i++)
{
if (huffTree[i].parent != -1)     //判断节点是否已经选过
continue;
else
{
if (weight == 0)
{
weight = huffTree[i].weight;
*a = i;
}
else
{
if (huffTree[i].weight < weight)
{
weight = huffTree[i].weight;
*a = i;
}
}
}
}
weight = 0; //找第二小的数
for (i = 0; i < n; i++)
{
if (huffTree[i].parent != -1 || (i == *a))//排除已选过的数
continue;
else
{
if (weight == 0)
{
weight = huffTree[i].weight;
*b = i;
}
else
{
if (huffTree[i].weight  < weight)
{
weight = huffTree[i].weight;
*b = i;
}
}
}
}
int temp;
if (huffTree[*a].lchild < huffTree[*b].lchild)  //小的数放左边
{
temp = *a;
*a = *b;
*b = temp;
}
}

void Huff_Tree(Node huffTree[], int w[], string ch[], int n)
{
for (int i = 0; i < 2 * n - 1; i++) //初始过程
{
huffTree[i].parent = -1;
huffTree[i].lchild = -1;
huffTree[i].rchild = -1;
huffTree[i].code = "";
}
for (int i = 0; i < n; i++)
{
huffTree[i].weight = w[i];
huffTree[i].ch = ch[i];
}
for (int k = n; k < 2 * n - 1; k++)
{
int i1 = 0;
int i2 = 0;
Select(huffTree, &i1, &i2, k); //将i1，i2节点合成节点k
huffTree[i1].parent = k;
huffTree[i2].parent = k;
huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
huffTree[k].lchild = i1;
huffTree[k].rchild = i2;
}
}

void Huff_Code(Node huffTree[], int n)
{
int i, j, k;
string s = "";
for (i = 0; i < n; i++)
{
s = "";
j = i;
while (huffTree[j].parent != -1) //从叶子往上找到根节点
{
k = huffTree[j].parent;
if (j == huffTree[k].lchild) //如果是根的左孩子，则记为0
{
s = s + "0";
}
else
{
s = s + "1";
}
j = huffTree[j].parent;
}
cout << "字符 " << huffTree[i].ch << " 的编码：";
for (int l = s.size() - 1; l >= 0; l--)
{
cout << s[l];
huffTree[i].code += s[l]; //保存编码
}
cout << endl;
}
}

string Huff_Decode(Node huffTree[], int n,string s)
{
cout << "解码后为：";
string temp = "",str="";//保存解码后的字符串
for (int i = 0; i < s.size(); i++)
{
temp = temp + s[i];
for (int j = 0; j < n; j++)
{
if (temp == huffTree[j].code)
{
str=str+ huffTree[j].ch;
temp = "";
break;
}
else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍历后没有
{
str= "解码错误！";
}
}
}
return str;
}

# 3 LZ77压缩算法

## 3.1 概述

Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法（A Universal Algorithm for Sequential Data Compression ）”的论文，论文中描述的算法被后人称为LZ77算法。值得说的是，LZ77严格意义上来说不是一种算法，而是一种编码理论。

## 3.3 实现过程

（1）设置编码位置为输入流的开始
（2）在滑窗的待编码区查找搜索区中的最大匹配字符串
（3）如果找到字符串，输出(偏移值， 匹配长度)， 窗口向前滑动“匹配长度”
（4）如果没有找到，输出待编码区的第一个字符，窗口向前滑动一个单位
（5）如果待编码区不为空，回到步骤2