一、本文概述

这是第一次在CSDN上写blog，想写很久了，一直因为忙耽搁了，放假了，打算整理一下这学期的一些代码和实验写blog。
本文主要根据我信息论课程的信源编码大作业报告所写，相关代码放在我的GitHub上，初次在CSDN发blog，小小紧张哈哈哈。

本文主要实现了哈夫曼编码，且性能较为优秀。另外还拓展实现了LZ编码和算数编码，并在将哈夫曼和LZ-78两种编码方式的cpp文件通过统一的main.cpp文件整合在一起，可以通过运行project来选择希望的编码方式对目标文件进行编码。

另外，本文的实验中，也出现了一些编译器的问题，例如Visual Studio下和Mac下存在着一定的优劣对比。

本文中给出了一些实现的部分代码，完整代码见GitHub：
https://github.com/YZ-WANG/Three-methods-for-source-encoding

二、编码原理

本文的实验实现了三种编码方式：哈夫曼编码、LZ编码和算数编码。下面分析其各自基本原理。

1. 哈夫曼编码

哈夫曼编码是是一种可变长的分组编码，完全依据各字符出现的概率来构造码字。二进制的哈夫曼编码是基于二叉树的编码思想，所有可能的输入符号在哈夫曼树上对应为一个节点，结点的位置就是该符号的哈夫曼编码。为了构造出唯一可译码，这些节点都是哈夫曼树上的终极结点（即叶子结点），不再延伸，不会出现前缀码。具体编码方法如下：

1. 将信源消息符号按其出现的概率大小依次排列为 p1≥p2≥…≥Pn；
2. 取两个概率最小的字母分别配以 0 和 1 两个码元，并将这两个概率相加作为一个新字母的概率，与未分配二进制符号的字母一起重新排队；
3. 对重排后的两个概率最小符号重复步骤2的过程；
4. 不断继续上述过程，直到最后两个符号配以 0 和 1 为止；
5. 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为相应码字。

特别地，有时为了得到最短平均码长，尽量减少赋长码的信源符号，需要在编码前对信源符号作添加，使得信源的符号数量满足 M(N-1)+1，其中M为正整数，N为进制，这样在多次合并后就能充分利用短码，以便降低平均码长。

此外，哈夫曼编码方法所得到的码并非是唯一的，造成非唯一的原因如下：

• 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼编码，但不会影响码字的长度。
• 对信源进行缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序可以是任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以得到较小的码方差。

哈夫曼编码的特点：

1. 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；
2. 而是缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。

哈夫曼码的编码效率是非常高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也将简单得多。但是应当注意，要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。
哈夫曼编码的解码则在识别出一个个叶子结点后按照叶子结点对应的原信源符号译码。

哈夫曼编码虽然效率出众，但仍然存在一些分组码所具有但缺点。例如概率特性必须精确测定，以此来编织码表，若略有变化，还需要更换码表。故实际编码过程中需要对原始数据扫描两遍，第一遍用来统计原始数据中各字符出现的概率，创建码表存放起来，第二遍则依据码表在扫描的同时进行编码，才能传输信息。如果将这种编码放在网络通信中，两遍扫描会引起较大的时延；如果用于数据压缩，则会降低速度。因此，出现了自适应哈夫曼编码方法，其码表不是实现构造，而是随着编码的进行，不断动态构造、调整。

2. 算术编码

由于在使用分组码对信源单符号进行编码时，没有将符号间的相关性纳入考虑之中：若将m个符号合起来进行编码则会增加设备复杂度，且组间符号的相关性还是无法纳入考虑。这就使得信源编码的匹配原则不能充分满足，编码效率有所损失。

为了克服这种局限性，一种基于非分组码的编码方法——算数编码应运而生。编码的基本思路是：将需要编码的全部数据看成某一 $L$ 长序列，所有可能出现的L长序列的概率映射到 $[0,1]$ 的区间上，把 $[0,1]$ 区间分成许多小段，每段长度等于某一序列的概率。再在段内取一个二进制小数用作码字，其长度可与该序列的概率匹配，达到高效率编码的目的。

算数编码实际的编译码过程比较复杂，但在性能上具有许多优点，特别是所需要的参数很少，不像哈夫曼编码那样需要一个很大的码表。从理论上说，只要已知信源符号集及其符号概率，算数编码的平均码长可以接近符号熵。

具体编码方法如下：

1. 将文件以字节为单位读入，并将其分割成bit串形式
2. 计算文件中bit0和bit1的总数量和各自的概率
3. 对一定长度L的符号串进行编码，并将数据写入压缩后文件中
4. 从压缩文件中读入数据，并还原成长度为L的符号串输入至解压文件中

3. LZ编码

LZ编码是由以色列研究者齐夫和伦佩尔完全脱离哈夫曼码和算术编码的设计思路，设计出的一系列比哈夫曼编码更有效、比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ系列算法利用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。

实验采用的 LZ-78编码 的编码过程如下：

• 设信源符号集 $A=a1,a2,\dots ,aK$ 共K个符号，设输入信源符号序列为 $U=(u1,u2,\dots \dots ,uL)$，编码是将此序列分成不同的段。
• 分解是迭代进行的，在第i步，编码器从 $s_i$ - 1 短语后的第一个符号开始向后搜索在此之前从未出现过的最短短语 $s_i$，将短语 $s_i$ 添入字典第i段。由于 $s_i$ 是此时字典中最短的新短语，所以 $s_i$ 在去掉最后一个符号 $x$ 后所得的前缀必定是字典中之前已经出现过的。
• 若设此前缀是在第 $j(<i)$ 步时出现的，则对 $s_i$ 的编码就可以利用 $j$ 和 $s_i$ 最后一位符号 $x$ 来表示，即为码字 $(j,x)$。对于段号 $j$，最多需要 $\lceil logi\rceil$ bit表示，而符号 $x$ 只需 $\lceil logK\rceil$ bit。若编码猴的字典中短语共有M(U)个，则U序列编码后输出的码流总长度为 $(\lceil logi\rceil +\lceil logK\rceil )$。

LZ-78编码的核心实际上就是一个包含了短语、段号、码字、二进制码的字典，如下所示。

短语	段号	码字	二进制码
a	1	(0,a)	(0,0)
b	2	(0,b)	(0,1)
ba	3	(2,a)	(10,0)
baa	4	(3,a)	(11,0)
…	…	…	…

LZ编码的编码方法非常简捷，译码也很简单，可以一边译码一边建立字典。译码时若收到的码字为 $(j,x)$，则在字典中找到第 $j$ 个短语，然后加上符号 $x$ 即可译出对应的新短语，并添入字典。因此发送时无需传送字典本身。LZ算法的逻辑简单，硬件实现廉价，运算速度快，在很多计算机数据存储中得到应用。其优点在于能够有效利用信源输出序列的频率、重复性和高使用率的冗余度，是一种自适应算法，只需对信源序列进行一次扫描，无须知道信源的先验统计特性，运算时间正比于序列长度。但也有缺点，一是不能有效地利用位置的冗余度；二是该算法通常在序列起始段压缩效果差一些，随着长度增加效果变好。

三、算法设计思路

1. 哈夫曼编码

a. 设置功能结构体和函数

为构造哈夫曼树，首先要知道压缩的目标文件中各个字符的频度。因此先对整个文件进行扫描，统计各个字符的频度。在本算法中，考虑到编码方式，将 每个字节对应于一个符号，对于 8 bit 的二进制码，共计 $2^8=256$ 种。故创建一个 结构体 Node，表示符号与对应的频度，用于对其进行统计。

struct Node
{
	unsigned char uch; //一字节的符号
	unsigned long weight;  //对应的频度
};

针对哈夫曼树本身，需要对每一个节点进行刻画。创建 结构体 HufNode，其中包含变量：频度 weight、父亲节点 parent、左子节点left_child、右子节点right_child，对应的符号uch，存放其编码的字符数组code。

struct HufNode
{
	unsigned char uch;                      //记录符号
	unsigned long weight;                   //权重，即频度
	char * code;                             //存放编码的数组
	int parent, left_child, right_child;    //定义父节点，左子节点，右子节点
};

typedef struct HufNode HufNode, * HufTree; //方便后续建树

有了struct HufNode之后，用于构造哈夫曼树的符号就用*HufTree来存储。为256种可能的符号各自构造实例组成指针数组，即Node *tmp_nodes =(Node *)malloc(256*sizeof(Node));。该语句为 存放256种符号的实例的指针数组 在内存开辟了相应的空间。

实际上，考虑到读入的目标文件实际上在计算机中就是 一长串的二进制码流，我们每次操作的 一字节的符号实际上就是8bit长的二进制码，那么这8bit二进制码其实就对应于十进制的0-255。如此一来，就可以把256种字节用0-255表示，即tmp_nodes[i].uch = (unsigned char)i;，每个节点存储的unsigned char uch实际上就 对应其下标的8位二进制码表示。

