C++ 哈夫曼树对文件压缩、加密实现代码

在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼。哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割。比如用lzw编码abc,就是1,2,3。但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性。而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110的时候就可以确定,已经走到尽头,回到根节点继续走,这样就避免了字符的分割,全部用1010101010101这样的路径表示字符,可以将8位压缩为1个char进行存储。在构造树的时候,将出现率高的char放在上面,这样路径就很短,自然就节省了存储空间。虽然哈夫曼压缩效率不是最高的,但还算比较乐观的。

哈夫曼除了压缩以外还可以用于加密,在将文本用哈夫曼编码时,需持久化生成的char计数链表结构,这样才能还原出树结构,而解码时路径正是依赖于树结构的。也就是说,这种编码是属于约定形式的编码,在编码时用原文本产生树结构,而存储的是树路径,解码的时候缺少树或树结构与原先不相符都是无法完成解码的,就好比,我用10代表a,你存的是10,你将10解释为 b或c等等都是不正确的。由于转换为了char存储,所以还需持久化最后填充的数目、文本长度,才能还原出原先的01表示的文本格式

这个代码有一定缺陷,由于当时考虑的是对文本进行处理,当文件中有char='\0' 时会出现错误,这个代码打的很费神,就不继续修复了,如有需要,可自行更改,解决的办法应该挺多的

先来个运行图:

源代码

#include<iostream>
#include<sstream>
#include<fstream> 

void WriteFile(char* path,const char* content,int length,bool append=false);
using namespace std;
struct Node{
  char data;
  Node* left;
  Node* right;
}; 

struct L_Node{
  int count;
  Node* node;
  L_Node* next;
}; 

Node* AddNode(int count,char data,L_Node*& first){
  L_Node* lnode=new L_Node();
  lnode->count=count;
  Node* node=new Node();
  node->data=data;
  node->left=0;
  node->right=0;
  lnode->node=node;
  if(first==0){
    first=lnode;
  }
  else{
    if(lnode->count<first->count){
      lnode->next=first;
      first=lnode;
    }
    else{
      L_Node* iter=first; 

      while(iter->next!=0&&iter->next->count<lnode->count){
        iter=iter->next;
      } 

      if(iter->next==0){
        iter->next=lnode;
        lnode->next=0;
      }
      else{
        lnode->next=iter->next;
        iter->next=lnode;
      }
    }
  }
  return node;
} 

void SaveLNodes(L_Node* first){
  stringstream ss;
  while(first!=0){
    ss<<(int)(unsigned char)first->node->data<<':'<<first->count<<' ';
    first=first->next;
  }
  WriteFile("nodes.txt",ss.str().c_str(),ss.str().length());
} 

void GetLNodes(L_Node*& first){
  char temp[32];
  ifstream in;
  in.open("nodes.txt",ios::in|ios::binary);
  while(!in.eof()){
    temp[0]=0;
    in>>temp;
    if(strlen(temp)>0){
      char* data=strtok(temp,":");
      char* count=strtok(0,":");
      AddNode(atoi(count),atoi(data),first);
    } 

  }
} 

void BuildSortedList(char* content,L_Node*& first,int length){
  int array[256]={
    0
  }; 

  for(int i=0;i<length;i++){
    array[(unsigned char)content[i]]++;
  } 

  for(int i=0;i<256;i++){
    if(array[i]>0){
      AddNode(array[i],(char)i,first);
    }
  }
  SaveLNodes(first);
} 

void BuildTree(L_Node*& first,Node*& root){//get l1->node,l2->node,remove l1,l2,then put l3 into list,then set l3->left and l3->right
  if(first->next==0){
    Node* node=new Node();
    root=node;
    root->right=0;
    node=new Node();
    node->data=first->node->data;
    node->left=0;
    node->right=0;
    root->left=node;
    delete first;
    return;
  } 

  while(first->next!=0){
    int count=first->count+first->next->count;
    Node* node1=first->node;
    L_Node* temp=first;
    first=first->next;
    delete temp;
    Node* node2=first->node;
    temp=first;
    delete temp;
    first=first->next;
    root=AddNode(count,0,first);
    root->left=node1;
    root->right=node2;
    //cout<<(int)node1->data<<':'<<(int)node2->data<<endl;
  }
  delete first;
} 

void PreOrderTraversal(Node* node,char* track,int branch,char** table){
  if(node!=0){ 

    char* track2=0; 

    if(branch==0){
      track2=new char[strlen(track)+2];
      sprintf(track2,"%s0\0",track);
    }
    else if(branch==1){
      track2=new char[strlen(track)+2];
      sprintf(track2,"%s1\0",track);
    }
    else{
      track2=new char[strlen(track)+1];
      sprintf(track2,"%s\0",track);
    } 

    if(node->data!=0){
      table[(unsigned char)node->data]=track2;
    } 

    PreOrderTraversal(node->left,track2,0,table);
    PreOrderTraversal(node->right,track2,1,table); 

    if(node->data==0){
      delete track2;
    }
  }
} 

