Huffman算法實作檔案加密

使用Huffman算法來加密檔案

這次的blog隻是為了記錄一下本人第一次自己編寫的算法（源于部落客的課設作業）

參考的部落格和文章忘了出處，如有相似的，請聯系部落客

此次程式主要使用C++來編寫，其中由于特殊原因混有一些C語言，部落客會逐漸逐漸完善代碼

程式的功能是在rawletter.txt中讀取出現的字元以及其權重（權重可以了解成出現的機率），然後通過使用Huffman算法來形成每個字元對應的Huffman編碼，按照原來rawletter.txt檔案中的字元一一對應生成由Huffman碼構成的新檔案codefile.txt，達到加密的效果。

此外程式還将生成key to letter.txt檔案來記錄每一個字元以及其對應的Huffman碼

部落客對檔案的解密功能還沒完全實作，目前隻能生成一個translate.txt檔案，但無法識别換行符`

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

class huffmannode   //節點類
{
	friend void getmin(huffmannode n1[], int *p1, int*p2, int k);
	friend void display(int num, huffmannode n[], string code[]);
	friend void receive(int *num, huffmannode p1[]);
	friend void translate(string code[], int num, huffmannode n[]);

	char str;    //每個節點對應的字元
	int weight, parent, lchild, rchild;   
public:
	huffmannode()
	{
		this->parent = 0;
		this->weight = 0;
		this->rchild = 0;
		this->lchild = 0;
	}

	huffmannode& combine(huffmannode& n1, huffmannode& n2,int index1,int index2,int index)  //把兩個節點合成新節點的函數
	{
		this->weight = n1.weight + n2.weight;
		n1.parent = index;
		n2.parent = index;
		this->lchild = index1;
		this->rchild = index2;
		return *this;
	}
};

void getmin(huffmannode n[],int *p1,int*p2,int k)              //得到權值最小的兩個節點
{
	int i;
	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0)
		{
			*p1 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && n[i].weight < n[*p1].weight)
		{
			*p1 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && i != *p1)
		{
			*p2 = i;
		}
	}

	for (i = 0; i < k; i++)
	{
		if (n[i].parent == 0 && n[i].weight < n[*p2].weight&& i !=*p1)
		{
			*p2 = i;
		}
	}
}

void display(int num,huffmannode n[],string code[])    //形成每個字元對應的Huffman碼    運用了檔案操作
{
	ofstream fout1("key to letter.txt");

	for (int i = 0; i < num; i++)
	{

		for (int j=i, f = n[j].parent; f; j = f, f = n[j].parent)
		{
			if (n[f].lchild == j)
			{
				code[i]+='0';
			}
			else
			{
				code[i]+='1';
			}
		}
		reverse(code[i].begin(), code[i].end());        //把字元串反向
		fout1 << n[i].str << " -> " << code[i] << endl;
		
	}
	fout1.close();
	
	ofstream fout("codefile.txt");
	ifstream fin("rawletter.txt");
	if (!fin.is_open())
	{
		cout << "the rawletter.txt isn't existed" << endl;
		return ;
	}

	char buffer;
	fin >> noskipws;          //使流的輸入不會忽略空格和換行符

	while (fin.peek()!=EOF)      //peek傳回下一個值的值，若使用ofe的話，會讀取多一個字元
	{
		fin >> buffer;
		
		for (int i = 0; i < num; i++)
		{
			if (n[i].str == buffer)
			{
				fout << code[i] << endl;
			}
		}
	}

	fin.close();
	fout.close();
	
	//編碼完成 ——》寫入檔案中
}

//下面兩個函數的作用是讀取rawletter.txt檔案，計算出出現的字元以及對應的權重（因為特殊原因，是部落客同學編寫的。。。）

void search(char a[], int b[52], char file[1000]);

void receive(int *num, huffmannode p1[]);

void translate(string code[],int num,huffmannode n[])     //解密檔案  由Huffman碼組成的檔案 --》字元檔案（翻譯檔案）
{
	string buffer;
	ofstream fout("translate.txt");
	ifstream fin("codefile.txt");
	if (!fin.is_open())
	{
		cout << "codefile.txt is not found" << endl;
		return;
	}

	while (getline(fin,buffer))
	{
		for (int i = 0; i < num; i++)
		{
			if (code[i] == buffer)
			{
				fout << n[i].str;
			}
		}
	}

	fout.close();
	fin.close();
}

int main()
{
	int i = 0,j;//j:用來疊代
	int num;//num是字元種類的數量
	string code[65];//用來存放每個字元對應的Huffman碼
	huffmannode pl[65];

	receive(&num, pl);   

	for (j = 0; j <num-1; j++)
	{
		int p1, p2, k = j + num;
		getmin(pl, &p1, &p2, k);        //得到最小的兩個節點
		pl[k].combine(pl[p1], pl[p2], p1, p2, k);     //合成新的節點
	}

	
	display(num, pl,code);
	translate(code, num, pl);
	return 0;
}

void receive(int *num,huffmannode p1[])
{
	char a[67] = { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890.," };
	a[66] = '\n';
	int b[67] = { 0 }, i, L = 0,sum=0;
	int k = 0;//用于疊代
	
	char file[9999];
	
	ifstream fp("rawletter.txt");
	if (!fp.is_open())
	{
		cout << "rawletter.txt isn't existed" << endl;
		return;
	}

	while (!fp.eof())
	{
		fp.getline(file, 9999);
		search(a, b, file);
	}
	fp.close();
	
	for (i = 0; i < 66; i++)
	{
		if (b[i] != 0)
		{
			L++;
		}
		sum += b[i];//得出字元總數量  
	}
	*num = L;//字元種類的數量

	for ( i = 0; i < 66; i++)
	{
		if (b[i] != 0)
		{
			//計算權重 -> 賦予HuffmanTree的節點
			float temp = b[i] / sum;
			p1[k].weight = int(temp);
			p1[k].str = a[i];
			k++;
		}
	}
}

//計算某種字元出現的頻率
void search(char a[], int b[], char file[1000])
{
	int i, j;
	for (i = 0; i<66; i++)
	{
		for (j = 0; file[j] != '\0'; j++)
		{
			if (file[j] == a[i])
			{
				b[i] += 1;
			}
		}
	}
}