综合设计目的、条件、任务和内容要求

目的

  掌握Huffman树的建立以及Huffman编码和解码

任务

  应用Huffman编码实现简单文本文件的压缩和解压缩

要求

  利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。综合设计的任务是：设计一个哈夫曼编码/译码系统，使学生掌握哈夫曼编码的特点、存储方法和基本原理，培养学生利用高级语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
  内容：分两个层次
  层次一：用下表中给出的字符和频度数据编程建立哈夫曼树，并实现对以下报文进行编码/译码。THIS PROGRAM IS MY FAVORITE

  层次二：编程从键盘任意输入一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码/译码。
    ①．作一个文本文件压缩器，从命令行输入需要压缩的文件，压缩之后的文件采用后缀名“zzz”。
    ②．编作一个解压缩器，从命令行输入需要解压缩的后缀名为“zzz”的文件，能够完整无误的实现文本文件的解压缩。
    ③对比用WinZip或者WinRAR压缩的文件和用自制压缩器压缩的文件，比较压缩效率。

设计简介及设计方案论述

编译环境

分配文件名

设置命令行参数

  在此项目完成后编译生成exe文件，在命令行中输入此exe文件名 + [参数1] + [参数2]，其中参数1是zip或者unzip, 参数2为文件名。

对文本文件压缩

  按二进制读取txt文件，生成哈夫曼树，生成哈夫曼编码，原文本的元素所对应的哈夫曼编码位压缩后存入压缩文件中，再将哈夫曼树生成的哈夫曼编码按照一定规则压缩后存入压缩文件zzz中。

对压缩文件解压缩

对位压缩进行解压，再根据哈夫曼编码查找对应的原文本元素，最后生成解压缩文件。

详细设计

  在Debug.cpp中，将main函数中的int型变量argc和char型二级指针传给debug函数，如果argc<=1或者argc>=4则提示命令行参数的正确使用方法；如果第二个命令行参数不为zip/unzip则提示命令行参数未被识别；第三个命令行参数为文件名，如果没有此参数则提示没有输入文件。
  可以执行的命令行例子：huffman zip C:\in.txt

压缩文件

更改保存的文件名

  EnZip.cpp中，enzip函数有三个形参：文件输入流ifs、char数组argv、文件输出流ofs. 其中ifs 打开需要解压的txt文件，ofs保存解压后的zzz文件，argv字符串保存的是打开文件的路径。
  新建一个string类filename, 复制argv字符串，保存文件所在路径，在路径后添加out.zzz作为保存文件路径。

读取文件

  由于文字编码方式的不同，相同的汉字在不同的文字编码方式所对应的二进制数可能不同。因此采用unsigned char型变量读取txt文件中的每一个字节，用vector来保存文件内容。

构造哈夫曼树

  创建一个vector类vsort复制vorigin中的内容，对vsort中的元素进行排序，vsort中的元素作为数哈夫曼结点的data, 计算每一个元素出现频率作为哈夫曼结点的weight, 按照哈夫曼树的构造方法从下至上构建哈夫曼树。
使用HTNode类数组ht保存哈夫曼树结点，[0, $n_0$)为叶子节点，也是需要编码的元素的节点。[$n_0$, 2*$n_0$)为非叶子节点，用于存储路径。

生成哈夫曼编码

  哈夫曼编码使用map<int, string>保存, key表示编码元素，value表示编码的二进制。
  生成编码的元素所对应的哈夫曼编码的方式是：从叶子节点开始往上寻找，如果该结点是其父结点的左结点则保存’0’, 如果是右结点则保存’1’，直到寻找的是根结点为止。然后将该保存的字符串倒置，此时的字符串即为叶子节点的哈夫曼编码。