void PreOrderTraversal(Node* node){
  if(node!=0){
    cout<<(int)(unsigned char)node->data<<endl;
    PreOrderTraversal(node->left);
    PreOrderTraversal(node->right);
  }
} 

char* Encode(const char* content,char** table,int length){ 

  stringstream ss; 

  for(int i=0;i<length;i++){
    if((unsigned char)content[i]==0){ 

    }
    else{
      ss<<table[(unsigned char)content[i]];
    }
  } 

  char* encoded_content=new char[ss.str().length()+1];
  memcpy(encoded_content,ss.str().c_str(),ss.str().length());
  encoded_content[ss.str().length()]=0;
  return encoded_content;
} 

int BinToDec(char* bin_content){
  int number=0;
  int cur=1;
  for(int i=7;i>=0;i--){
    number+=(bin_content[i]-'0')*cur;
    cur*=2;
  }
  return number;
}  

char* BinToCharText(const char* bin_content,int& fill_count,int& save_length){
  int length=strlen(bin_content); 

  fill_count=8-length%8; 

  if(fill_count>0){
    char* temp=new char[length+fill_count+1]; 

    char temp1[fill_count];
    for(int i=0;i<fill_count;i++){
      temp1[i]='0';
    } 

    sprintf(temp,"%s%s",bin_content,temp1);
    temp[length+fill_count]=0;
    bin_content=temp;
  } 

  length+=fill_count; 

  save_length=length/8; 

  char* text=new char[length/8+1];
  for(int i=0;i<length;i+=8){
    char temp[8];
    memcpy(temp,bin_content+i,8);
    text[i/8]=(char)BinToDec(temp); 

  }
  text[length/8]=0; 

  if(fill_count>0){
    delete bin_content;
  } 

  return text;
} 

char* DecToBin(int num){
  char* bin=new char[8];
  if(num<0){
    num=256+num;
  } 

  for(int i=7;i>=0;i--){
    bin[i]=num%2+'0';
    num/=2;
  }
  return bin;
} 

char* CharTextToBin(char* text,int fill_count,int save_length){
  int length=save_length; 

  char* content=new char[8*length+1]; 

  int pos=0;
  for(int i=0;i<length;i++){
    int number=text[i];
    char* bin=DecToBin(number);
    memcpy(content+pos,bin,8);
    pos+=8;
    delete bin;
  } 

  content[8*length-fill_count]=0; 

  return content;
} 

char* Decode(const char* encode_content,Node* tree){
  stringstream ss;
  Node* node=tree; 

  for(int i=0;i<strlen(encode_content);i++){
    if(encode_content[i]=='0'){
      node=node->left;
    }
    else if(encode_content[i]=='1'){
      node=node->right;
    } 

    if(node->data!=0){
      ss<<node->data;
      node=tree;
    }
  }
  char* decode_content=new char[ss.str().length()+1];
  memcpy(decode_content,ss.str().c_str(),ss.str().length());
  decode_content[ss.str().length()]=0;
  return decode_content;
} 

void ReleaseTable(char** table){
  for(int i=0;i<256;i++){
    if(table[i]!=0){
      delete table[i];
    }
  }
} 

void PostOrderTraversal(Node* node){
  if(node!=0){
    PostOrderTraversal(node->left);
    PostOrderTraversal(node->right);
    delete node;
  }
}  

char* ReadFile(char* path,long& length){
  char* content=0;
  ifstream in;
  in.open(path,ios::in|ios::binary);
  in.seekg(0,ios::end);
  length=in.tellg();
  content=new char[length+1];
  in.seekg(0,ios::beg);
  int i=0;
  while(!in.eof()){
    content[i++]=in.get();
  }
  content[length]=0;
  in.close();
  return content;
} 

char* ReadFile(char* path,int& fill_count,int& save_length){
  char* content=0;
  ifstream in;
  in.open(path,ios::in|ios::binary);
  in>>fill_count>>save_length;
  long cur=in.tellg()+(long)1;
  in.seekg(0,ios::end);
  long length=in.tellg()-cur;
  content=new char[length+1];
  in.seekg(cur,ios::beg);
  int i=0;
  while(!in.eof()){
    content[i++]=in.get();
  }
  content[length]=0;
  in.close();
  return content;
} 

void WriteFile(char* path,const char* content,int length,bool append){
  ofstream out;
  if(append){
    out.open(path,ios::out|ios::binary|ios::app);
  }
  else{
    out.open(path,ios::out|ios::binary);
  } 

  out.write(content,length);
  out.close();
} 

