您现在的位置:首页 >> 技术文章 >> 数值分析 >> 内容

matlab代做highspeedlogic★四元Huffman编码

时间:2015-10-5 19:32:10 点击:

  核心提示:matlab代做,FPGA代做,淘宝,专业代做MATLAB、FPGA博士/硕士/本科毕业设计、项目仿真、Coursework、Assignment...

matlab代做FPGA代做淘宝专业代做MATLABFPGA博士/硕士/本科毕业设计项目仿真CourseworkAssignment

QQ: 1224848052

一.问题描述
随意输入一些字符串,统计每一个输入字符出现的个数,然后以它们作为权值,设计一 
个四元Huffman编/译码系统。

二.基本要求
(1)统计输入的字符串含有几个字符,即是计算出需多少个码元。
(2)调整码元的个数,以达到可以建立Huffman树。
(3)输出字符串中符号(码元)的个数。
(4)以每个字符出现的次数为权值,建立Huffman树,求出Huffman码。
(5)计算出编码的效率。
(6)对输入字符串进行译码。

三.测试数据
  测试数据:abcd;  abbccddw;  aadasdweqweqedsg
,
四.算法思想
构造哈夫曼树算法:
(1)用给定的一组权值{W1,W2,…,Wn},生成一个有n棵树组成的森林F={T1,T2,…Tn},  其中每棵树Ti只有一个结点,即权值为 Wi的根结点(也是叶子结点);
(2)从F中选择四个根结点权值最小的树,作为新树根的四个孩子,新树根的权值是四个孩 子根结点的权值之和;
(3)从F中删除这四棵树,另将新的四树加入F中;
(4)重复(2)和(3),直到F中只包含一棵树为止。

                      
 
编码  
   该函数实现对哈夫曼树的编码,先申请一个能存储字符编码的临时空间cd,编码从哈夫曼树的叶子结点开始,寻找其父母结点,然后根据父母结点判断孩子结点的位置,1的置0,2的置1,3的置2,4的置3,并将0,1,2,3这样的字符从后往前逆序存放在cd中,每求得一个叶子结点的编码,就将其复制到存储哈夫曼编码的头指正数组中,找完叶子结点的编码后就释放临时空间cd。           
                          
                     
对哈夫曼码译码 
   逐个读取存放在里边的编码字符,并与先前的编码相匹配,直到找到编码对应的原字符。
                             

五.模块划分

功能函数模块划分
void main()                                            //主函数
count(char *inp_str,int count_str[],char sa_str[])             //统计输入的字符和字符串
select(HuffmanTree HT,int k,int &s1,int &s2,int &s3,int &s4)   //挑选权值最小的的四个节点
creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int count_str[],char sa_str[])//建立霍夫曼树
HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)//给霍夫曼树的每个叶子节点分配二进制码
coding(HuffmanCode HC,char inp_str[],char get[])    //输出字符串的二进制编码
decode(HuffmanCode HC,char receive[],char s[])   //译码
code_ratio(char inp_str[],int count_str[],HuffmanCode HC)  //计算编码效率


六.源程序

#include
#include
#include
using namespace std;
#define n 100                    //设定输入最大的码元
#define m 133                   //在码元最大时,霍夫曼树的节点
int ad_num=0;                  //不平衡霍夫曼树时,调整的增加的个数
int tot_num=0;                  //霍夫曼树总的节点数
int num=0;                     //霍夫曼树的码元


//码点的存储结构
 struct CodeNode
{
    char ch;  //信源符号
    char bits[9]; //存放码字
    int len;//码字长度
};
typedef CodeNode HuffmanCode[n+1];//定义CodeNode存储结构的数组类型


//树节点的存储结构
 struct  HTNode
{
    int weight;
    int child1,child2,child3,child4;
    int parent;

};
 typedef HTNode HuffmanTree[m+1];

//统计输入的字符和字符串
int  count(char *inp_str,int count_str[],char sa_str[])
{
    char *p;
    int i,j;
    int temp[257];
    for(i=0;i<257;i++)
        temp[i]=0;
    for(p=inp_str;*p!='\0';p++)
    {
        temp[*p]++;
    }
    for(i=0,j=0;i<257;i++)
        if(temp[i]!=0)
        {
            j++;
            sa_str[j]=i;
            count_str[j]=temp[i];
        }


      if((j-1)%3!=0)
      {
       
          if(j%3==0)
          {
              count_str[++j]=0;
               ad_num=1;
          }
       
          else
          {
              count_str[++j]=0;
              count_str[++j]=0;
              ad_num=2;
          }
      }

      num=j;
      return j;
}