压缩

  根据vorigin中的元素对应map中的key值在map中查找value，将查找到的value值放入新创建的string类szip中。
  将生成的szip作为原文本的哈夫曼编码，通过位运算将每8个字符所对应的二进制数放入文件输出流ofs中。


  将map或哈夫曼树压缩成二进制存入文件输出流ofs比较复杂，在此本人将map压缩成二进制。
  第一个字节存放map.begin()->first的元素，第二个字节存放map.begin()->second.length()的长度，根据长度确定map.begin()->second所占的字节数，根据计算，如果是1GB以下的文本，map.begin()->second所占的字节数不超过4。第三个字节到第6个字节存放map.begin()->second, 压缩该字符串的原理和压缩szip的原理类似。然后删除map.begin()这个迭代器在map中的位置，重新对新的map.begin()进行操作，直到map被清空为止。


  最后将szip中的长度用8个字节存储，通过位运算存入文件输出流ofs中。

解压缩文件

更改保存的文件名

  解压缩是压缩的逆过程，更改文件名的操作和压缩时更改文件名的操作大致相同，后缀名改为.txt

读取文件

  此操作和解压时的读取文件操作相同，用vector来保存文件内容。

解压缩

  解压缩为压缩的逆过程。同压缩一样，先通过位运算计算此压缩文件的最后8个字节确定slen的长度，再通过位运算解析出s和map的原字符串、原映射关系。根据公式可以计算出bound = ceil(slen * 1.0 / 8), 其中，[v.size()-8, v.size())属于哈夫曼编码长度，[0, bound) 属于原哈夫曼编码，[bound, v.size()-8))属于哈夫曼编码的map.



  在拥有原哈夫曼总编码字符串s和每个元素的哈夫曼编码map之后，通过前缀编码在map中寻找value, 如果value和前缀编码相同， 那就通过value寻找key, 并将前缀编码删除，继续生新的前缀码。由于在map中需要根据value来寻找key, 需要借助Lambda表达式。

回收内存

  在C++的STL中，T.clear()无法释放内存，需要借助.swap()函数。

设计结果及分析

运行程序

配置环境变量

  为此项目的目录配置环境变量（如果不配置环境变量那么命令行就只能在此项目的目录下输入命令行）

输入命令行参数运行

  打开终端，输入命令行。命令行格式：[参数1] [参数2] [参数3]
  其中参数1为exe文件前缀，参数2为 zip/unzip, 代表需要进行解压/压缩参数，参数3为需要操作的文件路径。如果参数2为zip, 那么压缩后的文件路径同参数3，文件后缀为out.zzz 如果参数2为unzip, 那么压缩后的文件路径同参数3，文件后缀为unzip.txt


  由于此程序的哈夫曼编码元素是字节所对应的二进制数的大小，因此此程序也可以压缩、解压绝大多数小于1GB的内容。将解压后的文件后缀名改为和压缩前文件名相同即可。

对比压缩前与解压后的文件

  肉眼对比压缩前的文件和解压后的文件之间的差别

  对于较难肉眼验证的文件可以通过编程来验证文件所含内容是否相同。

  经过多个文件比较，所有测试的文件压缩前与解压后的内容相同。

计算压缩率

  压缩率=压缩后的文件大小/压缩前文件的大小*100%，压缩率越小压缩的空间效率越高。测试多组数据的压缩率。
第一组数据，1.22KB的txt英文文档， 压缩率≈67.20%

  第二组数据，2.07KB的txt中英文档，编码方式为utf-8, 压缩率≈90.79%

  第三组数据，615KB的pptx文档, 压缩率≈99.64%

  第四组数据，含有大量重复内容的英文txt文档, 压缩率≈54.84%

  第五组数据，随机数生成的200KB的txt文档, 压缩率≈100.38%