实际上没必要在用指针指向对应的节点，只需要存储其对应节点的uch的8位二进制码相应的十进制值，就可以 通过指针数组的索引到达对应节点。在编码构造哈夫曼树时，需要每次在tmp_nodes数组找到目前剩余节点中频度最小的两个节点，将其纳入树中。因此要编写一个函数void Find2Min来完成该功能。该函数实现起来比较简单，主要就是两次for循环遍历未加入哈夫曼树的节点。

void Find2Min(HufNode * huf_tree, unsigned int n, int * s1, int * s2)
{
	unsigned int i;
	unsigned long min = ULONG_MAX;
	for(i = 0; i < n; i++)
		if(huf_tree[i].parent == 0 && huf_tree[i].weight < min)
		{
			min = huf_tree[i].weight;
			* s1 = i;
		}
		huf_tree[* s1].parent=1;

	min = ULONG_MAX;//赋值无穷大正数
	for(i = 0; i < n; i++)
		if(huf_tree[i].parent == 0 && huf_tree[i].weight < min)
		{
			min = huf_tree[i].weight;
			* s2 = i;
		}
}

接着需要写一个构造哈夫曼树的函数。其实该函数思路很简单，循环待操作符号节点个数的次数，并且每次都是在待操作节点中找到频度（也就是权值）最小的两个节点，将其加入树中。于是利用之前的Find2Min(huf_tree, i, &s1, &s2);函数可以很方便地实现。

//建立哈夫曼树
//char_sum即出现符号的种类数目；node_num即哈夫曼树的最大节点数目
void BuildTree(HufNode *huf_tree, unsigned int char_sum, unsigned int node_num)
{
	unsigned int i;
	int s1, s2;
	for(i = char_sum; i < node_num; i++)
	{
		Find2Min(huf_tree, i, &s1, &s2);
		huf_tree[s1].parent = huf_tree[s2].parent = i;
		huf_tree[i].left_child = s1;
		huf_tree[i].right_child = s2;
		huf_tree[i].weight = huf_tree[s1].weight + huf_tree[s2].weight;
	}
}

不难预想到，我们在获得排序完毕的哈夫曼树之后，需要对其进行编码，我们同样出于封装的考虑，写一个函数void HufCode来完成此功能。我们只要调用它，并传入排序成哈夫曼树的完成的*tmp_nodes以及待编码的符号总数即可。最终，会把每个节点的编码结果放入节点的.code变量存放。这里我们对出现的符号种类的节点遍历，分别以这些节点为起点，自下而上检测左右关系来编码，具体实现如下。

//对完成排序的哈夫曼树进行编码
void HufCode(HufNode *huf_tree, unsigned char_sum) //char_sum为出现符号种类数
{
	//定义略去
	for(i = 0; i < char_sum; i++)
	{
		index = 256-1;
		for(cur = i, next = huf_tree[i].parent; next != 0;
			cur = next, next = huf_tree[next].parent)
			if(huf_tree[next].left_child == cur)
				code_tmp[--index] = '0';
			else
				code_tmp[--index] = '1';
		huf_tree[i].code = (char * )malloc((256-index) * sizeof(char));
		strcpy(huf_tree[i].code, &code_tmp[index]);
	}
	free(code_tmp);
}

b. 压缩文件

初始化统计表频度

开辟Node *tmp_nodes的256个Node单位的内存空间，用于存储字符频度的统计表。开辟空间后随即进行初始化。

Node *tmp_nodes =(Node * )malloc(256*sizeof(Node)); //为字符频度统计表分配内存空间
for(i = 0; i < 256; i++)
{
  tmp_nodes[i].weight = 0;
  tmp_nodes[i].uch = (unsigned char)i;
}

读入文件并统计频度

这里使用C语言中的FILE中的fread函数，从*infile中一字节一字节地读入符号存入(char * )&temp_char中，边读边更新统计表。读完后接下来就对temp_char的这段内存空间里的符号操作即可

FILE *infile, *outfile;
unsigned char temp_char; //存储读入的字符
unsigned long file_len = 0;	//文件字节数
infile = fopen(ifname, "rb");
if (infile == NULL)
  return -1;
fread((char *)&temp_char, 1, 1, infile);
while(!feof(infile))
{
  tmp_nodes[temp_char].weight++; //统计表中相应符号频度更新
  file_len++;			//统计文件字节数
  fread((char * )&temp_char, 1, 1, infile);
}
fclose(infile);

对统计表频度排序

这里采用冒泡排序对统计表中的 Node 实例们进行从大到小排序。然后找到第一个频度为0的Node，其索引下标即为出现的符号种类数目。

for(i = 0; i < 256-1; i++)
    for(j = i+1; j < 256; ++j)
        if(tmp_nodes[i].weight < tmp_nodes[j].weight)
        {
            node_temp = tmp_nodes[i];
            tmp_nodes[i] = tmp_nodes[j];
            tmp_nodes[j] = node_temp;
        }
for(i = 0; i < 256; i++)
    if(tmp_nodes[i].weight == 0)
        break;
char_sum = i;

建立哈夫曼树进行编码

首先给HufNode *类型的huf_tree指针数组开辟空间，共2 * char_sum - 1个节点，并根据统计表对出现的符号的节点进行初始化。

然后调用

//初始化树节点
node_num = 2 * char_sum - 1;
huf_tree = (HufNode * )malloc(node_num * sizeof(HufNode));
for(i = 0; i < char_sum; i++)
{
  huf_tree[i].uch = tmp_nodes[i].uch;
  huf_tree[i].weight = tmp_nodes[i].weight;
  huf_tree[i].parent = 0;			//初始化节点
}
free(tmp_nodes);
//将以上节点全部设置为待加入节点
for(; i < node_num; i++)
  huf_tree[i].parent = 0;

BuildTree(huf_tree, char_sum, node_num);		//建立哈夫曼树
HufCode(huf_tree, char_sum);				//对树进行编码

写文件

首先要写入原始数据的符号种类数目，fwrite((char *)&char_sum, 4, 1, outfile);,因为char_sum是存储为int类型，故占4个字节。然后将哈夫曼编码表写入文件，即.uch和.weight变量对。接着写入文件的长度file_len，大小为4字节。

接下来我们再一次扫描目标文件，这一次每读入一个符号就查表编码。这有一个难点，考虑到哈夫曼编码是变长码，理论上需要按照bit为单位操作；而实际上计算机中变量存储或者文件读写的最小可操作单位都是字节。因此这里我们借助字符类型数组char code_buf[256] = "\0";，每次编码都将码子先并入该字符数组strcat(code_buf, huf_tree[i].code);。

具体实现中，我们使用while循环直到文件读完。在while循环中，每一次我们都读入一字节符号，将其编码存入 code_buf 数组；每当code_buf中字符长度大于8时，获取数组中的前八位，将其对应的ASCII码所对应的字符存入输出文件中，再将整个字符串前移八位，strcpy(code_buf, code_buf+8);。一直循环该操作，直至code_buf字符长度小于8或为0，然后再次读入符号。若长度最终为0，则写入完毕。若不为0，则将其不足的位数补0，写入到输出文件最后。其中核心部分，也就是每8位输出的转换过程如下。

temp_char = '\0';
for(i = 0; i < 8; i++)
{
  temp_char <<= 1; //左移一位
  if(code_buf[i] == '1')
      temp_char |= 1; //与1按位异或
}
fwrite((char *)&temp_char, 1, 1, outfile);

c. 解压文件

压缩所得文件起始即记录了原文件中字符的种类数，获得后可知之后的多少字节中存储了哈夫曼树的编码信息，按照压缩的格式读取信息后，可以还原出编码后的哈夫曼树，即编码表可知。再向后读取，可得文件中字符的总数，即文件的总长度。

此时，压缩文件中剩余的信息即为编码信息，将其逐位读入后，按照编码表翻译为原来的字符，写入输出文件中，即可得到原文件。需要注意的是，在解码过程中，每次成功解码后将一计数器加一，用于统计解码数是否到达原文件的字符长度，当长度到达后，舍弃压缩文件中剩余位数，完成写入，其目的为防止原先压缩过程中可能存在的补零操作所造成的影响。

2. 算数编码

设置功能类class Arithmetic，成员如下：

string FileAddress; //操作对象文件地址
int TotalNumber = 0;  //记录总的bit数
int NumList[2] = {0};   //存储0和1出现的次数
long double ProbaList[2] = {0.0};   //存储0和1出现的概率
long double P[2] = {0.0};     //存储0和1概率区间的下限
Arithmetic();   //构造函数
void open(string input);
void Press();   //压缩文件
void Decode(string sourcefile, string dstfile); //解压文件

以字节为单位读入，并将其分割成bit串形式