//挑选权值最小的的四个节点
void select(HuffmanTree HT,int k,int &s1,int &s2,int &s3,int &s4)
{
    int i,j;
    int minl=32767;
    //s1
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s1=j;
    //s2
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s2=j;
     //s3
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s3=j;
    //s4
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s4=j;

}
//建立霍夫曼树
void creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int count_str[],char sa_str[])
{
    int i,s1,s2,s3,s4;
    for(i=1;i<=tot_num;i++)
    {
        HT[i].child1=0;
        HT[i].child2=0;
        HT[i].child3=0;
        HT[i].child4=0;
        HT[i].parent=0;
        HT[i].weight=0;
    }
    for(i=1;i<=num;i++)
    {
        HT[i].weight=count_str[i];
    }

    for(i=num+1;i<=tot_num;i++)
    {
        select(HT,i-1,s1,s2,s3,s4);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[s3].parent=i;
        HT[s4].parent=i;

        HT[i].child1=s1;
        HT[i].child2=s2;
        HT[i].child3=s3;
        HT[i].child4=s4;
      
        HT[i].weight=HT[s1].weight+HT[s2].weight+HT[s3].weight+HT[s4].weight;
    }
    for(i=1;i<=num-ad_num;i++)
    {
        HC[i].ch=sa_str[i];
     
    }
}

 

//给霍夫曼树的每个叶子节点分配二进制码
void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)
{
    int c,p,i;
    char cd[n];
    int start;
    cd[num]='\0';
    for(i=1;i<=num;i++)
    {
        start=num;
        c=i;
        while((p=HT[c].parent)>0)
        {
            start--;
            if(HT[p].child1==c)
              cd[start]='0';
            if(HT[p].child2==c)
              cd[start]='1';
            if(HT[p].child3==c)
             cd[start]='2';
            if(HT[p].child4==c)
             cd[start]='3';

            c=p;
        }
        strcpy(HC[i].bits,&cd[start]);
        HC[i].len=num-start;
    }
}
//输出字符串的二进制编码
void coding(HuffmanCode HC,char inp_str[],char get[])
{
    int i,j=0;
    while(inp_str[j]!='\0')
    {
        for(i=1;i<=num-ad_num;i++)
        if(HC[i].ch==inp_str[j])
        {
            strcat(get,HC[i].bits);
            break;
        }
        j++;
    }
    strcat(get,"\0");
}
//译码
void decode(HuffmanCode HC,char receive[],char s[])
{
    char str[268];
    char cd[9];
    int i,j,k=0,p=0,cjs;
    while(receive[p]!='\0')
    {
        cjs=0;
        for(i=0;i
        {
            cd[i]=' ';
            cd[i+1]='\0';
            cd[i]=receive[p++];
            for(j=1;j<=num-ad_num;j++)
              if(strcmp(HC[j].bits,cd)==0)
              {
                str[k]=HC[j].ch;
                k++;
                cjs=1;
                break;
              }
        }
    }
    str[k]='\0';
    strcpy(s,str);
}

//计算编码效率
double code_ratio(char inp_str[],int count_str[],HuffmanCode HC)
{
    double up=0.0,down=0.0,temp=0.0;
    int i,len=strlen(inp_str);
    for(i=1;i<=num-ad_num;i++)
    {
        temp=count_str[i]/double(len);
        up-=temp*(log(temp)/log(4));
        down+=temp*HC[i].len;
    }
    return (up/down)*100;
}

int main()
{
    char sa_str[257];
    char inp_str[1000],s[1000];
    int count_str[257];
    int i;
    char receive[1000];
    HuffmanTree HT;
    HuffmanCode HC;

    cout<<"输入要编码的字符串"<<"  ";
    cin>>inp_str;
    num=count(inp_str,count_str,sa_str);
    cout<<"共有多少种字符"<<num-ad_num<<endl;
    tot_num=num+num/3;

    creat_HuffmanTree(HT,HC,count_str,sa_str);
    HuffmanEncoding(HT,HC);
    for(i=1;i
        cout<<"字符"<<HC[i].ch<<"出现的次数"<<count_str[i]<<",编码为"<<HC[i].bits<<endl;

    char get[1000];
    get[0]='\0';
    coding(HC,inp_str,get);
    cout<<"Huffman编码为:"<<get<<endl;
    cout<<"编码效率:"<<code_ratio(inp_str, count_str, HC)<<endl;
    cout<<"译码输入:";
     cin>>receive;
    decode(HC,receive,s);
    cout<<"译码:"<<s<<endl;
return 0;
}

作者:highspeedlogic 来源:highspeedlogic
  • 您是如何找到本站的?
  • 百度搜索
  • Google搜索
  • 查阅资料过程中
  • 论坛发现
  • 百度贴吧发现
  • 朋友介绍
本站最新成功开发工程项目案例
相关文章
  • 没有相关文章
相关评论
发表我的评论
  • 大名:
  • 内容:
  • matlab代做|matlab专业代做|matlab淘宝代做(www.hslogic.com) © 2018 版权所有 All Rights Reserved.
  • Email:highspeed_logic@163.com 站长QQ: 1224848052

    专业代做/代写/承接、MATLAB、SIMULINK、FPGA项目、博士/硕士/本科毕业设计、课题设计、论文,毕业论文,Coursework、Eassy、Assignment