和WinRar软件比较

  RAR是一种专利文件格式，用于数据压缩与归档打包，由尤金·罗谢尔开发，Windows操作系统下比较有名的编码器是WinRar. 将4.3中的测试样例进行压缩，和本项目的运行程序压缩效率进行对比。
  第一组数据，本项目程序压缩率≈67.20%, WinRar压缩率≈57.25%

  第二组数据，本项目程序压缩率≈90.79%, WinRar压缩率≈61.11%

  第三组数据，本项目程序压缩率≈99.64%, WinRar压缩率≈93.77%

  第四组数据，本项目程序压缩率≈54.84%, WinRar压缩率≈0.03%

  第五组数据，本项目程序压缩率≈100.38%, WinRar压缩率≈100.07%

分析结果

汉字压缩率过高

  由于汉字在utf-8中使用多个字节，因此按照字节流进行读取的时候会有很多干扰的字节变成了哈夫曼编码的元素，因此当文本中有非英文字的时候压缩的空间效率会大大折扣。
解决方法：C++不方便使用字节流进行操作，可以将编程语言换成Java，按字符流读取文件，那么在压缩汉字的过程中压缩率会降低。

解压时间效率偏低

  解压缩的过程是将前缀编码和总哈夫曼编码进行逐一比对，虽然map的查找效率比较高，但是字符串的比较默认是O(n*m)的比较方式而不是O(n+m)的KMP比较方式，所以总时间复杂度较大，在解压超过1MB的非纯英文文件时明显感觉到耗费较多时间，远比WinRar的时间效率低。
解决方法：根据哈夫曼元素的哈夫曼编码的map逆向构建哈夫曼树，如果前缀字符串在哈夫曼树上的路径的终点不是叶子节点则继续往前缀字符添加哈夫曼编码。由于哈夫曼树是一棵最优二叉树，因此查找效率非常高，可以大幅度降低时间复杂度。

分析WinRar压缩率低的原因

  从理论上来讲，采用哈夫曼编码所得到的压缩文件在磁盘中所占据的空间应该是最小的，但是在实际生活中，WinRar的压缩文件所占空间小一些。
  WinRar压缩的主要原理是查找文件内的重复字节，根据重复的字节建立一个相同字节的“词典文件”，并用一串代码来表示。事实上，即使人们不去刻意地使用重复字节，各种类型的数据都有重复的倾向。程序的源文件中，语法关键字会重复出现；一篇论文中，为数不多的术语倾向于重复出现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会重复出现。正是因为存在着这些重复出现的字节让rar的空间存储效率大幅度提升。再加上rar的压缩过程中有很多优质的算法，rar压缩、解压的时间效率也相当高。

总结

  哈夫曼树是由n 个带权叶子结点构成的所有二叉树中带权路径长度WP L 最小的二叉树, 是一种带权路径长度最短的树, 又叫最优二叉树。
  在数据压缩中, 哈夫曼编码是一种变长编码, 采用的是一种优化静态编码方法。具有以下不足:
    ( l) 需要事先知道输入码字符集的频率分布, 在不同的数据文件中, 不同字符出现的频率不同。
    ( 2 ) 需要对原始数据块扫描两次: 第一次是统计原始数据中各符号出现的频率并排序, 利用得到的频率值创建哈夫曼树并将树的有关信息保存起来, 便于解压时使用；第二次是进行编码, 根据前面得到的哈夫曼树对原始数据进行编码, 并将编码信息存储起来, 便于存储和传输。如果将这种方法用于数据的网络通信中，两遍扫描势必会引起较大的延时, 两次扫描所引发的低效率不容忽视；同时,如果用于文件数据的压缩中, 重复扫描增加了磁盘访问，额外的磁盘访问将会降低该算法的数据压缩速度, 从而降低压缩效率。
  生成压缩文件时除了需要保存原文件所对应的哈夫曼编码外，还需要保存每一个元素所对应的哈夫曼编码或者哈夫曼树。在解压的过程中需要分离压缩文件中的总哈夫曼编码以及每一个元素所对应的哈夫曼编码。在还原原文件时，可以通过前缀码逐个在哈夫曼编码中查找，也可以在哈夫曼树中查找。后者的时间效率更高。