read.read((char*)InChar, sizeof(unsigned char));    //读第一个字节
	while (!read.eof())   //未读到末尾继续循环
	{
		TotalNumber += 8;   //每读入一个字符，总bit数加8
		BitList[0] = (* InChar & 0x80) == 0x80 ? 1 : 0;
		BitList[1] = (* InChar & 0x40) == 0x40 ? 1 : 0;
		BitList[2] = (* InChar & 0x20) == 0x20 ? 1 : 0;
		BitList[3] = (* InChar & 0x10) == 0x10 ? 1 : 0;
		BitList[4] = (* InChar & 0x08) == 0x08 ? 1 : 0;
		BitList[5] = (* InChar & 0x04) == 0x04 ? 1 : 0;
		BitList[6] = (* InChar & 0x02) == 0x02 ? 1 : 0;
		BitList[7] = (* InChar & 0x01) == 0x01 ? 1 : 0;    //将字节分割成bit形式

计算文件中bit0和bit1的总数量和各自的概率

ProbaList[0] = long double(NumList[0]) / TotalNumber;    //计算0和1出现的概率
ProbaList[1] = long double(NumList[1]) / TotalNumber;

P[0] = 0;    //计算0和1概率区间的下限
P[1] = ProbaList[0];   

对一定长度L的符号串进行编码，并将数据写入压缩后文件中。然后从压缩文件中读入数据，并还原成长度为L的符号串输入至解压文件中

for (int i(0); i < N; i++)
{
	if (count == 0)		break;  //如果已经读完文件，则退出循环
	for (int j(0); j < 8; j++)
	{
		if (temp >= P[1])
		{	count -= 1;
			OutList[j] = 1;
			temp = (temp - P[1]) / ProbaList[1];				
		}
	else
	{		count -= 1;
			OutList[j] = 0;
			temp = (temp - P[0]) / ProbaList[0];
	}
}

算法的流程图如下。

算数编码流程图

3. LZ-78编码

a. 设计功能类

LZ-78编码的核心就是编码和解码中构造一个字典，通过字典的段号与最后一位字符来构造码字。因此这里将编码（或解码）这一事件封装成一个class类。类中有一个struct Dictionary变量，该变量存储一段符号串单元的字典元，其中依次包含了：

• unsigned short preIndex：无符号短整型，长2字节，存储符号串的前缀的段号；
• unsigned char lastChar：无符号字符型，长1字节，存储符号串末尾字符；
• unsigned int Index：无符号整型，存储符号串的字典元在字典序列中的段号；
• vector<unsigned char> stringInDic：无符号字符型组成的vector容器变量（相当于字符串），用于存储完整的该符号串。

另外，class LZ78中还写了两个重要的函数：

• 函数 IfStringInDic： 返回bool类型值，表示当前符号串是否已经在字典中出现过。该函数要求传入vector<Dictionary*>类型的变量，即编码中的字典和对应的vector（相当于字符串）。同时，传入的无符号整型Index是引用传递，这是为了让函数的执行结果能传递到外面的preIndex上，即找到并存储前缀的段号。该函数用于编码阶段；
• 函数 FindPreString： 返回无符号字符类型的vector变量（相当于字符串）。要求传入字典和前缀数值。该函数用于解码阶段。

整体的编码和解码使用的就是 函数 lz_compress 和 函数 lz_decompress。这两个函数通过调用之前的两个重要的函数，能够简化其代码，最终实现LZ78的解码和编码。

class LZ78
{
public:
    struct Dictionary //设置一个动态字典的单元
    {
        unsigned short preIndex; //2字节,前缀段号
        unsigned char lastChar; //最后一位字符
        unsigned int Index; //序列段号
        vector<unsigned char> stringInDic; //完整符号串
    };
    void lz_compress(string originfile); //压缩文件
    void lz_decompress(string sourcefile, string dstfile); //解压文件
private:
    bool IfStringInDic(vector<Dictionary*> DataDic, vector<unsigned char> CurrentString, unsigned int &Index);
    //判断字符串是否在字典中
    vector<unsigned char> FindPreString(vector<Dictionary*> DataDic, unsigned int preindex);
    //找到并返回前缀字符串
};

b. 主程序调用测试

借助前面定义的功能类，只要实例化LZ78 document;，就可以调用document.lz_compress和document.lz_decompress来对传入的文件进行压缩和解压。在测试时，也引入了clock( )来测试运行的时间，并通过cout<<来输出运行中的提示。基础代码如下所示。

int main(int argc, const char * argv[]) {
    LZ78 document;
    document.lz_compress("/Users/xrosheart/Desktop/news.txt");   //压缩文件
    document.lz_decompress("/Users/xrosheart/Desktop/news.txt.lz", "/Users/xrosheart/Desktop/test.txt");
    getchar();
    return 0;
}

c. 功能类函数实现

1. 函数 lz_compress

首先是 处理文件的读写。这里不同于之前哈夫曼编码，这里 采用了C++风格的fstream来进行文件读写 的操作。这也算是小组合作的好处之一，能够相互学习不同的编写方式。

需要注意的是，在open操作时，要设置为ios::in|ios::binary，这是为了以二进制方式打开文件。要知道，由于历史原因，Windows 操作系统是用 两个字符\r\n来表示换行符的；而Unix操作系统却是用 单个字符\n来表示换行符 的。虽然无论是否指定二进制方式打开文件，读写的最小单位都是字节，但是在创建文件流时，如果指定了以ios::binary方式打开，那么换行符就是单字符的；否则，就采用Windows操作系统的双字符。

ifstream read;
read.open(originfile, ios::in|ios::binary);
if (!read )
{
		cout << "文件读取错误" << endl << endl;
		return;
}

ofstream write;
write.open(originfile + ".lz", ios::out|ios::binary);
if (!write)
{
		cout << "输出文件不能建立(.lz)" << endl;
}

打开文件之后读入目标文件时，我们使用ifstream的read函数进行操作，每次读入一字符，也就是一字节的长度，即8位二进制码。同样地，输出操作时，我们使用ofstream的write函数进行对文件的写入。每次写入3字节，也就刚好把 Dictionary 类型的前两个变量，即 preIndex 和 lastChar 写入。那么在后面的解码操作时，读写也是一样的方式，只是该方式的逆操作。

//读入字符
unsigned char *now = new unsigned char;
read.read((char*)now, sizeof(unsigned char));
//输出压缩结果
Dictionary *currentInfo = new Dictionary;
write.write((char*)currentInfo,3);

接下来就是 边读入边建立字典编码的过程 了。这里首先要分两类，即第一次读入和接下来的读入，这是为了对于文件是否为空的操作。我们这里直接对接下来的读入进行分析。因为是边读入边建立字典，因此我们使用一个while循环包含了这些操作，涉及的变量如下所示。

//大循环外
vector<Dictionary*> DataDic;    //使用vector建立字典，单元为后面的currentInfo
//大循环内
unsigned char *now = new unsigned char; //用于读取的字符
unsigned char *reallast = new unsigned char; //一组字符串除去已出现的前缀的末尾字符
vector<unsigned char> CurrentString; //当前字符串
unsigned int index = 0;  //字符串存在在字典中的位置， 初始设为0
Dictionary *currentInfo = new Dictionary;   //存储到字典单元中，使用动态指针，便于读写

我们使用函数 IfStringInDic 来作为do ... while的条件，每次找到一组新出现的字符串，然后前缀段号也由该函数通过引用传递到index变量中。而末尾字符也就存到*reallast指向的空间。最后把这些信息存入到字典单元*currentInfo中，然后将字典单元压入字典（vector）中，即DataDic.push_back(currentInfo);。每次都输出*currentInfo的前三字节到压缩输出文件中，也就是需要到码字了。

2. 函数 lz_decompress

该部分实际上与前面类似，不过会简单许多。同样都是建立字典，如果说压缩是将原文件转变为struct Dictionary然后输出 preIndex 和 lastChar 作为码字写入压缩文件；那么解压就是将压缩文件的码字的 preIndex 和 lastChar 转变为struct Dictionary，然后输出字典的 stringInDic。实际上就是互为逆过程。与之前不同的是，这里的采用的是vector<Dictionary> DataDic;和DataDic.push_back(*now);。这是因为指针类型的 vector 会导致码字解码的丢失，因此采用传统的 vector 形式。其中利弊会在优化中指出。

3. 函数 IfStringInDic 和 函数 FindPreString

这两个函数其实都比较简单。实际上就是对字典的遍历操作，但这两个函数中有一点区别，函数 IfStringInDic 中建立的 DataDic 是 Dictionary* 类型的vector，而函数 FindPreString 中建立的 DataDic 是 Dictionary 类型的vector。这两者的区别就在于遍历查找的速度差别。

4. 优化

实际上优化的点就在于数据结构的选择，即vector的单元中选择的单元类型是 Dictionary* 还是 Dictionary。在测试中发现，vector<Dictionary*>比vector<Dictionary>的查找要快了不少，但前者的存储空间调用更加负责，在解码的时候会产生码字流失现象。因此只在压缩中采取了前者的数据结构，而在解压中采用了后者的传统结构。

四、实验拓展与编码操作

实验对实现的哈夫曼编码和LZ-78编码进行了整合，即可以在一个程序下进行两种编码方式的切换选择，其简易操作界面展示如下。

1.打开项目，打开main.cpp文件并运行程序，可以看到如图的简易操作界面，上面提示我们选择编码方式，待选项有：选项1，哈夫曼编码；选项2，LZ-78编码。

图1 运行操作界面

图2 哈夫曼编码压缩txt

图3 哈夫曼编码解压txt

2.选择编码方式，我们先选择哈夫曼编码进行测试，即输入1，然后会车。接下来操作界面会提示请输入您的选项(Q/C/D):，其中Q表示退出程序，C表示编码压缩，D表示解码解压。这里我们先选择压缩，即输入C然后回车，如图2所示。

3.输入源文件和目标文件路径。在步骤2键入C后，会提示[源文件]:。这里既可以输入绝对路径（如E://user/…），也可以是相对路径（如图2）。输入完后，又会提示[目标文件]:，操作同上。

4.步骤3完成后就会开始压缩。这里是把目标文件news.txt压缩成news.txt.huf，同时程序会对压缩过程进行计时。如图3所示，这次 哈夫曼编码压缩txt用时13/ms。

5.接着对刚刚产生对压缩文件进行解压。我们选择1，也就是哈夫曼编码，再选择D，然后输入源文件news.txt.huf和解压文件result.txt，进行解压，结果如图4所示。可以看到这次 哈夫曼编码解压txt用时10ms。另外也可以从图5和图6的对比中看到，哈夫曼编码压缩和解压后的文件和原文件一模一样。

图4 news.txt 截图

图5 result.txt 截图

图6 result1.txt 截图

6.使用哈夫曼编码对news.docx进行压缩，压缩为news.docx.huf。操作过程与结果如图8所示，可见这次 哈夫曼编码压缩docx用时659ms。接着再对news.docx.huf进行解压，得到result.docx，其操作过程和结果如图9所示，可见这次 哈夫曼编码压缩docx用时239ms。

图7 哈夫曼编码压缩docx

图8 哈夫曼编码解压docx

7.接下来对LZ-78编码进行测试。使用LZ-78编码把news.txt压缩为news.txt.lz，然后再把news.txt.lz解码为result1.txt，通过图9可见，生成文件与原文件一模一样。压缩过程如图10所示，解压过程如图11所示，可见这次LZ-78编码txt用时24s，解压txt用时49s。其x

图9 LZ-78编码压缩txt

图10 LZ-78编码解压txt

以上就是整合的两种编码方式简易操作界面的操作过程，通过使用C++的clock( )进行计时来记录编码解码的用时，通过对前后文件大小的变化衡量编码效率。该过程也可以进行哈夫曼和LZ-78的编码效果对比。

五、编码结果与性能分析

1. 哈夫曼编码

操作环境： Windows10，Visual Studio 2017。

测试用例： 使用了老师所给的17KB的news.txt文件、531KB的news.docx，以及自己随机找的96KB的little.docx和17.6M的large.docx，包括了 txt、docx和mp4三种文件类型，和4个不同数量级的文件大小，小到17KB，大到30.2M，测试范围涵盖全面。

测试数据： 主要测试压缩前后文件大小，计算压缩率；另外记录编码和解码用时。具体数据如下所示。

原始文件	news.txt (17KB)	little.docx (96KB)	news.docx (531KB)	large.docx (17.6M)	test.mp4 (30.2M)
压缩文件	news.txt.huf (10KB)	little.docx.huf (96KB)	news.docx.huf (531KB)	large.docx (17.6M)	test.mp4.lz (30.2M)
压缩率	58.8%	1	1	1	1
编码用时	10ms	133ms	659ms	24164ms	44s
解码用时	4	63ms	239ms	7742ms	15s

可见编写的哈夫曼编码适用范围广，对于txt、docx、mp4视频等文件均适用，而且编码解码速度较快。不足之处在于，虽然对于txt文件有着优秀的压缩率，但对于docx、mp4这类较大较负责的文件，几乎无压缩效果。这点也是需要后期有机会改进的。

2. LZ-78编码

该算法最初在macOS Xcode 10.1上编写调试，初步效果对于txt和较小的docx文件较好。出于在算法设计中提到的，译码时采用指针类型vector会导致码字丢失，故在解码过程中采用了传统的vector数据结构，速度较慢。这也在测试数据中明显地体现出来了：编码用时比解码用时少，编码速度较快而解码速度稍慢。

原始文件	news.txt (17KB)	little.docx (98KB)
压缩文件	news.txt.lz (13KB)	little.docx.lz (122KB)
压缩率	76.5%	1.24
编码用时	44ms	30ms
解码用时	275ms	202s

然而，或许是因为macOS类Linux系统与Windows系统的差别，二者对于指针存储结构的处理能力差别较大。因此在win10的 Visual Studio 2017上效果明显劣于macOS上的表现。

原始文件	news.txt (17KB)	little.docx (96KB)
压缩文件	news.txt.huf (13KB)	little.docx.lz (96KB)
压缩率	76.5%	1.24
编码用时	24s	2547s
解码用时	47s	/

可见 此处实验使用的LZ-78实现算法更适合在macOS系统上使用。从这其中发现的 系统差别对于编码性能的影响 也算是实验的意外收获了。

3. 算数编码

对96KB的news.txt文件进行算数编码，压缩结果如图10所示，压缩总 bit 数为 137872 bit，其中0的概率为 54.3%，1的概率为 47.3%。压缩用时271ms，解压用时1ms。

图11 编码字符串1字节news.txt结果

由于未能在代码中解决浮点数在运算和存储中精度的不确定性，因此编码效率无法到达100%，会产生一定的无码，因而无法压缩docx文档。

另外，在压缩txt文件时，随着待编码字符串长度的增加，对浮点数精确度要求更高，编码准确率降低，以下显示待编码字符串长度为1字节、2字节、3字节时的压缩情况。

图12 编码字符串1字节时情况

图13 编码字符串2字节时情况

图14 编码字符串3字节时情况

六、问题总结与体会

以上信源编码的实现需要深刻地理解 哈夫曼编码、LZ编码与算数编码 的原理，并且明白了不同编码的实现方式。一开始时，由于对于这些编码方式的理解并不深刻，对于该如何用程序实现代码也没有思路，所以进展比较缓慢。于是尝试首先理解这些编码的基本编码原理，再尝试利用C++代码实现这些编码的字典，一步步走，最后得以写出完整的编码。

在实现哈夫曼编码的过程中，最初不知道怎样将文件进行读入或者读出，所以最初实现的编码方式是通过指令台输入要编码的信源序列，并且采用一个数组来保存它，对它进行读取扫描来实现哈夫曼树或者建立字典，但是由于数组长度有限，而且希望以文件格式输入输出，所以最开始实现的程序需要在很大程度上进行改进；此外，在实现哈夫曼树的过程中时，当一步步将概率合并以将哈夫曼树走到上层之后，如何一步步返回到下层又成了问题。

在实现LZ-78编码的过程中，遇到的两个主要问题就是如何实现bit单位的变长码字以及如何存储字典数据。在查阅资料以及不同数据结构的尝试下，找到了较优的数据结构，即采用指针单位的vector数据类型。另外对于变长码字，由于bit单位的操作较为负责，退而求其次，采用了一个上限长度，不过缺点在于造成了一定的冗余。在macOS的Xcode移植到win10的VS上时，发现了 系统与编译器对编码算法性能的巨大影响。通过查阅资料了解了VS和Xcode的性能比对后，将 原因归结于系统的差别——类Linux系统和windows系统在存储方式的差别对指针类型存储结构的操作性能差异。

在实现算数编码的过程中，最初是对每一个字符进行编码。由于$ASCII$码对应的长度为一个字节而许多中文字符对应的长度为两个字节，因此单纯对一个字符进行编码会造成不同字符长度不一致的问题。最后决定对文件中一个字节一个字节读入，然后对 8位比特的256种不同的可能性 进行编码。由于算数编码需要对不同的字符的概率进行映射，而一个文本中8位不同的比特可能组合会高达数十种，造成有些概率非常接近，最终精度不够，编码正确率不够高。最后采取的方式为将文件分割成比特形式，统计比特0和比特1出现的概率并在此基础上编码，提升了准确率。

最后，将哈夫曼编码和LZ-78整合在一起的过程也遇到了一些阻力：一方面是对VS不够了解，另一方面对于整合用的main.cpp的设计。不过有了之前编码实现的提示，也都比较顺利地解决了困难，最终做出了一个 简易的操作界面，实现了 哈夫曼编码和LZ-78的选择编码。

https://blog.csdn.net/u010653908/article/details/53994021

 

response设置编码的三种方式以及比较

2017年01月03日 14:12:46 Listen_Silently 阅读数：18021

在很多场合会发现我们输出的中文是乱码，这主要可能有两方面的原因：

一个是浏览器的解析方式，另一个是我们服务器端返回数据的方式。只要我们保证浏览器的解析方式和我们回显的数据的编码格式是一致的，基本上乱码问题就可以得到解决。大多数数情况下，浏览器的默认编码方式是utf-8，因此我们只要设置服务器返回的数据的编码方式也是utf-8即可。

 

在Java后台的Action代码或者Servlet代码中用response的方法来设置输出内容的编码方式，主要有以下三个方法：


　　1、response.setCharacterEncoding("UTF-8");


　　2、response.setContentType("text/html;charset=UTF-8");


　　3、response.setLocale(new java.util.Locale("zh","CN"));
下面对以上3种方法进行差异分析：
      第一种方法只能用来设置out输出流中所采用的编码，但是它的优先权最高，可以覆盖后面两种方法中的设置；


      第二中方法可以设置out输出流中字符的编码方式，也可以设置浏览器接收到这些字符后以什么编码方式来解码，它的优先权低于第一种方法，  
但高于第三种方法；这种方法通知response以UTF-8输出和浏览器以UTF-8打开。即等价于

response.setHeader("content-type", "text/html;charset=UTF-8");通知浏览器以utf-8解析

和response.setCharacterEncoding("UTF-8");注意第二句句需要写在PrintWriter out = response.getWriter();的前面，如果拿到字符流后再设置编码是没有用的。


      第三种方法只能用来设置out输出流中字符的编码方式，但是它的优先权最低，在已经使用前两种方法中的一个设置了编码方式以后，它就被覆盖而不起作用了。

 

response字符编码解决中文乱码

阅读数 3664

response.setContentType("text/html;charset=UTF-8");有二层含义：1_服务器按照UTF-8的方式编码2_浏览器按照UTF-8的方式解码以上只针对非英文和...博文来自： qq1164014750

request、response 中文乱码问题与解决方式

阅读数 1万+

request、response中文乱码问题与解决方式request乱码指的是：浏览器向服务器发送的请求参数中包含中文字符，服务器获取到的请求参数的值是乱码；response乱码指的是：服务器向浏览器...博文来自： dingjingchao的博客

servlet中response和request的字符编码问题

阅读数 1万+

javaweb中的中文乱码问题。博文来自： 断肠人在刷牙

SpringMVC之使用ResponseEntity

阅读数 4万+

1、Post请求一般情况下，在非必须的情况下，使用Jquery实现post请求，而后台返回一般都需要手动封装ResponseUtil，和使用@ResponseBody注解来实现返回。然而我们书上学到的...博文来自： ryelqy的博客

 

response设置编码的三种方式

阅读数 9142

在java后台的Action代码或者Servlet代码中用response的方法来设置输出内容的编码方式，有以下三个方法：　　1、response.setCharacterEncoding("UTF-...博文

request与response的编码问题

阅读数 4307

request.setCharacterEncoding（）：是设置从request中取得的值或从数据库中取出的值。   指定后可以通过getParameter()则直接获得正确的字符串，如果不指定，...博文来自： u014007037的专栏

response设置返回的编码

阅读数 1069

varon202=function(req,res,bodyStr){//设置为UTF-8res.writeHead(200,{'Content-Type':'text/javascript;char...博文来自： u010129379的博客

28.ResponseEntity与ResponseBody注解的关系

阅读数 4254

1.ResponseEntity的优先级高于@ResponseBody。在不是ResponseEntity的情况下才去检查有没有@ResponseBody注解。如果响应类型是ResponseEntit...博文来自： YingZiBo的博客

完整的HTTP请求会经历以下过程

阅读数 2万+

一次完整的Http请求，虽然说的是浏览器，但是换成ios，android也是完全没毛病的。原文http://blog.51cto.com/linux5588/1351007当我们在浏览器的地址栏输入w...博文来自： gcs的博客

response设置编码的三种方式以及比较 - 勿忘初心 方得..._CSDN博客

11-9

 

response设置编码的三种方式 - 未干的咸鱼 - CSDN博客

5-11

response设置编码的三种方式以及比较 01-03 阅读数 1万+ 在很多场合会发现我们...博文 来自: 勿忘初心 方得始终 response设置编码的方式 11-19 阅读数 1万...

request、response揭秘（备java基础，servlet，jsp，javaee）

掌握Request对象的作用，期属性，response特点。学院讲师：任亮

完整的http请求会经过哪些步骤

阅读数 3027

Http的header会给我们的请求包装，比如在请求设置中的Accept（xml,text,xhtml,html）域名解析，根据域名找到服务器的IP发起TCP的三次握手建立TCP连接后发起http请求...博文来自： demo_xue的博客

response设置编码的三种方式 - cmingjun - CSDN博客

4-2

response设置编码的三种方式以及比较 01-03 阅读数 1万+ 在很多场合会发现我们...博文 来自: 勿忘初心 方得始终 response设置编码的方式 11-19 阅读数 1万...

response设置响应编码 - 一个被代码耽搁了的法师 - CSDN博客

11-24

 

一次完整的HTTP请求所经历的7个步骤

阅读数 7198

HTTP通信机制是在一次完整的HTTP通信过程中，Web浏览器与Web服务器之间将完成下列7个步骤： 1.建立TCP连接在HTTP工作开始之前，Web浏览器首先要通过网络与Web服务器建立连接，该连接...博文来自： 菜鸟程序猿的博客

request、response 中文乱码问题与解决方式 - dingjing..._CSDN博客

11-14

 

response设置编码 - wakata随记 - CSDN博客

11-7

      是服务器端java程序运行时的输出编码,即服务器端以什么样...response设置编码的三种方式以及比较 - 勿忘初心 方得始终 01-03 1万 在...

SPRING MVC3.2案例讲解--SPRING MVC3的@ResponseBody和ResponseEntity

阅读数 3万+

在传统的开发过程中，我们的控制CONTROLL层通常需要转向一个JSP视图；但随着WEB2.0相关技术的崛起，我们很多时候只需要返回数据即可，而不是一个JSP页面。 SPRINGMVC3的@Respo...博文来自： json20080301的专栏

Response常见方法使用和问题

阅读数 4404

•向客户端输出中文数据用PrintWriter(字符流)发送数据：示例：response.getWriter().write(“中国”);有没有乱码？原因：以默认编码发送数据ISO-8859-1（没有...博文来自： Calo_missile的博客

response字符编码解决中文乱码 - qq1164014750 - CSDN博客

1-11

response设置编码的三种方式以及比较 01-03 1.4万 在很多场合会发现我们输出...来自: 勿忘初心 方得始终 response设置编码的方式 11-19 1.4万 在java后台...

关于response设置字符的问题 - hq091117的博客 - CSDN博客

5-7

response设置编码的三种方式以及比较 01-03 阅读数 1万+ 在很多场合会发现...博文 来自: 勿忘初心 方得始终 response设置编码的方式 11-19 阅读数 1万...

HttpServletResponse编码问题

阅读数 1817

1.HttpServletResponse对象(1).Web服务器收到一个http请求，会针对每个请求创建一个HttpServletRequest和HttpServletResponse对象，向客户端...博文来自： yanyangy_js的专栏

 

response设置返回的编码 - u010129379的博客 - CSDN博客

4-4

response设置编码的三种方式以及比较 01-03 阅读数 1万+ 在很多场合会发现我们...博文 来自: 勿忘初心 方得始终 response设置编码的方式 11-19 阅读数 1万...

response设置响应编码

阅读数 769

1.response.setContentType(“text/html;charset=UTF-8”)不仅发送到浏览器的内容会使用UTF-8编码，而且还通知浏览器使用UTF-8编码方式进行显示。所以...博文来自： 一个被代码耽搁了的法师

response设置编码

阅读数 1285

参考来源：http://hi.baidu.com/wangkuoguang/item/dc64a00e4802bc91a3df43c2response设置编码。     是服务器端java程序运行...博文来自： wakata随记

@ResponseBody 注解设置 utf-8 编码的方式

阅读数 1757

我最终采用的方式：&amp;lt;beanclass=&quot;org.springframework.web.servlet.mvc.annotation.AnnotationMethodHand...博文来自： HeatDeath的博客

Request与Response常用方法总结

阅读数 2187

Request类1.setAttribute()在Request域中存储数据2.setCharacterEncoding()设置请求参数的编码方式,只对post请求有效3.getMethod()获取请...博文来自： hanshangzhi的博客

response.setHeader()下载中文文件名乱码问题

阅读数 2万+

1.HTTP消息头（1）通用信息头即能用于请求消息中,也能用于响应信息中,但与被传输的实体内容没有关系的信息头,如Data,Pragma主要:Cache-Control,Connection,Data...博文来自： liangrockman的专栏

 

浅谈HTTP请求的过程

阅读数 1343

1、详细版1) 浏览器会开启一个线程来处理这个请求，对URL分析判断，如果是HTTP协议，就按照Web方式来处理。2) 调用浏览器内核中的对应方法，比如WebView中的loadUrl方法。3) 通过...博文来自： 筱葭的博客

Spring MVC中的ResponseEntity和ResponseBody的区别

阅读数 4629

1.ResponseEntity的优先级高于@ResponseBody。在不是ResponseEntity的情况下才去检查有没有@ResponseBody注解。如果响应类型是ResponseEntit...博文来自： Mamba28

一个完整的HTTP请求的七个步骤

阅读数 1317

一个完整的HTTP请求，通常有以下七个步骤：1、建立TCP连接2、Web浏览器向Web服务器发送请求命令3、Web浏览器发送请求头信息4、Web服务器应答5、Web服务器发送应答头信息6、Web服务器...博文来自： 当王八遇到羔子的博客

解决HttpServletResponse输出的中文乱码问题

阅读数 12万+

首先，response返回有两种，一种是字节流outputstream，一种是字符流printwrite。申明：这里为了方便起见，所有输出都统一用UTF-8编码。先说字节流，要输出“中国"，给输出流的...博文来自： simon_1的专栏

request与response的字符集编码区别

阅读数 1877

request.setCharacterEncoding(): 设置从request对象中取的值的编码方式。   指定后可以通过getParameter()则直接获得正确的字符串，如果不指定，则默认使...博文来自： Lm的博客

 

response 设置编码格式

阅读数 583

在java后台的Action代码或者Servlet代码中用response的方法来设置输出内容的编码方式，有以下三个方法：　　1、response.setCharacterEncoding("UTF-...博文来自： 蓝魔

response.setHeader()设置下载中文文件名乱码问题

阅读数 1万+

1.HTTP消息头（1）通用信息头即能用于请求消息中,也能用于响应信息中,但与被传输的实体内容没有关系的信息头,如Data,Pragma主要:Cache-Control,Connection,Data...博文来自： 零度的博客专栏

解决response.setHeader()下载中文文件名乱码问题

阅读数 2434

response.setHeader(&quot;Content-Disposition&quot;,&quot;attachment;filename=&quot;+java.net.URLEnco...博文来自： zhangvalue的博客

response响应头设置总结

阅读数 1万+

response博文来自： y41992910的博客

彻底解决Spring MVC 中文乱码 问题

阅读数 25万+

1：表单提交controller获得中文参数后乱码解决方案注意：jsp页面编码设置为UTF-8form表单提交方式为必须为post，get方式下面spring编码过滤器不起效果修改web.xml，增加...博文来自： passport_daizi的博客

 

网页http请求的整个过程

阅读数 8648

这几天看一个讲解一个网页从我们输入地址到显示在我们面前的一个讲解，是我对http又有了一个完整的了解，现在做一下整个流程的记录，虽然不是很详细，但是整个过程是完整的。如果不对，请指正！...博文来自： 养码青年

ResponseEntity 20 80

阅读数 170

博文来自： lph2017的博客

PHP 页面编码声明方法详解(header或meta，解决中文乱码问题)

阅读数 1万+

PHP页面编码声明与用header或meta实现PHP页面编码的区别php的header来定义一个php页面为utf编码或GBK编码php页面为utf编码header("Content-type:te...博文来自： 偶木

设置response.setHeader时，含有中文字符，设置出现错误

阅读数 8171

在设置response.setHeader时，如果含有中文字符，一定要转换成ISO8859-1格式，否则设置的中文会出现错误。   response.setHeader("content-dispos...博文来自： 成大事不在于力量多少，而在能坚持多久。

response.setHeader(...)下载中文文件名乱码问题

阅读数 52

关于中文文件下载的问题，网上的咨询和答疑已经很多，我原来处理下载的代码如下：        response.setHeader(&quot;Content-Disposition&quot;,&qu...博文来自： xixiaoyunyi的博客

 

关于response设置字符的问题

阅读数 219

response设置字符，这个很常见，但是就是遇到设置了也没用的时候都知道一般是response.setContentType(&quot;application/json;charset=UTF-8...博文来自： hq091117的博客

解决 response 中文乱码 ????

阅读数 4347

response.setHeader(&quot;Content-type&quot;,&quot;text/html;charset=UTF-8&quot;);response.setCharact...博文来自： luckyxiaobaiyang的博客

response返回中文乱码

阅读数 1731

       //这句话的意思，是让浏览器用utf8来解析返回的数据        response.setHeader(&quot;Content-type&quot;,&quot;text/htm...博文来自： zhou

response输出乱码问题

阅读数 2260

//这句话的意思，是让浏览器用utf8来解析返回的数据response.setHeader("Content-type","text/html;charset=UTF-8");//这句话的意思，是告诉...博文来自： long_here的专栏

怎么解决输入流和输出流编码问题

阅读数 5905

在java中读取文件时应该采用什么编码？Java读取文件的方式总体可以分为两类：按字节读取和按字符读取。按字节读取就是采用InputStream.read()方法来读取字节，然后保存到一个byte[]...博文来自： 思考、总结、专注

一次完整的http请求处理过程

阅读数 2999

Web服务请求处理步骤一次完整的http请求处理过程1、建立连接：接收或拒绝连接请求2、接收请求：接收客户端请求报文中对某资源的一次请求的过程3、处理请求：服务器对请求报文进行解析，并获取请求的资源及...博文来自： 咻一咻的博客

Response详解

阅读数 5341

1.1. Response概述1.1.1. Response概述Servlet中应该如何向用户输出数据呢？在doGet和doPost方法的参数中，HttpServletRequest代表的是http请...博文来自： 一个技术宅

response介绍及应用、乱码问题解决

阅读数 402

1.  http协议响应数据-response1.1. 响应数据组成1.2. 响应行HTTP/1.1200OK 格式：协议版本+http状态码+状态码含义 1.2.1.  http状态码介绍     ...博文来自： qq_36371449的博客

javaweb中中文乱码解决方法总结之response和request解决方法

阅读数 1万+

javaweb中文乱码解决博文来自： 小芳

response返回中文乱码解决方案

阅读数 4244

response.setCharacterEncoding(&quot;UTF-8&quot;);response.setContentType(&quot;text/html;charset=utf...博文来自： qrne06的博客

response乱码 response.setCharacterEncoding("UTF-8")不生效的原因及解决方法

阅读数 1万+

本文主要讲述response乱码原因及response.setCharacterEncoding("UTF-8")不生效的原因及解决方法一、response乱码1、首先，response返回有两种，一...博文来自： TLMS_的专栏

Python 使用requests时的编码问题

阅读数 1万+

官网说明：ComplianceRequestsisintendedtobecompliantwithallrelevantspecificationsandRFCswherethatcomplianc...博文

response 设置响应头的常用几种方法

阅读数 3305

response 设置响应头的常用几种方法    1.Location  的用法      response.setStatus(302)//临时定向响应码    response.setHeader...博文来自： hanshangzhi的博客

HttpClient设置发送内容的编码格式

阅读数 7940

/** *根据url获取输入流(POST),https,利用HttpClient * *@paramurl *@paramcontent *@paramaccessToken *@return *@t...博文来自： draven1122的博客

【问题解决】HttpClient解析服务器返回的response出现乱码

阅读数 1万+

问题场景最近在用httpClient做网络爬虫的时候，遇到了一个不大不小的问题，当使用HttpGet向指定网址发送请求后，接收到的Response无法正常解析，出现口口？？这样的乱码，编码也考虑到了中...博文来自： 正在加载中

response设置编码的三种方式

阅读数 87

在一个utf-8项目中，调用支付宝的及时到账支付接口，本身的jsp接口是没有问题的。但是用到自己的struts工程中，显示的订单中文名称总是乱码经过多方试验，发现是因为在输出流时没有指定输出的编码方式...博文来自： 微尘的世界

eclipse 性能优化

阅读数 708

eclipse调优 一般在不对eclipse进行相关设置的时候，使用eclipse总是会觉得启动好慢，用起来好卡，其实只要对eclipse的相关参数进行一些配置，就会有很大的改善。 加快启动速度 ...博文来自： 疯狂小强

mybatis一级缓存(session cache)引发的问题

阅读数 3万+

mybatis一级缓存(session cache)引发的问题博文来自： flysharkym的专栏

webService学习（二）—— 调用自定义对象参数

阅读数 3万+

webService学习（二）—— 调用自定义对象参数 本文主要内容： 1、如何通过idea进行webService Client的简单实现（不再使用wsimport的方式，其实是ide帮我们做了...博文来自： 止水的专栏

jsp表单的批量提交

阅读数 1万+

baseBaseLineFormSubmit=function(data){ var startDate=$('#formSdate').datebox('getValue'); va...博文来自： IT小生

Android微信app支付集成步骤详解

阅读数 3847

Android微信app支付集成步骤博文来自： CTSN的博客

将Excel文件导入数据库（POI+Excel+MySQL+jsp页面导入）第一次优化

阅读数 5万+

本篇文章是根据我的上篇博客，给出的改进版，由于时间有限，仅做了一个简单的优化。相关文章：将excel导入数据库2018年4月1日，新增下载地址链接：点击打开源码下载地址十分抱歉，这个链接地址没有在这篇...博文来自： Lynn_Blog

编写C语言版本的卷积神经网络CNN之一：前言与Minst数据集

阅读数 3万+

卷积神经网络是深度学习的基础，但是学习CNN却不是那么简单，虽然网络上关于CNN的相关代码很多，比较经典的是tiny_cnn（C++）、DeepLearnToolbox（Matlab）等等，但通过C语...博文来自： tostq的专栏

Hbuider hybrid app开发细节积累

阅读数 2876

1. 搜索框的属性的设置。要虚拟键盘显示“搜索”二字，需满足以下两个条件： （1）设置input属性 type=‘search’ （2）input需在form表单中。 html代码 ...博文来自： 千里马的专栏

Android平台Camera实时滤镜实现方法探讨(五)--GLSurfaceView实现Camera预览

阅读数 2万+

前面有一篇探讨了如何在片段着色器中将YUV数据转换为RGB数据并显示，但采用samplerExternalOES将SurfaceTexture作为OpenGL外部纹理，需要使用GL_TEXTURE_E...博文

关于Arcgis数据导入mdb完成后如何立刻解除mdb的锁定

阅读数 7535

今天尝试博文来自： Sean的专栏

微信支付V3微信公众号支付PHP教程(thinkPHP5公众号支付)/JSSDK的使用

阅读数 17万+

扫二维码关注，获取更多技术分享 本文承接之前发布的博客《 微信支付V3微信公众号支付PHP教程/thinkPHP5公众号支付》必须阅读上篇文章后才可以阅读这篇文章。由于最近一段时间工作比较忙，...博文来自： Marswill

logstash 配置文件编写详解

阅读数 2213

说明 它一个有jruby语言编写的运行在java虚拟机上的具有收集分析转发数据流功能的工具 能集中处理各种类型的数据 能标准化不通模式和格式的数据 能快速的扩展自定义日志的格式 能非常方便的...博文来自： 人生无处不修行

游戏手柄（JoyStick）编程学习笔记（1）

阅读数 1万+

游戏手柄（JoyStick）编程学习笔记（1）最近我开发的一个项目中需要用手柄控制一个二维移动平台的运动，找了些工业用的操作杆，感觉都挺丑的。后来想到打游戏时用的游戏手柄就挺漂亮，就决定试试用游戏手柄...博文来自： Ivan 的专栏

DirectX修复工具增强版

阅读数 202万+

最后更新：2018-12-20 DirectX修复工具最新版：DirectX Repair V3.8 增强版NEW! 版本号：V3.8.0.11638 大小: 107MB/7z格式压缩，189M...博文来自： VBcom的专栏

深度学习（卷积神经网络）一些问题总结

阅读数 12万+

深度卷积网络   涉及问题： 1.每个图如何卷积：   （1）一个图如何变成几个？   （2）卷积核如何选择？ 2.节点之间如何连接？ 3.S2-C3如何进行分配？ 4.16-...博文来自： 江南研习社

数据结构中八大排序算法

阅读数 4163

一、冒泡排序 思想：重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。 时间复杂度：O(n^2) 空间复杂度:O(1) 稳定性：稳定 1...博文来自： tan313的专栏

【CESM】1.2.0环境搭建扩充版

阅读数 4782

上周的时候，CESM的环境基本算是搭建完成了，得益于论坛中很多朋友的帮助，希望写一个尽量完整的搭建指南，供新同学参考。 当然欢迎高手们批评指正。 参考帖：http://bbs.06climate.co...博文来自： a1333888的专栏

Date()方法格式化

阅读数 391

博文来自： 美利坚天朝分部

VS2010 操作Word（一）建立工程

阅读数 1万+

在网上所搜索很多操作Word的都是用VC，VS2010做了一些修改，添加操作的方式和用法都有所变化。 要操作Word必须先添加对应的类，如下图在工程中添加操作类（TypeLib中的 MFC类）： ...博文来自： xiangjianbo127的专栏

servlet+jsp实现过滤器，防止用户未登录访问

阅读数 3万+

我们可能经常会用到这一功能，比如有时，我们不希望用户没有进行登录访问后台的操作页面，而且这样的非法访问会让系统极为的不安全，所以我们常常需要进行登录才授权访问其它页面，否则只会出现登录页面，当然我的思...博文来自： 沉默的鲨鱼的专栏

VS下生成与配置静态库与动态库（一）

阅读数 2万+

此处仅以VS2010为例，详细说明一下如何在VS环境下生成和使用C++的静态库与动态库。Qt下生成和使用静态和动态库后续再讲。 本文仅供初学者参考，如果有问题欢迎大家指正。        首先简单地理...博文来自： luyan的博客

关于SpringBoot bean无法注入的问题（与文件包位置有关）

阅读数 24万+

问题场景描述整个项目通过Maven构建，大致结构如下： 核心Spring框架一个module spring-boot-base service和dao一个module server-core 提供系统...博文来自： 开发随笔

强连通分量及缩点tarjan算法解析

阅读数 64万+

强连通分量： 简言之 就是找环（每条边只走一次，两两可达） 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点）   定义： int Ti...博文来自： 九野的博客

SQL Server之查询检索操作

阅读数 6555

SQL Server查询和检索操作。 一道例题学会查询和检索操作： 1、在SQL SERVER 2008上附加teaching数据库,其中三张表的含义解释如下： 学生表dbo...博文来自： J.Anson的博客

jquery/js实现一个网页同时调用多个倒计时(最新的)

阅读数 51万+

jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自： Websites

Android通过代码模拟物理、屏幕点击事件

阅读数 12万+

本文讲的是通过使用代码，可以控制手机的博文来自： 其实并不难,是你太悲观

cocos2D-X源码分析之从cocos2D-X学习OpenGL（1）----cocos2D-X渲染结构

阅读数 1万+

cocos2D-X 3.0渲染结构代码讲解，也是cocos2D-X源码讲解系列文章和从cocos2D-X学习OpenGL系列文章的开始...博文来自： 手机游戏开发学习笔记

连续特征离散化和归一化

阅读数 5万+

连续特征进行离散化处理。博文来自： hero_fantao的专栏

Android中折线图实现方法（各类图表实现）

阅读数 1万+

需要外部资源：mpandroidchartlibrary-2-1-6.jar 下载地址： http://download.csdn.net/detail/u011084603/9369473效果图...博文来自： 张平的专栏

设计制作学习 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型

mysql关联查询两次本表 native底部 react extjs glyph 图标 大数据学习路线以及资料 学习大数据的经历以及规划

Listen_Silently

关注

原创

33

粉丝

38

喜欢

103

评论

12

等级：

 

访问：

 

25万+

积分：

 

1696

排名：

 

4万+

勋章：

 

最新文章

• python读取csv文件中文乱码
• linux NFS服务器的安装与配置
• redhat6.6的nfs服务端配置
• Oracle创建表空间、创建用户以及授权
• win10系统安装oracle11g时遇到INS-13001环境不满足最低要求

个人分类

• SSH框架9篇
• JVM2篇
• JAVA基础高级4篇
• Java线程安全1篇
• 网络协议5篇
• 云计算与虚拟化2篇
• JAVA NIO1篇
• SpringMVC2篇
• Mybatis1篇
• JAVA1篇
• 数据库3篇
• java纠错1篇
• 网络安全1篇
• 计算机网络3篇
• 虚拟机1篇
• linux5篇
• 华为网络竞赛2篇
• 操作系统1篇
• 前端1篇

展开

归档

• 2018年1月1篇
• 2017年10月2篇
• 2017年9月7篇
• 2017年8月6篇
• 2017年7月3篇
• 2017年6月10篇
• 2017年5月4篇
• 2017年4月2篇
• 2017年3月6篇
• 2017年1月1篇
• 2016年12月17篇
• 2016年11月1篇
• 2016年9月2篇
• 2016年3月1篇
• 2015年11月1篇

展开

热门文章

• 如何将dmp文件导入到自己的oracle数据库中

  阅读数 128691

• response设置编码的三种方式以及比较

  阅读数 18002

• openstack创建一个虚拟机的过程

  阅读数 14545

• tomcat与jvm的关系分析

  阅读数 11546

• 如何让HashMap变成线程安全的？

  阅读数 11110

最新评论

• 自己总结的基于ssh框架的网站的简...

  qq_42287104：感觉楼主的流程解释更加通俗易懂,看别人的流程解释看不懂....

• tomcat与jvm的关系分析

  qq_39329226：哥 今天我又来了

• tomcat与jvm的关系分析

  qq_39329226：哥 我想问 tomcat 线程 和java 线程是什么关系 比方说 一个请求 tomcat 开启了一个线程,这个tomcat线程是怎么让 jvm 产生对应的线程并与之交互的了

• 如何将dmp文件导入到自己的ora...

  u011047145：补充下：有可能遇到导入用户(test)没权限问题， 1、grant sysdba to test; 2、grant imp_full_database to test;

• 如何将dmp文件导入到自己的ora...

  tomcoding：可以自己写程序导入的，百度tomcoding，上面有dmp文件的格式和导入数据的程序源代码，免费下载

 

CSDN学院

CSDN企业招聘

kefu@csdn.netQQ客服

客服论坛400-660-0108

工作时间 8:30-22:00

关于我们招聘广告服务 网站地图

百度提供站内搜索 京ICP备19004658号

©1999-2019 北京创新乐知网络技术有限公司

经营性网站备案信息网络110报警服务

北京互联网违法和不良信息举报中心

中国互联网举报中心家长监护版权申诉

•  

  3

•  
•  
•  
•  
•  

 

 

一、ASCII 码

我们知道，计算机内部，所有信息最终都是一个二进制值。每一个二进制位（bit）有0和1两种状态，因此八个二进制位就可以组合出256种状态，这被称为一个字节（byte）。也就是说，一个字节一共可以用来表示256种不同的状态，每一个状态对应一个符号，就是256个符号，从00000000到11111111。

上个世纪60年代，美国制定了一套字符编码，对英语字符与二进制位之间的关系，做了统一规定。这被称为 ASCII 码，一直沿用至今。

ASCII 码一共规定了128个字符的编码，比如空格SPACE是32（二进制00100000），大写的字母A是65（二进制01000001）。这128个符号（包括32个不能打印出来的控制符号），只占用了一个字节的后面7位，最前面的一位统一规定为0。

二、非 ASCII 编码

英语用128个符号编码就够了，但是用来表示其他语言，128个符号是不够的。比如，在法语中，字母上方有注音符号，它就无法用 ASCII 码表示。于是，一些欧洲国家就决定，利用字节中闲置的最高位编入新的符号。比如，法语中的é的编码为130（二进制10000010）。这样一来，这些欧洲国家使用的编码体系，可以表示最多256个符号。

但是，这里又出现了新的问题。不同的国家有不同的字母，因此，哪怕它们都使用256个符号的编码方式，代表的字母却不一样。比如，130在法语编码中代表了é，在希伯来语编码中却代表了字母Gimel (ג)，在俄语编码中又会代表另一个符号。但是不管怎样，所有这些编码方式中，0--127表示的符号是一样的，不一样的只是128--255的这一段。

至于亚洲国家的文字，使用的符号就更多了，汉字就多达10万左右。一个字节只能表示256种符号，肯定是不够的，就必须使用多个字节表达一个符号。比如，简体中文常见的编码方式是 GB2312，使用两个字节表示一个汉字，所以理论上最多可以表示 256 x 256 = 65536 个符号。

中文编码的问题需要专文讨论，这篇笔记不涉及。这里只指出，虽然都是用多个字节表示一个符号，但是GB类的汉字编码与后文的 Unicode 和 UTF-8 是毫无关系的。

三. Unicode

正如上一节所说，世界上存在着多种编码方式，同一个二进制数字可以被解释成不同的符号。因此，要想打开一个文本文件，就必须知道它的编码方式，否则用错误的编码方式解读，就会出现乱码。为什么电子邮件常常出现乱码？就是因为发信人和收信人使用的编码方式不一样。

可以想象，如果有一种编码，将世界上所有的符号都纳入其中。每一个符号都给予一个独一无二的编码，那么乱码问题就会消失。这就是 Unicode，就像它的名字都表示的，这是一种所有符号的编码。

Unicode 当然是一个很大的集合，现在的规模可以容纳100多万个符号。每个符号的编码都不一样，比如，U+0639表示阿拉伯字母Ain，U+0041表示英语的大写字母A，U+4E25表示汉字严。具体的符号对应表，可以查询unicode.org，或者专门的汉字对应表。

四、Unicode 的问题

需要注意的是，Unicode 只是一个符号集，它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储。

比如，汉字严的 Unicode 是十六进制数4E25，转换成二进制数足足有15位（100111000100101），也就是说，这个符号的表示至少需要2个字节。表示其他更大的符号，可能需要3个字节或者4个字节，甚至更多。

这里就有两个严重的问题，第一个问题是，如何才能区别 Unicode 和 ASCII ？计算机怎么知道三个字节表示一个符号，而不是分别表示三个符号呢？第二个问题是，我们已经知道，英文字母只用一个字节表示就够了，如果 Unicode 统一规定，每个符号用三个或四个字节表示，那么每个英文字母前都必然有二到三个字节是0，这对于存储来说是极大的浪费，文本文件的大小会因此大出二三倍，这是无法接受的。

它们造成的结果是：1）出现了 Unicode 的多种存储方式，也就是说有许多种不同的二进制格式，可以用来表示 Unicode。2）Unicode 在很长一段时间内无法推广，直到互联网的出现。

五、UTF-8

互联网的普及，强烈要求出现一种统一的编码方式。UTF-8 就是在互联网上使用最广的一种 Unicode 的实现方式。其他实现方式还包括 UTF-16（字符用两个字节或四个字节表示）和 UTF-32（字符用四个字节表示），不过在互联网上基本不用。重复一遍，这里的关系是，UTF-8 是 Unicode 的实现方式之一。

UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号，根据不同的符号而变化字节长度。

UTF-8 的编码规则很简单，只有二条：

1）对于单字节的符号，字节的第一位设为0，后面7位为这个符号的 Unicode 码。因此对于英语字母，UTF-8 编码和 ASCII 码是相同的。

2）对于n字节的符号（n > 1），第一个字节的前n位都设为1，第n + 1位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的 Unicode 码。

下表总结了编码规则，字母x表示可用编码的位。

Unicode符号范围     |        UTF-8编码方式
(十六进制)        |              （二进制）
----------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

跟据上表，解读 UTF-8 编码非常简单。如果一个字节的第一位是0，则这个字节单独就是一个字符；如果第一位是1，则连续有多少个1，就表示当前字符占用多少个字节。

下面，还是以汉字严为例，演示如何实现 UTF-8 编码。

严的 Unicode 是4E25（100111000100101），根据上表，可以发现4E25处在第三行的范围内（0000 0800 - 0000 FFFF），因此严的 UTF-8 编码需要三个字节，即格式是1110xxxx 10xxxxxx 10xxxxxx。然后，从严的最后一个二进制位开始，依次从后向前填入格式中的x，多出的位补0。这样就得到了，严的 UTF-8 编码是11100100 10111000 10100101，转换成十六进制就是E4B8A5。

六、Unicode 与 UTF-8 之间的转换

通过上一节的例子，可以看到严的 Unicode码 是4E25，UTF-8 编码是E4B8A5，两者是不一样的。它们之间的转换可以通过程序实现。

Windows平台，有一个最简单的转化方法，就是使用内置的记事本小程序notepad.exe。打开文件后，点击文件菜单中的另存为命令，会跳出一个对话框，在最底部有一个编码的下拉条。

里面有四个选项：ANSI，Unicode，Unicode big endian和UTF-8。

1）ANSI是默认的编码方式。对于英文文件是ASCII编码，对于简体中文文件是GB2312编码（只针对 Windows 简体中文版，如果是繁体中文版会采用 Big5 码）。

2）Unicode编码这里指的是notepad.exe使用的 UCS-2 编码方式，即直接用两个字节存入字符的 Unicode 码，这个选项用的 little endian 格式。

3）Unicode big endian编码与上一个选项相对应。我在下一节会解释 little endian 和 big endian 的涵义。

4）UTF-8编码，也就是上一节谈到的编码方法。

选择完"编码方式"后，点击"保存"按钮，文件的编码方式就立刻转换好了。

七、Little endian 和 Big endian

上一节已经提到，UCS-2 格式可以存储 Unicode 码（码点不超过0xFFFF）。以汉字严为例，Unicode 码是4E25，需要用两个字节存储，一个字节是4E，另一个字节是25。存储的时候，4E在前，25在后，这就是 Big endian 方式；25在前，4E在后，这是 Little endian 方式。

这两个古怪的名称来自英国作家斯威夫特的《格列佛游记》。在该书中，小人国里爆发了内战，战争起因是人们争论，吃鸡蛋时究竟是从大头(Big-endian)敲开还是从小头(Little-endian)敲开。为了这件事情，前后爆发了六次战争，一个皇帝送了命，另一个皇帝丢了王位。

第一个字节在前，就是"大头方式"（Big endian），第二个字节在前就是"小头方式"（Little endian）。

那么很自然的，就会出现一个问题：计算机怎么知道某一个文件到底采用哪一种方式编码？

Unicode 规范定义，每一个文件的最前面分别加入一个表示编码顺序的字符，这个字符的名字叫做"零宽度非换行空格"（zero width no-break space），用FEFF表示。这正好是两个字节，而且FF比FE大1。

如果一个文本文件的头两个字节是FE FF，就表示该文件采用大头方式；如果头两个字节是FF FE，就表示该文件采用小头方式。

八、实例

下面，举一个实例。

打开"记事本"程序notepad.exe，新建一个文本文件，内容就是一个严字，依次采用ANSI，Unicode，Unicode big endian和UTF-8编码方式保存。

然后，用文本编辑软件UltraEdit 中的"十六进制功能"，观察该文件的内部编码方式。

1）ANSI：文件的编码就是两个字节D1 CF，这正是严的 GB2312 编码，这也暗示 GB2312 是采用大头方式存储的。

2）Unicode：编码是四个字节FF FE 25 4E，其中FF FE表明是小头方式存储，真正的编码是4E25。

3）Unicode big endian：编码是四个字节FE FF 4E 25，其中FE FF表明是大头方式存储。

4）UTF-8：编码是六个字节EF BB BF E4 B8 A5，前三个字节EF BB BF表示这是UTF-8编码，后三个E4B8A5就是严的具体编码，它的存储顺序与编码顺序是一致的。