利用哈弗曼編碼進(jìn)行壓縮-創(chuàng)新互聯(lián)
// sZipDemo.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include "HuffmanTree.cpp"
#include "sZip.h"
#include <fstream>
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
char str1[10000];
ifstream in;
in.open("text.txt",ios::in|ios::binary);
in>>str1;
cout<<"成功讀取text.doc！"<<endl;
int num = in.gcount();
in.close();
char tempstr[100000];
for(int i = 0;i <= num;i++)
tempstr[i] = str1[i];
unsigned int count[128];
char data[128];
HuffmanTree<char> Tree;
Tree.creat(tempstr,data,count);
char charCount[256];
for(int i = 0;count[i] != 0;i++){
static int n = -1;
if(count[i] < 10){ //個(gè)位
charCount[++n] = count[i]+48;
charCount[++n] = '#';
}
else if(count[i] >= 10 && count[i] < 100){ //十位
charCount[++n] = count[i]/10+48;
charCount[++n] = count[i]%10+48;
charCount[++n] = '#';
}
else if(count[i] >= 100 && count[i] < 1000){ //百位
charCount[++n] = count[i]/100+48;
charCount[++n] = count[i]%100/10+48;
charCount[++n] = count[i]%10+48;
charCount[++n] = '#';
}
else{ //千位
charCount[++n] = count[i]/1000+48;
charCount[++n] = count[i]%1000/100+48;
charCount[++n] = count[i]%100/10+48;
charCount[++n] = count[i]%10+48;
charCount[++n] = '#';
}
charCount[n+1] = 0;
}
ofstream out;
out.open("text11.txt",ios::out|ios::binary);
out<<data<<'#'<<'#'<<charCount;
out<<'#'<<'#';
sZip zip;
char str2[100000];
int size = 0;
zip.zip(str1,str2,Tree.root,size,data);
out<<str2;
out.close();
cout<<"成功壓縮text.doc文件，壓縮文件為text11.doc"<<endl;
cout<<"------------------------------------------------------------------------"<<endl;
char str3[100000];
char str4[10000];
in.open("text11.txt",ios::in|ios::binary);
in.read(str3,80000);
in.close();
str3[in.gcount()] = 0;
zip.unzip(str3,str4);
out.open("text22.txt",ios::out|ios::binary);
out<<str4;
out.close();
return 0;
}#pragma once
template <class T>
struct HuffmanTreeNode{
T data; //數(shù)據(jù)
unsigned int count; //權(quán)值
char code[128]; //結(jié)點(diǎn)的哈弗曼編碼
HuffmanTreeNode<T> *leftChild; //左子女
HuffmanTreeNode<T> *rightChild; //右子女
HuffmanTreeNode<T> *parent; //父節(jié)點(diǎn)
HuffmanTreeNode():leftChild(NULL),rightChild(NULL),parent(NULL){} //構(gòu)造函數(shù)
bool operator <=(HuffmanTreeNode &R){return count <= R.count;} //重載<=和>運(yùn)算符
bool operator >(HuffmanTreeNode &R){return count > R.count;}
};
template <class T>
class HuffmanTree
{
public:
HuffmanTree();
HuffmanTree(HuffmanTree<T> &t);
~HuffmanTree(void);
void printData();
int getWPL(); //獲取WPL //打開(kāi)文件
void creat(char str[],char data[],unsigned int count[]); //哈弗曼的建立
void creat(char data[],unsigned int count[]); //重載
template <class T>
friend void findKey(HuffmanTreeNode<T> *subTree,T key,char code[]){ //尋找結(jié)點(diǎn)的code
static T firstNodeData = subTree->data;
if(subTree != NULL){
if(subTree->data != key){
findKey(subTree->leftChild,key,code);
findKey(subTree->rightChild,key,code);
}
else{
int i = 0;
for(;subTree->code[i] != 0;i++)
code[i] = subTree->code[i];
code[i] = 0;
}
}
}
HuffmanTreeNode<T> *root;
protected:
private:
int WPL;
void census(unsigned int count[],char data[],char str[],unsigned int &size); //建立哈弗曼樹(shù)時(shí)統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)
void deleteTree(HuffmanTreeNode<T> *subTree); //刪除subTree結(jié)點(diǎn)的所有子結(jié)點(diǎn)
void encode(HuffmanTreeNode<T> *subTree,char code[] ,char m = 0); //編碼
void calculateWPL(HuffmanTreeNode<T> *subTree,int i = 0); //計(jì)算WPL
void printCode(HuffmanTreeNode<T> *subTree); //輸出哈弗曼編碼的子函數(shù)
void printData(HuffmanTreeNode<T> *subTree); //輸出所有結(jié)點(diǎn)data和權(quán)值的子函數(shù)
};#pragma once
#include "StdAfx.h"
#include "HuffmanTree.h"
#include "MinHeap.cpp"
#include <fstream>
template <class T>
HuffmanTree<T>::HuffmanTree(){
WPL = 0;
root = new HuffmanTreeNode<T>;
};
template <class T>
HuffmanTree<T>::~HuffmanTree(){
deleteTree(root); //刪除哈弗曼樹(shù)
}
template <class T>
void HuffmanTree<T>::creat(char str[],char data[],unsigned int count[]){
unsigned int size; //字符的個(gè)數(shù)
for(unsigned int i = 0; i < 128; i++) //count的初始化
count[i] = 0;
census(count,data,str,size);
minHeap<HuffmanTreeNode<T>> hp;
HuffmanTreeNode<T> *parent, *first, *second;
HuffmanTreeNode<T> *work;
for(unsigned int i = 0; i < size; i++){ //把每個(gè)元素都插入最小堆中
work = new HuffmanTreeNode<T>;
work->data = data[i];
work->count = count[i];
work->leftChild = NULL;
work->rightChild = NULL;
work->parent = NULL;
hp.insert(*work);
}
for(unsigned int i = 0; i < size-1; i++){
parent = new HuffmanTreeNode<T>;
first = new HuffmanTreeNode<T>;
second = new HuffmanTreeNode<T>;
hp.removeMin(*first); //每次從最小堆中取出兩個(gè)最小的數(shù)
hp.removeMin(*second);
parent->leftChild = first; //parent作為他們的父節(jié)點(diǎn)
parent->rightChild = second;
parent->count = first->count + second->count;
parent->data = '#'; //parent不是根結(jié)點(diǎn)所以把它的data設(shè)為'#'
first->parent = parent;
second->parent = parent;
hp.insert(*parent); //再把parent插入最小堆中，進(jìn)行循環(huán)判斷
}
root = parent; //最后一個(gè)parent就是根結(jié)點(diǎn)
char code[128];
for(unsigned int i = 0;i < 128; i++)
code[i] = 0;
encode(root,code); //對(duì)結(jié)點(diǎn)進(jìn)行哈弗曼編碼（空的地方取0）
};
template <class T>
void HuffmanTree<T>::creat(char data[],unsigned int count[]){
unsigned int size = 0;
for(unsigned int i = 0; count[i] != 0; i++)
size++;
minHeap<HuffmanTreeNode<T>> hp;
HuffmanTreeNode<T> *parent, *first, *second;
HuffmanTreeNode<T> *work;
for(unsigned int i = 0; i < size; i++){ //把每個(gè)元素都插入最小堆中
work = new HuffmanTreeNode<T>;
work->data = data[i];
work->count = count[i];
work->leftChild = NULL;
work->rightChild = NULL;
work->parent = NULL;
hp.insert(*work);
}
for(unsigned int i = 0; i < size-1; i++){
parent = new HuffmanTreeNode<T>;
first = new HuffmanTreeNode<T>;
second = new HuffmanTreeNode<T>;
hp.removeMin(*first); //每次從最小堆中取出兩個(gè)最小的數(shù)
hp.removeMin(*second);
parent->leftChild = first; //parent作為他們的父節(jié)點(diǎn)
parent->rightChild = second;
parent->count = first->count + second->count;
parent->data = '#'; //parent不是根結(jié)點(diǎn)所以把它的data設(shè)為'#'
first->parent = parent;
second->parent = parent;
hp.insert(*parent); //再把parent插入最小堆中，進(jìn)行循環(huán)判斷
}
root = parent; //最后一個(gè)parent就是根結(jié)點(diǎn)
char code[128];
for(unsigned int i = 0;i < 128; i++)
code[i] = 0;
encode(root,code); //對(duì)結(jié)點(diǎn)進(jìn)行哈弗曼編碼（空的地方取0）
}
template <class T>
void HuffmanTree<T>::deleteTree(HuffmanTreeNode<T> *subTree){
if(subTree != NULL){
deleteTree(subTree->leftChild); //后序遍歷來(lái)刪除結(jié)點(diǎn)
deleteTree(subTree->rightChild);
delete subTree;
}
}
template <class T>
void HuffmanTree<T>::census(unsigned int count[],char data[],char str[],unsigned int &size){
//用于統(tǒng)計(jì)字符出現(xiàn)的次數(shù)
for(int i = 0; str[i] != 0;i++){
if(str[i] == '#') //當(dāng)出現(xiàn)的是已出現(xiàn)過(guò)的字符時(shí)就執(zhí)行下次循環(huán)
continue;
static int n = 0;
count[n]++; //第一次出現(xiàn)時(shí)加一
data[n] = str[i];
for(int j = 0; str[j] != 0;j++){
if(str[i] == str[j] && i != j){
count[n]++; //每次出現(xiàn)重復(fù)的時(shí)候加一并且
str[j] = '#'; //表明已出現(xiàn)過(guò)
}
}
data[++n] = 0;
size = n;
}
}
template <class T>
void HuffmanTree<T>::encode(HuffmanTreeNode<T> *subTree,char code[] ,char m = 0){
if(subTree != NULL){
int j;
for(j = 0;code[j] != 0;j++){
subTree->code[j] = code[j];
}
for(j = 0;code[j] != 0;j++){
}
subTree->code[j] = m;
subTree->code[j+1] = 0;
encode(subTree->leftChild,subTree->code,'0');
encode(subTree->rightChild,subTree->code,'1');
}
}
template <class T>
void HuffmanTree<T>::calculateWPL(HuffmanTreeNode<T> *subTree,int i = 0){
if(subTree != NULL){
if(subTree->data != '#')
WPL += i*subTree->count; //i為當(dāng)前層數(shù),count為結(jié)點(diǎn)權(quán)值
calculateWPL(subTree->leftChild,++i); //前序遍歷
i--;
calculateWPL(subTree->rightChild,++i);
i--;
}
}
template <class T>
int HuffmanTree<T>::getWPL(){
return WPL;
}#pragma once
#define DafaultSize 50
template<class E>
class minHeap{
public:
minHeap(int size = DafaultSize);
~minHeap();
bool insert(const E& x);
bool removeMin(E& x);
private:
E *heap;
int currentSize;
int maxHeapSize;
void siftDown(int start, int m);
void siftUp(int start);
};#pragma once
#include "StdAfx.h"
#include "MinHeap.h"
template<class E>
minHeap<E>::minHeap(int size){
maxHeapSize = (DafaultSize<size)? size:DafaultSize;
heap = new E[maxHeapSize];
if(heap == NULL){
//cout<<"堆存儲(chǔ)分配失敗"<<endl;
}
currentSize = 0;
};
template<class E>
minHeap<E>::~minHeap(){
delete heap;
}
template<class E>
void minHeap<E>::siftDown(int start, int m){
int i = start; //初始位置
int j = 2*i+1; //j是i的左子女位置
E temp = heap[i];
while(j <= m){
if(j<m && heap[j] > heap[j+1]) //左子女大于右子女時(shí)，j指向右子女
j++;
if(temp <= heap[j])
break;
else{ //大則向上移
heap[i] = heap[j];
i = j;
j = 2*j+1;
}
}
heap[i] = temp;
};
template<class E>
void minHeap<E>::siftUp(int start){
int j = start;
int i = (j-1)/2; //i的左子女是j
E temp = heap[j];
while(j>0){
if(heap[i] <= temp) //如果父節(jié)點(diǎn)大
break;
else{ //如果父節(jié)點(diǎn)小,上滑
heap[j] = heap[i];
j = i;
i = (i-1)/2;
}
}
heap[j] = temp;
};
template<class E>
bool minHeap<E>::insert(const E& x){
if(currentSize == maxHeapSize){ //堆滿時(shí)
// cout<<"堆已滿"<<endl;
return false;
}
heap[currentSize] = x; //在heap尾插入x
siftUp(currentSize); //對(duì)x進(jìn)行上滑判斷
currentSize++;
return true;
};
template<class E>
bool minHeap<E>::removeMin(E& x){
if(currentSize == 0){ //堆空時(shí)
// cout<<"堆為空?。?<<endl;
return false;
}
x = heap[0]; //從heap頭獲取remove的數(shù)據(jù)
heap[0] = heap[currentSize-1]; //從heap尾獲取元素補(bǔ)到heap頭的位置
currentSize--; //元素個(gè)數(shù)減一
siftDown(0,currentSize-1); //再對(duì)heap從頭到尾進(jìn)行下滑判斷
return true;
};#pragma once
#include "HuffmanTree.cpp"
class sZip
{
public:
sZip(void);
~sZip(void);
void zip(char str1[],char str2[],HuffmanTreeNode<char>* subTree,int &size,char data[]);
void unzip(char str1[],char str2[]);
private:
bool codeEqual(char code1[],char code2[][128],int &num);
void getHuffCode(HuffmanTreeNode<char>* subTree,char code[][128],char data[]);
void strBinary(char str[],int &size);
void binaryStr(char str1[]);
};#include "StdAfx.h"
#include "sZip.h"
#include <iostream>
using namespace std;
sZip::sZip(void){
}
sZip::~sZip(void)
{
}
void sZip::zip(char str1[],char str2[],HuffmanTreeNode<char>* subTree,int &size,char data[]){
char code[128][128];
getHuffCode(subTree,code,data); //獲取subTree的哈弗曼編碼
unsigned int i = 0;
unsigned int n = -1;
for(; str1[i] != 0 ;i++){ //遍歷str1，把里面的字符轉(zhuǎn)化為哈弗曼編碼存在str2中
int j = 0;
while(data[j] != str1[i]){
j++;
if(data[j] == 0)
break;
}
if(data[j] == str1[i]){
for(int count = 0;code[j][count] != 0;count++)
str2[++n] = code[j][count];
str2[n+1]=0;
}
}
strBinary(str2,size); //把str2的每一個(gè)字符變成每一個(gè)bit，8個(gè)bit合成一個(gè)字符
}
void sZip::unzip(char str1[],char str2[]){
unsigned int count[128];
for(int i = 0;i < 127;i++)
count[i] = 0;
char code[128][128];
char data[128];
for(int i = 0;i < 128;i++)
code[i][0] = 0;
int i = 0;
for(;str1[i] != '#';i++)
data[i] = str1[i];
data[i] = 0;
int j = i+2;
i = -1;
while(1){
if(str1[j] != '#' && str1[j+1] == '#') //個(gè)位
count[++i] = str1[j]-48;
else if(str1[j+1] != '#' && str1[j+2] == '#'){ //十位
count[++i] = int(str1[j]-48)*10+int(str1[j+1]-48);
j++;
}
else if(str1[j+1] != '#' && str1[j+2] != '#' && str1[j+3] == '#'){ //百位
count[++i] = int(str1[j]-48)*100+int(str1[j+1]-48)*10+int(str1[j+2]-48);
j = j+2;
}
else if(str1[j+1] != '#' && str1[j+2] != '#' && str1[j+3] != '#'&& str1[j+4] =='#'){ //千位
count[++i] = int(str1[j]-48)*1000+int(str1[j+1]-48)*100+int(str1[j+2]-48)*10+int(str1[j+3]-48);
}
else if(str1[j] == '#' && str1[j+1] == '#') //讀完
break;
else
cout<<"讀取錯(cuò)誤"<<endl;
j = j+2;
}
HuffmanTree<char> tree;
tree.creat(data,count);
getHuffCode(tree.root,code,data);
j = j+2;
i = -1;
char tempchar[100000];
for(;str1[j] != 0;j++)
tempchar[++i] = str1[j];
tempchar[i+1] = 0;
binaryStr(tempchar); //把壓縮文件轉(zhuǎn)化為二進(jìn)制編碼
char tempcode[128];
j = -1;
int num;
int n = -1;
i = 0;
for(;tempchar[i] != 0;i++){ //遍歷tempchar，把它從哈弗曼編碼轉(zhuǎn)化為對(duì)應(yīng)的字符
tempcode[++n] = tempchar[i];
tempcode[n+1] = 0;
if(codeEqual(tempcode,code,num)){
str2[++j] = data[num];
for(n = 0;tempcode[n] != 0;n++) //重置tempcode
tempcode[n] = 0;
n = -1;
}
else
continue;
}
str2[++j] = 0;
}
void sZip::getHuffCode(HuffmanTreeNode<char>* subTree,char code[][128],char data[]){
for(int i = 0;data[i] != 0;i++)
findKey(subTree,data[i],code[i]);
}
void sZip::strBinary(char str[],int &size){
char str2[100000];
char bit[8];
int n = 0;
int count = 0;
while(str[n] == '1' || str[n] == '0'){
for(int i = 0;i < 8 ;i++){
if(str[n] == 0){
str[n] = '0';
str[n+1] = 0;
}
bit[i] = str[n];
n++;
}
str2[count] = 0;
for(int i = 0;i < 8 ;i++){
if(bit[i] == '1'){
char temp = 1;
str2[count] = (str2[count]<<1)|temp; //給它最后一位加上一即：左移一位，然后和00000001求或
}
else
str2[count] = (str2[count]<<1);
}
count++;
}
for(int i = 0;i <= count;i++)
str[i] = str2[i];
for(int i = count;str[i] != 0;i++)
str[i] = 0;
size = count;
}
void sZip::binaryStr(char str1[]){
char str2[100000];
int i = -1;
int n = 0;
while(str1[n] != 0){
int temp[8];
int tempchar = abs(str1[n]);
for(int count = 0;count < 8;count++){
temp[count] = tempchar%2;
tempchar /= 2;
}
if(str1[n]<0 && str1[n] > -128){ //當(dāng)為負(fù)數(shù)時(shí)，二進(jìn)制為正數(shù)第一位為1（符號(hào)位）的反碼最后一位加一（補(bǔ)碼）
temp[7] = 1;
for(int count = 0;count < 7;count++){ //求反碼
if(temp[count] == 0)
temp[count] = 1;
else
temp[count] = 0;
}
int x = 1; //進(jìn)位數(shù)
for(int count = 0;count < 8;count++){ //末位加一
if(temp[count] == 0){
if(x == 1){
temp[count] = 1;
x = 0;
}
}
else
if(x == 1)
temp[count] = 0;
}
}
for(int count = 7;count != -1;count--)
str2[++i] = char(temp[count]+48);
n++;
}
str2[++i] = 0;
for(int count = 0;count <= i;count++)
str1[count] = str2[count];
}
bool sZip::codeEqual(char code1[],char code2 [][128],int &num){
unsigned int size1 = 0;
unsigned int size2 = 0;
for(int i = 0;code1[i] != 0;i++)
size1++;
for(int i = 0;code2[i][0] != 0;i++)
size2++;
for(int i = 0;i < size2;i++){
int j = 0;
int size3 = 0;
for(int n = 0;code2[i][n] != 0;n++)
size3++;
for(;j < size1;j++){
if(code1[j] != code2[i][j])
break; //有一位不等于就直接跳出
}
if(j == size1 && j == size3){
num = i;
return true;
}
}
return false;
}
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
文章標(biāo)題：利用哈弗曼編碼進(jìn)行壓縮-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://muchs.cn/article0/depdio.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、定制網(wǎng)站、網(wǎng)站建設(shè)、App開(kāi)發(fā)、定制開(kāi)發(fā)、外貿(mào)建站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
- pytorch模型之train模式與eval模式的示例分析-創(chuàng)新互聯(lián)
- CSS的基本概念、作用、使用、語(yǔ)法和屬性-創(chuàng)新互聯(lián)
- Java虛擬機(jī)有什么用-創(chuàng)新互聯(lián)
- Android浮動(dòng)編輯框的具體實(shí)現(xiàn)代碼-創(chuàng)新互聯(lián)
- 在php中模擬POST提交的方法有哪些-創(chuàng)新互聯(lián)
- [附源碼]計(jì)算機(jī)畢業(yè)設(shè)計(jì)springboot游戲商城平臺(tái)論文-創(chuàng)新互聯(lián)
- 正確，理性的看待頁(yè)面關(guān)鍵詞出現(xiàn)的頻次、密度并合理運(yùn)用
- 頂級(jí)域名分類及域名注冊(cè)技巧 2021-01-30
- 網(wǎng)站域名注冊(cè)常見(jiàn)問(wèn)題 2016-09-22
- 網(wǎng)站域名怎么選？企業(yè)網(wǎng)站域名注冊(cè)注意事項(xiàng) 2021-02-10
- 域名注冊(cè)哪個(gè)好？ 2022-08-03
- 域名注冊(cè)技巧？ 2022-07-11
- 域名注冊(cè)機(jī)構(gòu)建議個(gè)人論壇關(guān)閉因很難成功備案 2021-01-14
- 域名注冊(cè)有多搶手？ 2023-01-22
- 域名注冊(cè)申請(qǐng)表應(yīng)包括哪些？如何購(gòu)買(mǎi)域名？ 2021-06-06
- 域名注冊(cè)哪一家 2022-07-07
- 你知道注冊(cè)域名要注意哪些事項(xiàng)嗎？ 2016-09-18
- 網(wǎng)站建設(shè)注冊(cè)域名的重要性 2017-02-07
- 短域名注冊(cè)會(huì)有哪些優(yōu)勢(shì)？ 2016-09-11