为提高压缩时间还可以将单线程变成多线程，使用C++ 11库中的thread类来进行并发操作，让分析文件与创建哈夫曼树同时进行，加快压缩和解压速度。
  单纯地使用静态哈夫曼编码可以实现数据的压缩，但是如果需要提高压缩的时间效率、空间效率那就需要采用更为高级的算法、更为高深的理论。
  WinRar可以将文件进行加密，此程序也可以试着向压缩文件进行加密，确保数据安全性。可以采用安全性较高的RSA加密算法进行加密。

附录 主要程序代码

Main.cpp

/********************* Main.cpp parameters argv[1] zip/unzip argv[2] filepath ifs inputFileStream ofs ouputFileStream functions debug choose operation according to command line enzip zip ".\\argv.txt" to ".\\out.zzz" unzip unzip ".\\argv.zzz" to ".\\unzip.txt" *********************/
# include <iostream>
# include <string> 
# include <fstream>

int debug(int argc, char* argv[]);
void enzip(std::ifstream& ifs, char argv[], std::ofstream& ofs);
void unzip(std::ifstream& ifs, char argv[], std::ofstream& ofs);

int main(int argc, char* argv[]) {
   
	std::ifstream ifs;
	std::ofstream ofs;

	switch (debug(argc, argv)) {
   
		case 2: {
   
			std::cout << "zipping" << std::endl;

			enzip(ifs, argv[2], ofs);
			std::cout << "Zip successfully" << std::endl;
			break;
		}
		case 4: {
   
			std::cout << "Unzipping" << std::endl;
			unzip(ifs, argv[2], ofs);
			std::cout << "Unzip successfully" << std::endl;
			break;
		}
	}

	ifs.close();
	ofs.close();
	return 0;
}

Debug.cpp

/********************* Debug.cpp parameters argv[1] zip/unzip argv[2] filepath functions debug choose operation according to command line *********************/
# include <iostream>
# include <cstring>

int debug(const int argc, char* argv[]) {
   
	if (argc <= 1 || argc >= 4) {
   
		std::cout << "Usage: huffman [zip/unzip] <filepath>" << std::endl;
		std::cout << "\t(to zip/unzip a file)" << std::endl;
		return 0;
	}
	
	if (strcmp(argv[1], "zip") == 0) {
   
		if (argv[2] == nullptr) {
   
			std::cout << "zip: fatal error: no input files\ncompilation terminated." << std::endl;
			return 1;
		}
		return 2;
	} 
	else if (strcmp(argv[1], "unzip") == 0) {
   
		if (argv[2] == nullptr) {
   
			std::cout << "unzip: fatal error: no input files\ncompilation terminated." << std::endl;
			return 3;
		}
		return 4;
	}
	else {
   
		std::cout << "huffman: error: unrecognized command line option " << '\'' << argv[1] << '\'' << std::endl;
		std::cout << "compilation terminated." << std::endl;
		return 5;
	}
}

HuffmanTree.h

/********************* HuffmanTree.h *********************/
# ifndef HUFFMANTREE_H
# define HUFFMANTREE_H

# include <iostream>
# include <string>

class HTNode {
   
public:
	int data;
	double weight;
	int parent;
	int lchild;
	int rchild;
};

# endif

HuffmanTree.cpp

/********************* HuffmanTree.cpp parameters ht HTNode, class v vector, each element is the byte of input file n0 size of ht functions setWeight set each HTNode's weight and data createHT set each HTNode's relationship *********************/
# include <vector>
# include "HuffmanTree.h"

void setWeight(HTNode*& ht, const std::vector<int>& v, int& n0) {
   
	int alpnum[260] = {
    0 };
	int fnum[260] = {
    0 };
	for (int i = 0; i < v.size(); i++) {
   
		if (alpnum[v[i]] == 0) {
   
			fnum[n0] = v[i];
			n0++;
		}
		alpnum[v[i]]++;
	}

	ht = new HTNode[2 * n0]();

	for (int i = 0; i < n0; i++) {
   
		ht[i].weight = 1.0 * alpnum[fnum[i]] / v.size();
		ht[i].data = fnum[i];
	}
}