int main(){
  long length;
  char* content=ReadFile("content.txt",length); 

  L_Node* first=0; 

  BuildSortedList(content,first,length); //create nodes list and save to nodes file
  //GetLNodes(first);//get and recreate nodes from file 

  Node* root=0;//used for buildtable and decode
  BuildTree(first,root);//build tree by nodes list and release sorted list 

  char* table[256]={//build table,used for encode
    0
  }; 

  PreOrderTraversal(root,"",-1,table);//create table 

  char* encode_content=Encode(content,table,length);//convert content to encoded bin text
  cout<<encode_content<<endl;
  delete content; 

  ReleaseTable(table);//release table when encode finished 

  int fill_count;
  int save_length;
  char* save_text=BinToCharText(encode_content,fill_count,save_length);//convert encoded bin text to char text and save these text to file
  delete encode_content;
  char head_info[32];
  sprintf(head_info,"%d %d ",fill_count,save_length);
  WriteFile("encoded_content.txt",head_info,strlen(head_info));
  WriteFile("encoded_content.txt",save_text,save_length,true);
  delete save_text;
  save_text=ReadFile("encoded_content.txt",fill_count,save_length);//read fill_count、save_length、encoded char text from file 

  char* bin_text= CharTextToBin(save_text,fill_count,save_length);//convert char text to bin text
  delete save_text; 

  char* decode_content=Decode(bin_text,root);//decode by bin_text and tree
  cout<<decode_content<<endl;
  delete bin_text;
  delete decode_content; 

  PostOrderTraversal(root);//release tree 

  return 0;
} 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++实现哈夫曼树简单创建与遍历的方法

    本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,

  • 解析C++哈夫曼树编码和译码的实现

    一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

  • C++数据结构之文件压缩(哈夫曼树)实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • 基于C语言利用哈夫曼树实现文件压缩的问题

    一.哈夫曼树 具有n个权值的n个叶子结点,构造出一个二叉树,使得该树的带权路径长度(WPL)最小,则称此二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 注意:哈夫曼树是带权路径长度最短的树,且权值越大的叶子结点离根结点越近. 二.哈夫曼编码         哈夫曼编码是一种编码方式,又称"霍夫曼编码",其是可变字长的编码(VCL)的一种,是由霍夫曼于1952年提出的一种编码方式,有时被称为最佳编码,一般称为Huffman编码. 那么我们为什么要使用哈夫曼编码进行压缩?

  • C++ 哈夫曼树对文件压缩、加密实现代码

    在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

  • Java实现赫夫曼树(哈夫曼树)的创建

    目录 一.赫夫曼树是什么? 1.路径和路径长度 2.节点的权和带权路径长度 3.树的带权路径长度 二.创建赫夫曼树 1.图文创建过程 2.代码实现 一.赫夫曼树是什么? 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 图1 一棵赫夫曼树 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.

  • java数据结构图论霍夫曼树及其编码示例详解

    目录 霍夫曼树 一.基本介绍 二.霍夫曼树几个重要概念和举例说明  构成霍夫曼树的步骤 霍夫曼编码 一.基本介绍 二.原理剖析 注意: 霍夫曼编码压缩文件注意事项 霍夫曼树 一.基本介绍 二.霍夫曼树几个重要概念和举例说明  构成霍夫曼树的步骤 举例:以arr = {1  3  6  7  8   13   29}  public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8

  • C++详解哈夫曼树的概念与实现步骤

    目录 一. 基本概念 二.构造哈夫曼树 三.哈夫曼树的基本性质 四.哈夫曼编码 五.哈夫曼解码 六.文件的压缩和解压缩 一. 基本概念 结点的权: 有某种现实含义的数值 结点的带权路径长度: 从结点的根到该结点的路径长度与该结点权值的乘积 树的带权路径长度: 树上所有叶结点的带权路径长度之和 哈夫曼树: 在含有 n n n个带权叶结点的二叉树中, w p l wpl wpl 最小 的二叉树称为哈夫曼树,也称最优二叉树(给定叶子结点,哈夫曼树不唯一). 二.构造哈夫曼树 比较简单,此处不赘述步骤

  • Java利用哈夫曼编码实现字符串压缩

    赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码 在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li

  • 图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • Python数据结构之哈夫曼树定义与使用方法示例

    本文实例讲述了Python数据结构之哈夫曼树定义与使用方法.分享给大家供大家参考,具体如下: HaffMan.py #coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class HaffTree: def __init__(self): sel

  • C++实现哈夫曼树的方法

    序言 对于哈夫曼编码,个人的浅薄理解就是在压缩存储空间用很大用处. 用一个很简单例子,存储一篇英文文章时候,可能A出现的概率较大,Z出现的记录较小,如果正常存储,可能A与Z存储使用的空间一样.但是用哈夫曼编码方式,A经常出现,所用编码长度就短. 构造哈夫曼树,生成哈夫曼编码 一.定义节点类型 struct Node { char C; long key; Node *Left, *Right,*parent; Node() { Left = Right = NULL; } }; 二.定义树类型(

随机推荐