void createHT(HTNode*& ht, int n0) {
   
	for (int i = 0; i < 2 * n0 - 1; i++) {
   
		ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
	}

	for (int i = n0; i < 2 * n0 - 1; i++) {
   
		double min1 = 1e100;
		double min2 = 1e100;
		int lnode = -1;
		int rnode = -1;

		for (int k = 0; k < i; k++) {
   
			if (ht[k].parent == -1) {
   
				if (ht[k].weight < min1) {
   
					min2 = min1;
					rnode = lnode;
					min1 = ht[k].weight;
					lnode = k;
				}
				else if (ht[k].weight < min2) {
   
					min2 = ht[k].weight;
					rnode = k;
				}
			}
		}

		ht[i].weight = ht[lnode].weight + ht[rnode].weight;
		ht[i].lchild = lnode;
		ht[i].rchild = rnode;
		ht[lnode].parent = i;
		ht[rnode].parent = i;
	}
}

HuffmanCode.h

/********************* HuffmanCode.h parameters hcd map, key representing huffman node's data string representing huffman node's code functions HCode::createHcode create each HCode's data and string code HCode::findValue find the key's value HCode::getMap() return HCode's protected map *********************/
# ifndef HUFFMANCODE_H
# define HUFFMANCODE_H

# include <iostream>
# include <map>
# include <string>
# include "HuffmanTree.h"

class HCode {
   
protected:
	std::map<int, std::string> hcd;

public:
	void createHcode(HTNode*& ht, int n0);
	const std::string& findValue(int key);
	const std::map<int, std::string>& getMap();
	~HCode() {
   
		while (this->hcd.size()) {
   
			std::string().swap(this->hcd.begin()->second);
			this->hcd.erase(this->hcd.begin());
		}

		std::map<int, std::string>().swap(this->hcd);
	}
};

# endif

HuffmanCode.cpp

/********************* HuffmanCode.cpp parameters ht HTNode, class n0 size of ht functions HCode::createHcode create each HCode's data and string code HCode::findValue find the key's value HCode::getMap() return HCode's protected map *********************/
# include <algorithm>
# include "HuffmanCode.h"

void HCode::createHcode(HTNode*& ht, int n0) {
   
	for (int i = 0; i < n0; i++) {
   
		std::string t;

		int c = i;
		int f = ht[i].parent;

		while (f != -1) {
   
			if (ht[f].lchild == c) {
   
				t.push_back('0');
			}
			else {
   
				t.push_back('1');
			}

			c = f;
			f = ht[f].parent;
		}

		std::reverse(t.begin(), t.end());
		hcd.insert({
    ht[i].data, t });

		std::string().swap(t);
	}
}

const std::string& HCode::findValue(int key) {
   
	auto it = hcd.find(key);
	if (it != hcd.end()) {
   
		return it->second;
	}
	else {
   
		return nullptr;
	}
}

const std::map<int, std::string>& HCode::getMap() {
   
	return this->hcd;
}

EnZip.cpp

/********************* EnZip.cpp parameters ifs inputFileStream ofs ouputFileStream argv filepath hcd HCode, class filename change filename ".\\argv.txt" to ".\\out.zzz" vorign vector, each element is the byte of input file vsort vector, sort vorigin to get the HTNode more easily szip string, huffman code containing "0100111......" functions enzip zip ".\\argv.txt" to ".\\out.zzz" stringZip zip szip and hcd to outputFileStream ".\\zzz" *********************/
# include <iostream>
# include <string> 
# include <fstream>
# include <vector>
# include <algorithm>
# include "HuffmanTree.h"
# include "HuffmanCode.h"

void setWeight(HTNode*& ht, const std::vector<int>& v, int& n0);
void createHT(HTNode*& ht, int n0);
void stringZip(std::ofstream& ofs, const std::string& s, HCode& hcd);

void enzip(std::ifstream& ifs, char argv[], std::ofstream& ofs) {
   
	ifs.open(argv, std::ios::binary);
	if (!ifs) {
   
		std::cout << "Failed in opening " << argv << std::endl;
		exit(-1);
	}

	std::string filename;
	char* itc = argv;
	while (*itc != '\0') {
   
		filename.push_back(*itc);
		itc++;
	}

	for (int i = filename.length() - 1; i >= 0; i--) {
   
		if (filename[i] != '\\' && filename[i] != '/') {
   
			filename.pop_back();
		}
		else {
   
			break;
		}
	}

	filename += "out.zzz";

	ofs.open(filename, std::ios::binary);
	if (!ofs) {
   
		std::cout << "Failed in opening " << filename << std::endl;
		exit(-1);
	}

	unsigned char c;
	std::vector<int> vorigin;
	while (ifs >> std::noskipws >> c) {
   
		vorigin.push_back((int)c);
	}

	int n0 = 0;
	std::vector<int> vsort = vorigin;
	std::sort(vsort.begin(), vsort.end());
	HTNode* ht;
	setWeight(ht, vsort, n0);
	createHT(ht, n0);
	HCode hcd;
	hcd.createHcode(ht, n0);

	std::string szip;
	for (int i = 0; i < vorigin.size(); i++) {
   
		szip += hcd.findValue(vorigin[i]);
	}
	stringZip(ofs, szip, hcd);

	std::vector<int>().swap(vorigin);
	std::vector<int>().swap(vsort);
	std::string().swap(szip);
	delete[] ht;
	ofs.close();
	ifs.close();
}

StringZip.cpp

/********************* StringZip.cpp parameters ofs ouputFileStream s string, huffman code containing "0100111......" hcd HCode, class tmap HCode's map functions stringZip zip s and tmap to outputFileStream ".\\zzz" *********************/
# include <iostream>
# include <string> 
# include <fstream>
# include "HuffmanCode.h"

void stringZip(std::ofstream& ofs, const std::string& s, HCode& hcd) {
   
	unsigned long long slen = s.length();

	for (int i = 0; i < s.length(); i += 8) {
   
		unsigned char c = 0;

		for (int j = 0; i + j < s.length() && j < 8; j++) {
   
			c |= (s[i + j] - '0') << (7 - j);
		}

		ofs << c;
	}

	std::map<int, std::string> tmap = hcd.getMap();

	while (tmap.size()) {
   
		auto it = tmap.begin();
		unsigned char fir = it->first;
		ofs << fir;

		int lensec = it->second.length();
		ofs << (unsigned char)lensec;
		for (int i = 0; i < lensec; i += 8) {
   
			unsigned char c = 0;

			for (int j = 0; i + j < lensec && j < 8; j++) {
   
				c |= (it->second[i + j] - '0') << (7 - j);
			}
			
			ofs << c;			
		}

		tmap.erase(tmap.begin());
	}

	for (int i = 63; i >= 0; i -= 8) {
   
		unsigned char c = 0;

		for (int j = 0; j < 8; j++) {
   
			c |= ((slen >> (i - j)) & 1) << (7 - j);
		}

		ofs << c;
	}

	std::map<int, std::string>().swap(tmap);
}

Unzip.cpp

/********************* Unzip.cpp parameters ifs inputFileStream(".\\argv.zzz") ofs outputFileStream(".\\unzip.txt") argv char[], input file name filename change filename ".\\argv.zzz" to ".\\unzip.txt" vread vector, each element is the byte of input file s string, huffman code containing "0100111......" st string, substring of s find_item iterator, find value's iterator tmap map, representing HCode's map functions stringUnzip unzip vread to s and tmap unzip unzip ".\\argv.zzz" to ".\\unzip.txt" *********************/
# include <iostream>
# include <string> 
# include <vector>
# include <fstream>
# include <algorithm>
# include <map>

void stringUnzip(std::vector<int>& v, std::string& s, std::map<int, std::string>& map);

void unzip(std::ifstream& ifs, char argv[], std::ofstream& ofs) {
   
	ifs.open(argv, std::ios::binary);
	if (!ifs) {
   
		std::cout << "Failed in opening " << argv << std::endl;
		exit(-1);
	}

	std::string filename;
	char* itc = argv;
	while (*itc != '\0') {
   
		filename.push_back(*itc);
		itc++;
	}

	for (int i = filename.length() - 1; i >= 0; i--) {
   
		if (filename[i] != '\\' && filename[i] != '/') {
   
			filename.pop_back();
		}
		else {
   
			break;
		}
	}

	filename += "unzip.txt";

	ofs.open(filename, std::ios::binary);
	if (!ofs) {
   
		std::cout << "Failed in opening " << filename << std::endl;
		exit(-1);
	}

	unsigned char c;
	std::vector<int> vread;
	while (ifs >> std::noskipws >> c) {
   
		vread.push_back((int)c);
	}

	std::string s;
	std::map<int, std::string> tmap;
	stringUnzip(vread, s, tmap);	

	std::string st;
	for (int i = 0; i < s.length(); i++) {
   
		st.push_back(s[i]);
		auto find_item = std::find_if(tmap.begin(), tmap.end(),
			[st](const std::map<int, std::string>::value_type item) {
   
				return item.second == st;
			});

		if (find_item != tmap.end()) {
   
			ofs << (unsigned char)find_item->first;
			std::string().swap(st);
		}
	}

	std::string().swap(s);
	std::vector<int>().swap(vread);
	ifs.close();
	ofs.close();
}

StringUnzip.cpp

/********************* StringUnZip.cpp parameters v vector, each element is the byte of input file s string, huffman code containing "0100111......" tmap map, representing HCode's map slen from [v.size()-8, v.size()) is huffman code's length bound from [0, bound) is the huffman code, from [bound, v.size()-8) is the map code functions StringUnzip unzip v to s and tmap *********************/
# include <iostream>
# include <string> 
# include <cmath>
# include <vector>
# include <map>

void stringUnzip(std::vector<int>& v, std::string& s, std::map<int, std::string>& map) {
   
	unsigned long long slen = 0;

	for (int i = v.size() - 8; i < v.size(); i++) {
   
		for (int j = 0; j < 8; j++) {
   
			int dig = 8 * (v.size() - i - 1) + 7 - j;

			slen |= (unsigned long long)((v[i] >> (7 - j)) & 1) << dig;
		}
	}			

	unsigned long long bound = (unsigned long long)ceil(slen * 1.0 / 8);
	for (unsigned long long i = 0; i < bound; i++) {
   
		for (int j = 0; j < 8; j++) {
   
			if (i * 8 + j < slen) {
   
				char c = ((v[i] >> (7 - j)) & 1) + '0';
				s.push_back(c);
			}
		}
	}
	
	for (unsigned long long i = bound; i < v.size() - 8; true) {
   
		int first = v[i];
		int seclen = v[i + 1];
		std::string secstr;
		int secbound = (int)ceil(seclen * 1.0 / 8);
		for (int j = i + 2; j < i + 2 + secbound; j++) {
   
			for (int k = 0; k < 8; k++) {
   
				if ((j - i - 2) * 8 + k < seclen) {
   
					char c = ((v[j] >> (7 - k)) & 1) + '0';	
					secstr.push_back(c);
				}
			}
		}
		
		map.insert({
    first, secstr });
		if (i + 2 + secbound >= v.size() - 8) {
   
			break;
		}
		else {
   
			i += (unsigned long long)2 + secbound;
		}

		std::string().swap(secstr);
	}
}