精华内容
下载资源
问答
  • 文本哈夫曼编码和译码 哈夫曼编码是最基本字符压缩编码。对文本进行哈夫曼编码后再进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据...

    文本串的哈夫曼编码和译码

    哈夫曼编码是最基本的字符压缩编码。对文本进行哈夫曼编码后再进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。 请设计一个程序,输入一行字符文本串(最大长度为10000个字符),构造其哈夫曼编码。根据需要(传输前)选择对字符文本进行编码(将字符文本转换为哈夫曼0-1编码),或对已编码的数据(接收后)进行译码(将0-1编码还原为字符文本)。
    具体:
    (1)初试化(I):读入一行文本,根据字符分布建立哈夫曼树,构造字符的哈夫曼编码(用于编码和译码),输出“Huffman code established!“”;
    (2)编码(C):使用得到的哈夫曼编码对原始字符文本进行编码,输出;
    (3)译码(D)::对编码后的0-1文本进行译码(还原为原来的字符文本),输出;
    (4)退出(X):结束;注:如果编码或译码时,哈夫曼编码还没建立,应提示"Huffman code does not exist!”
    例如:
    样例输入:
    I
    Welcome to the school of computer science and technology.
    C
    D
    11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
    X
    样例输出:
    Huffman code established!
    11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
    Welcome to the school of computer science and technology.

    要注意:
    string不能malloc,要用new! string不能malloc,要用new! string不能malloc,要用new!
    就是因为这个,codeblocks上边可以运行通过,OJ上不行,两天的段错误啊……
    建立哈夫曼树的方法:
    1.找到两个权值最小的点(若权值一样,则选择前面的),然后将这两个点连接到一个“根”上(根的权值是两个点权值之和),将“根”放到原序列最后,将选择的两个点从原序列删除(原序列指删除重复字符后的给定序列);
    2.重复上述操作,直至原序列剩余一个点,将其标记为根节点。

    包括空格的字符串这样输入:

    getchar();
    char c;
    scanf("%c",&c);
    int i=0;
    while(c!='\n')
    {
        str[i]=c;
        i++;
        scanf("%c",&c);
        }
    len=i;
    

    完整代码如下:

    #pragma GCC optimize(3,"Ofast","inline")
    #pragma G++ optimize(3)
    #include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <fstream>
    #include <algorithm>
    #include <cmath>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cstring>
    #include <map>
    #include <stack>
    #include <set>
    #include <sstream>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<ll,ll> pll;
    typedef pair<int,int> pii;
    typedef queue<int> q_i;
    typedef queue<string> q_s;
    typedef queue<double> q_d;
    typedef queue<ll> q_ll;
    typedef queue<char> q_c;
    typedef priority_queue<int> pq_i;
    typedef priority_queue<string> pq_s;
    typedef priority_queue<double> pq_d;
    typedef priority_queue<ll> pq_ll;
    typedef stack<int> s_i;
    typedef stack<string> s_s;
    typedef stack<double> s_d;
    typedef stack<ll> s_ll;
    typedef stack<char> s_c;
    typedef map<ll,ll> m_ll_ll;
    typedef map<int,ll> m_i_ll;
    typedef map<string,ll> m_s_ll;
    typedef map<char,int> m_c_i;
    typedef map<char,ll> m_c_ll;
    #define rep(i,l,r) for(ll i=l;i<=r;i++)
    #define per(i,l,r) for(ll i=r;i>=l;i--)
    #define eif else if
    #define N 3005
    #define mm(dp) memset(dp,0,sizeof(dp))
    #define mm1(dp) memset(dp,-1,sizeof(dp))
    #define mm2(dp) memset(dp,0x3f,sizeof(dp))
    #define IT set<int>::iterator
    #define fs(n) fixed<< setprecision(n)
    #define inf 0x3f3f3f3f
    const double e=2.71828182845;
    const double pi = acos(-1.0);
    map<char,int>mapp;
    map<char,string>mapp1;
    typedef struct
    {
        string s1;
        int num;
    }STU;
    typedef struct
    {
        string s1,s0;
        int num;
    }STU1;
    bool cmp(STU x,STU y)
    {
        return x.num>y.num;
    }
    typedef struct node
    {
        string data;
        struct node *left,*right;
    }HuffmanTreeNode,*PtrHuffman;
    class Haffman
    {
        public:
        PtrHuffman head=NULL;
        PtrHuffman p[100005];
        void create1(int nm,STU *stu)
        {
            int u=0;
            rep(i,1,nm)
            {
                PtrHuffman t=new HuffmanTreeNode;
                t->data = stu[i].s1;
                t->left = t->right = NULL;
                p[i]= t;
            }
            rep(i,1,nm-1)
            {
                int fi=inf,se=inf;
                int fi1=0,se1=0;
                rep(j,1,nm+u)
                {
                    if(stu[j].num>0&&stu[j].num<fi)
                    {
                        fi=stu[j].num;
                        fi1=j;
                    }
                }
                rep(j,1,nm+u)
                {
                    if(stu[j].num>0&&stu[j].num<se&&j!=fi1)
                    {
                        se=stu[j].num;
                        se1=j;
                    }
                }
                PtrHuffman q=new HuffmanTreeNode;
                q->data=p[fi1]->data+p[se1]->data;
                q->left=p[fi1];
                q->right=p[se1];
                u++;
                stu[nm+u].s1=stu[fi1].s1+stu[se1].s1;
                stu[nm+u].num=stu[fi1].num+stu[se1].num;
                p[nm+u]=q;
                stu[fi1].num=-1;
                stu[se1].num=-1;
                head=q;
            }
        }
        void bianli(struct node *t1,int u)
        {
            if(t1==NULL)
                return;
            if(u==0)
                cout<<t1->data<<endl;
            else
            {
                cout<<u<<" ";
                cout<<t1->data<<endl;
            }
            bianli(t1->left,u+1);
            bianli(t1->right,u+1);
        }
    
        void bianli1(struct node *t1,char ch,string str)
        {
            if(t1==NULL)
                return;
            string s1="";
            s1+=ch;
            string ss=t1->data;
            if(ss==s1)
            {
                mapp1[ch]=str;
                return;
            }
            else
            {
                string s=t1->data;
                int len=s.size();
                int flag=0;
                rep(i,0,len)
                {
                    if(s[i]==ch)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==0)
                    return;
                else
                {
                    bianli1(t1->left,ch,str+"0");
                    bianli1(t1->right,ch,str+"1");
                }
            }
        }
        STU1 bianli2(struct node *t1,string str)
        {
            if(t1->data.size()==1)
            {
                STU1 stu;
                stu.s1=t1->data;
                int len=str.size();
                stu.s0=str;
                return stu;
            }
            char ch=str[0];
            int len=str.size();
            str=str.substr(1,len-1);
            if(ch=='0')
            {
                return bianli2(t1->left,str);
            }
            if(ch=='1')
            {
                return bianli2(t1->right,str);
            }
        }
    };
    int len;
    int main()
    {
        //ios::sync_with_stdio(false);
        //cin.tie(0);
        //cout.tie(0);
        Haffman ha;
        char str[10005];
        int uu=0;
        while(1)
        {
            char ch;
            cin>>ch;
            if(ch=='X')
                break;
            eif(ch=='I')
            {
                getchar();
                char c;
                scanf("%c",&c);
                int i=0;
                while(c!='\n')
                {
                    str[i]=c;
                    i++;
                    scanf("%c",&c);
                }
                len=i;
                string ss="";
                rep(i,0,len-1)
                {
                    if(mapp[str[i]]==0)
                    {
                        mapp[str[i]]=1;
                        ss+=str[i];
                    }
                    eif(mapp[str[i]]!=0)
                    {
                        mapp[str[i]]++;
                    }
                }
                int len1=ss.size();
                STU stu[10005];
                rep(i,0,len1-1)
                {
                    string s0="";
                    char c=ss[i];
                    s0+=c;
                    stu[i+1].s1=s0;
                    stu[i+1].num=mapp[c];
                }
                ha.create1(len1,stu);
                cout<<"Huffman code established!"<<endl;
                uu=1;
            }
            eif(ch=='C')
            {
                if(uu==0)
                {
                    cout<<"Huffman code does not exist!"<<endl;
                }
                else{
                rep(i,0,len-1)
                {
                    char cc=str[i];
                    ha.bianli1(ha.head,cc,"");
                    cout<<mapp1[str[i]];
                }
                cout<<endl;
            }}
            eif(ch=='D')
            {
                if(uu==0)
                {
                    cout<<"Huffman code does not exist!"<<endl;
                }
                else{
    
                string s2;
                cin>>s2;
                while(1)
                {
                    if(s2=="")
                        break;
                    STU1 huan=ha.bianli2(ha.head,s2);
                    cout<<huan.s1;
                    s2=huan.s0;
                }
                cout<<endl;
            }}
        }
        return 0;
    }
    
    展开全文
  • 对一个 ASCII 编码的文本文件中字符进行哈夫曼编码,生成编码 文件;反过来,可将编码文件译码还原为一个文本文件。 (1) 从文件中读入任意一篇英文短文(文件为 ASCII 编码扩展名为 txt); (2) 统计并输出...
  • /** 一个lzw 压缩算法 编码 和译码 实现程序* 压缩一个已有文件(sourcefile)到目标文件(targetfile) ,然后读取压缩码;* 此程序采用12位压缩码,词典作多可以存储2^12个词条;* 生成压缩码 经过解压缩...

    package com.anywhere;
    import java.io.*;

    /** 一个lzw 压缩算法的 编码 和译码 的实现程序
    * 压缩一个已有文件(sourcefile)到目标文件(targetfile) ,然后读取压缩的码;
    * 此程序采用12位压缩码,词典作多可以存储2^12个词条;
    * 生成的压缩码 经过解压缩,可以恢复为原先文件;
    *对文本文件的压缩率,大约为60%,尚不能支持中文的文件输入:)
    * @author Lai Yongxuan     2003.3.12
    * @version 1.0
    */
    public class lzwCode
    {
      /**
      @see Dictionary
      */
       Dictionary dic=new Dictionary();
       /**count1: the bytes of input file,count2:the bytes of output  file
       */
       int count1=0,count2=0;
       /** the max number of the dictionary;
       *this number can be add to the codebuf[] if
       * the file has only odd words to be treated ; 
       */
       /** the input file  : character file or coding file
       */
       BufferedInputStream in;
       /** the output file: character file or coding file
       */
       BufferedOutputStream out;
       final short END=4095;
        
    /**the entry of the class,and check the arguments first
     @param args array of string arguments
      -c sourceFile [targetFile] 建立一个压缩文件
      -d sourceFile [targetFile]  解压缩一个文件
     @return No return value
     @exception No ecceptions thrown
    */
      public static void main(String []args)
        {
            if ( args.length<=1 || args.length>4 )
            {
                System.out.println("-c sourceFile [targetFile] [-dic]  建立一个压
    缩文件\n");
                System.out.println("-d sourceFile [targetFile] [-dic]  解压缩一个
    文件\n");
            }
            else if(! ( args[0].equals(new String("-c") )||args[0].equals(new
    String("-d") )  )  )
            {
                System.out.println("-c sourceFile [targetFile]  建立一个压缩文件\
    n");
                System.out.println("-d sourceFile [targetFile]  解压缩一个文件\n"
    );
            }
            else if(args.length>=2)
            {
              lzwCode a=new lzwCode(args);
              a.run(args);
             
            }
            return ;
        }
       
       
    /** the constuctor of the class of "lzwCode "
    *@param args array of string arguments input at the main()
    *
    *
    */
        public lzwCode(String []args)
        {
       
            
            try{
                    String f=new String();
                    in =new BufferedInputStream(
                      new FileInputStream(
                       new File(args[1])));
                      if(args.length==3 && !args[2].equals(new String("-dic")))
                      {
                        f=args[2];
                      }
                      else
                      {
                        int i=args[1].lastIndexOf(new String(".") );
                        f=args[1].substring(0,i)+((args[0].equals("-c")
    )?".lzw":".dlzw");
                      }
                     out=new BufferedOutputStream(
                         new FileOutputStream(
                          new File(f)));
                    
             
               
              }//try
              catch(FileNotFoundException e )
                  {
                    System.err.println(e);
                        return;
                  }
     
               catch(IOException e )
                {
                    System.err.println(e);
                        return;
                }   

             
        }
    /** the entry of the process;
    @param Srring args[]: array of string arguments input at the main()
             BufferedInputStream in: the input charstream file
             BufferedOutputStream out:the output code stream file
    * @return No return value
    */

    public void run(String args[] )
    {
       
         if(args[0].equals(new String("-c"))   )
              {
                code(in,out);
                }
                else
                {
                decode(in,out);
                }
      if(args[args.length-1].equals(new String("-dic") ))
           System.out.println(dic.toString ());
       
    }

    /** input the charstream from a file,and output the code stream to anpther
    file
    * @param BufferedInputStream in: the input charstream file
             BufferedOutputStream out:the output code stream file
    * @return No return value

    *
    */
      public void code(BufferedInputStream in,BufferedOutputStream out)
      {
        System.out.println("coding...\n"+ ".......\n");
       
        //a:the buffer byte read from the input file,then to be converted to
    String
        //buf: the codestream to store in the code file
        //prefix :the pre_String of the dictory
        // the indexbuf[] is the index of dictionary to be converted in
        // the code file
        //str: the current charecter of the character input Stream
        byte a[]=new byte[1],buf[]=new byte[3];
       
        String prefix="",cur="";
        byte i=0;
        short indexbuf[]=new short[2];
       
        String str=null;
        try{
        short m=0;
        while(  (a[0]=(byte)in.read() )  != -1 )
          {
            cur=new String(a);// be converted
            count1++; // the number of bytes of  input file
            str=prefix;
            str=str.concat(cur);
            m=(short)dic.indexOf(str); 
          
            if( m!=-1)//the prefix is in the dictionary,
            {
                prefix=str;
             }
            else//
            {
               
                if(i==0)//the first indexbuf,store in codebuf[]
                {
                   indexbuf[0]=(short)dic.indexOf(prefix);
                   i=1;
                }
                else// now have 2 index number,then ouput to the code file
                {
                  indexbuf[1]=(short)dic.indexOf(prefix);
                  zipOutput(out,indexbuf);
                 
                  count2+=3;//3 bytes stored to the code file
                  i=0;
                }
                    
                dic.add(str);
                prefix=cur;
               
            }//else
             
        
          }//while
         
        //  System.out.println("i="+i);
          if(i==(byte)1) //this is the case that the
                   //input file has only odd index number to store
          {
            indexbuf[1]=END;//put a special index number
                            //(the max number of the dictionary) END to the
    code file
            zipOutput(out,indexbuf);
            count2+=3;
               
          }
         
          dic.add(str);
          in.close ();
          out.close ();
       
         
          System.out.println("zip rate:"+(float)count2*100/count1+"% ");
         }catch(IOException e )
                {
                    System.err.println(e);
                        return;
                }
           catch(OutDictionaryException e)
           {    
                   System.err.println(e);
                      return;
            }
               

      }
    /** input the code stream from a file,and output the char stream to anpther
    file
    * @param BufferedInputStream in: the input code   file
             BufferedOutputStream out:the output charstream  stream file
    * @return No return value
    * @exception No return Exception
    *
    *
    */ public void decode(BufferedInputStream in,BufferedOutputStream out)
      {
        System.out.println("decoding...\n"+".......\n");
       
        short precode=0,curcode=0;
        String prefix=null;
        short i=0;
        short bufcode[]=new short[2];//2 code read from the code file
        boolean more=true;//indicate the end of the file or some error while
    input the file
       
       
       
      //    DataOutputStream out2=new DataOutputStream(out);   
        try{
       
        more=zipInput(in,bufcode);//first input 2 code
        if(more)
        {
         curcode=bufcode[0];
      // out2.writeChars(dic.getString(curcode));
         stringOut(out,dic.getString(curcode) );
        
        
        }
        else
         System.out.println("error in the beginning...");

         while(more)
          {
             precode=curcode;
       
           
             if(i==0)
             {
              curcode=bufcode[1];
              i=1; 
             }
            else
            {
                more=zipInput(in,bufcode);
         
                curcode=bufcode[0];
                if(bufcode[1]==END)
                   {
                  
                    stringOut(out,dic.getString (bufcode[0] ));
                        break;
                    }      
                 i=0;
            }
                   
       
             if(curcode<dic.length())//if the prefix string can be found in the
    dictory
             {
            //  out2.writeChars(dic.getString(curcode));
                stringOut(out,dic.getString(curcode) );
                prefix=dic.getString(precode);
                       
                prefix+=(dic.getString(curcode)).substring(0,1);
                dic.add(prefix);
                   
            }
            else
            {
                prefix=dic.getString(precode);
                prefix+=prefix.substring(0,1);
            //  out2.writeChars(prefix);
                stringOut(out,prefix );
                dic.add(prefix);
           
               
            }//else
          }//while
        
       
          in.close ();
          out.close ();
     
        }catch( OutDictionaryException e )
                {
                   System.err.println(e);
                        return;
                   }    
      catch(IOException e)
        {
            System.err.println(e);
                        return;
        }           
       
      } 

    /** output the index number of the dictionary  to the code stream;
     ecah index is converted to 12 bit ;and output 2 short numbers at a
     time
    * @param  BufferedOutputStream out:the output charstream  stream file
              short index[]:the 2 short array to be converted to code form
    * @return No return value
    * @exception No return Exception
    *
    *
    */
      private void zipOutput(BufferedOutputStream out,short index[])
      {
        try{
       
       
        byte buf[]=new byte[3];
     
        buf[1]=(byte)(index[0]<<4);
       
        buf[0]=(byte)(index[0]>>4);
        
        buf[2]=(byte)index[1];
        buf[1]+=(byte)(index[1]>>8);
       
        out.write(buf,0,3);
     
        //out put the decoding
    //  System.out.println(index[0]+"\t"+index[1]+"\t"); 
     
     /*     short codebuf[]=new short[2];
           
        //codebuf[0]=(short)(buf[0]<<4);
        codebuf[0]=toRight(buf[0],4);
        codebuf[0]+=(short)(toRight(buf[1],0)>>4);
       
        //codebuf[1]=(short)buf[2];
          codebuf[1]=toRight(buf[2],0);
        //codebuf[1]=(byte)(buf[1]<<4);
        byte temp=(byte)(toRight(buf[1],4));
       
        codebuf[1]+=toRight(temp,4);
      
      
       // codebuf[1]+=(short)(buf[1]<<4);
       
        System.out.println("\t"+codebuf[0]+"\t"+codebuf[1]);
        */     
         }catch( IOException e )
           {
                System.err.println(e);
                        return;
           }    
       
      }
     
    /** convert the  code stream to the file in the original way;
    * each time deel with 3 bytes,and return  2 index number
    * @param  BufferedOutputStream in :the input code  stream file
              short index[]:the 2 short array buffer of index of dictionary
    * @return return loolean value:if not the end of file and the converted
    code
              is right ,return true;else ,return false
    * @exception No return Exception
    *
    *
    */
      private  boolean  zipInput(BufferedInputStream in,short codebuf[])
      {
        byte buf[]=new byte[3],temp;
        //int intbuf[]=new int[3],temp;
        short le=(short)dic.length();
        try{       
      
        if(in.read(buf,0,3)!=3)
         {
             System.out.println("the end of the file!");
             return false;
          }
        //codebuf[0]=(short)(buf[0]<<4);
        codebuf[0]=toRight(buf[0],4);
        codebuf[0]+=(short)(toRight(buf[1],0)>>4);
       
        //codebuf[1]=(short)buf[2];
        codebuf[1]=toRight(buf[2],0);
        //codebuf[1]=(byte)(buf[1]<<4);
        temp=(byte)(toRight(buf[1],4));
        codebuf[1]+=toRight(temp,4);
      //  System.out.println(codebuf[0]+"\t"+codebuf[1]);
          
           
        if(codebuf[0]<-1 ||codebuf[1]<-1)
          {
            System.out.println("erroring while getting the code
    :"+codebuf[0]+"\t"+codebuf[1]);
            System.out.println(dic);
            return false;
          }
        //System.out.println(codebuf[0]+"\t"+codebuf[1]);  
     }
      catch(IOException e )
            {
                 System.err.println(e);
                      return false;
            }
      return true;
     }
     
     /**converte a byte number,to the short form;and
      * shift a byte n bits to the right;and reglect whether
      *&the byte is positive or negective
      *@param byte:the byte you want to shift
      *            int :the bits you shift to the right
      *@return int :the result of the shifted
     */ private short toRight(byte buf,int n)
     {
        short s=0;
        for(short i=7;i>=0;i--)
        {
            if( ( (1L<<i)&buf )!=0 )
              s+=(short)(1L<<(i+n));
        }
        return s;
     }

     /**output the String to a file,but in a form of "byte" way;
     * in order to be ecactly as the oririnal file ,i deel with
    *  the file in bytes form
    *@param BufferedOutputStream out:the output file
    *       String str:the buf of String to be output
    */ private  void stringOut(BufferedOutputStream out,String str)
       {
          byte a[]=str.getBytes();
          try{
          out.write(a,0,str.length());
        }
        catch(IOException e )
            {
                 System.err.println(e);
                     
            }
           
      }

     


    //Dictionary.java 

    package com.anywhere;
    import java.util.*;
    /**the Exception to indicate that the dictionary is too large
    */
     class OutDictionaryException extends Exception
          {
            public  String toString()
                {
                    return (super.toString ()+"out of the dictionary size!!");
                }
          }
    /**
     a dictonry that  contains at most 2^12 words,and should be inited
     at the beginning; it can be looked up,can be added and return the size
    @author :Lai Yongxuan  2002.3.10
    @version :1.0
    */
    public class Dictionary
    {
        /** the container of the dictionary,use ArrayList
        *@see java.util.ArrayList
        */
        ArrayList ar=new ArrayList();
       
        /**the constuctor of the class,and put the 128 ASCII to the dictionary 
        */
        public Dictionary()
        {
          // byte i[]=new byte[1];
           char c[]=new char[1];
           for( c[0]=0;c[0]<128;c[0]++)
           {
            
             ar.add(new String(c));
            
           }
        }
        /**return the index number of the word in the dictionary
        */
        public int indexOf(String a)
        {
            return ar.indexOf(a);
        }
        /**add a string to the dictionary
        @param String :the word to be added
        @return NO returned value
        @Exception OutDictionaryException is thrown if the dictionary is too
            large ,it only can contain 4096(2^12) words at most
        */
        public void add (String a) throws OutDictionaryException
        {
          
           if( length()<4096)
               ar.add(a);
           else
           {
            
              throw(new OutDictionaryException());
           
           }
       }
        /** the size  of the dictionary
        */
        public int length()
        {
       
           return (short)ar.size();
        }

        public String toString()
        {
            Integer le=new Integer(length() );
       
            String str="size of the dictionary: "+le.toString ()+"\n";
            for(int i=0;i<length();i++)
              str+=new String(i+": "+(String)ar.get(i)+"\t");
           return str;
        }
        /** return the word by the index pointor
        */
        public String getString(short i)
        {
            return (String)ar.get(i);
        }
        /** only to test the dictionary
        */
        public static void main(String []args )
        {
            Dictionary a=new Dictionary();
        /* try{
           
            for(int i=128;i<6000;i++)
            {
                a.add(new String("i am a student") );
            }
         
          }
          catch(Exception e)
          { 
          
            System.err.println (e.toString());
           
            }*/
           System.out.println(a);
        }
    }

     

    展开全文
  • 压缩包中包含实验报告,运行视频,...其中功能包括输入字母及频率,然后生成相应哈夫曼编码,然后编码txt文件中的文本,输出,并且会把输出结果存入文件。重新打开控制台,可以通过读取文件重新建立哈夫曼树,就很强
  • 哈夫曼编码译码

    2020-11-24 11:10:47
    从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包 括标点符号空格)使用频率; 根据已统计字符使用频率构造哈夫曼编码树,并给出每个字符哈夫曼编 码(字符集哈夫曼编码表); 将文本...
    1. 从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包 括标点符号和空格)的使用频率;
    2. 根据已统计的字符使用频率构造哈夫曼编码树,并给出每个字符的哈夫曼编 码(字符集的哈夫曼编码表);
    3. 将文本文件利用哈夫曼树进行编码,存储成压缩文件(哈夫曼编码文件);
    4. 计算哈夫曼编码文件的压缩率;
    5. 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。
    6. 利用堆结构,优化的哈夫曼编码算法
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXLEAF 50
    #define MAXNODE 2*MAXLEAF-1
    #define MAXWEIGHT 10000
    #define MAXBIT 100
    typedef struct character
    {
        char ch;
        int count=0;
    }CHARACTER;             //记录原文本文件中出现的字符及相应出现次数的类型
    typedef struct hnodetype
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        char value;
        int i;
    }HNodeType;             //哈夫曼树的结点定义
    typedef struct huffcodetype
    {
        int bit[MAXBIT];
        int start;
    }HCodeType;             //记录每个字符哈夫曼编码
    typedef struct heap
    {
        HNodeType node[MAXNODE+1];
        int n;
    }HEAP;                  //最小堆的类型定义
    void Statistic(CHARACTER chars[],int &n);                       //统计原文本中出现的字符及其使用频率
    void Display(CHARACTER chars[],int n);                          //打印原文本中出现的字符及其使用频率
    void CreateHT(HNodeType huffnode[],int n,CHARACTER chars[]);    //构建哈夫曼树
    void Coding(HNodeType huffnode[],HCodeType huffcode[],int n);   //构建哈夫曼编码表
    void Calculate(CHARACTER chars[],int n,int chnum);              //计算压缩率
    void Display(HNodeType huffnode[],HCodeType huffcode[],int n);  //打印哈夫曼编码表
    void CodingFile(HNodeType huffnode[],HCodeType huffcode[],int n,int &chnum);    //将文本编码并存入文件
    void Decoding(HNodeType huffnode[],int n);                                      //将编码文件译码恢复
    
    void Insert(HEAP &heap,HNodeType item);     //向堆里插入元素
    HNodeType Delete(HEAP &heap);               //取堆顶元素并删除
    void CreateHT_heap(HNodeType huffnode[],CHARACTER chars[],int n,HEAP &heap);    //用最小堆优化构建哈夫曼树的过程
    int main()
    {
        CHARACTER chars[MAXLEAF];
        HNodeType huffnode[MAXNODE];
        HCodeType huffcode[MAXLEAF];
        HEAP heap;heap.n=0;
        int n=0,chnum=0;
        Statistic(chars,n);
        Display(chars,n);
        //CreateHT_heap(huffnode,chars,n,heap);
        CreateHT(huffnode,n,chars);
        Coding(huffnode,huffcode,n);
        Display(huffnode,huffcode,n);
        CodingFile(huffnode,huffcode,n,chnum);
        Calculate(chars,n,chnum);
        Decoding(huffnode,n);
    }
    void Statistic(CHARACTER chars[],int &n)    //统计原文本中出现的字符及其使用频率
    {
        FILE *f=NULL;
        if((f=fopen("original.txt","r"))==NULL)
        {
            printf("Fail to open original.txt!\n");
            exit(0);
        }
        char ch;
        int i=0,j=0,flag=0;;
        fscanf(f,"%c",&ch);
        chars[i].ch=ch;
        chars[i].count++;
        //printf("%c",chars[i].ch);
        i++;
        while(ch!='#')  //从文件读入文本,以#标记结束
        {
            fscanf(f,"%c",&ch);
            flag=0;
            if(ch!='#')
            {
                for(j=0;j<i;j++)
                {
                    if(ch==chars[j].ch)  //如果读入的字符已被记录,则将出现次数+1
                    {
                        chars[j].count++;
                        flag=1;
                        //printf("%c",chars[j].ch);
                        break;
                    }
                }
                if(flag==0)
                {
                    chars[i].ch=ch;
                    chars[i].count++;
                    //printf("%c",chars[i].ch);
                    i++;
                }
            }
        }
        n=i;
        fclose(f);
    }
    void CreateHT(HNodeType huffnode[],int n,CHARACTER chars[])     //构建哈夫曼树
    {
        int i,j,w1,w2,x1,x2;
        for(i=0;i<2*n-1;i++)        //初始化
        {
            huffnode[i].weight=chars[i].count;
            huffnode[i].parent=-1;
            huffnode[i].lchild=-1;
            huffnode[i].rchild=-1;
            huffnode[i].value=chars[i].ch;
        }
        for(i=0;i<n-1;i++)
        {
            w1=w2=MAXWEIGHT;
            x1=x2=0;
            for(j=0;j<n+i;j++)      //寻找权值最小的两个结点
            {
                if(huffnode[j].parent==-1&&huffnode[j].weight<w1)
                {
                    w2=w1;
                    x2=x1;
                    w1=huffnode[j].weight;
                    x1=j;
                }
                else if(huffnode[j].parent==-1&&huffnode[j].weight<w2)
                {
                    w2=huffnode[j].weight;
                    x2=j;
                }
            }
            huffnode[x1].parent=n+i;
            huffnode[x2].parent=n+i;
            huffnode[n+i].lchild=x1;
            huffnode[n+i].rchild=x2;
            huffnode[n+i].weight=w1+w2;
        }
    }
    void CreateHT_heap(HNodeType huffnode[],CHARACTER chars[],int n,HEAP &heap)  //利用堆优化哈夫曼树的构建
    {
        int i;
        HNodeType node1,node2;
        for(i=0;i<2*n-1;i++)
        {
            huffnode[i].weight=chars[i].count;
            huffnode[i].parent=-1;
            huffnode[i].lchild=-1;
            huffnode[i].rchild=-1;
            huffnode[i].value=chars[i].ch;
            huffnode[i].i=i;
            if(i<n)
                Insert(heap,huffnode[i]);
        }
        for(i=0;i<n-1;i++)
        {
            node1=Delete(heap);
            node2=Delete(heap);
            huffnode[node1.i].parent=n+i;
            huffnode[node2.i].parent=n+i;
            huffnode[n+i].lchild=node1.i;
            huffnode[n+i].rchild=node2.i;
            huffnode[n+i].weight=node1.weight+node2.weight;
            huffnode[n+i].i=n+i;
            Insert(heap,huffnode[n+i]);
        }
    }
    void Coding(HNodeType huffnode[],HCodeType huffcode[],int n)        //构建字符的哈夫曼编码表
    {
        HCodeType temp;
        int p,c;
        for(int i=0;i<n;i++)
        {
            huffcode[i].start=MAXBIT-1;
            c=i,p=huffnode[i].parent;
            while(p!=-1)
            {
                if(c==huffnode[p].lchild)
                    huffcode[i].bit[huffcode[i].start]=0;
                else
                    huffcode[i].bit[huffcode[i].start]=1;
                c=p;
                p=huffnode[p].parent;
                huffcode[i].start--;
            }
            huffcode[i].start++;
        }
    }
    void Display(HNodeType huffnode[],HCodeType huffcode[],int n) //打印哈夫曼编码表
    {
        for(int i=0;i<n;i++)
        {
            printf("%c: ",huffnode[i].value);
            for(int j=huffcode[i].start;j<MAXBIT;j++)
            {
                printf("%d",huffcode[i].bit[j]);
            }
            printf("\n");
        }
    }
    void CodingFile(HNodeType huffnode[],HCodeType huffcode[],int n,int &chnum)     //对原文本编码并将编码写入文件
    {
        FILE *fo=NULL;
        FILE *fc=NULL;
        if((fo=fopen("original.txt","r"))==NULL)
        {
            printf("Fail to open original.txt!\n");
            exit(0);
        }
        if((fc=fopen("compressed.txt","w"))==NULL)
        {
            printf("Fail to open compressed.txt!\n");
            exit(0);
        }
        char ch;
        do
        {
            fscanf(fo,"%c",&ch);
            if(ch!='#')
            {
                for(int i=0;i<n;i++)
                {
                    if(huffnode[i].value==ch)
                    {
                        for(int j=huffcode[i].start;j<MAXBIT;j++)
                        {
                            fprintf(fc,"%d",huffcode[i].bit[j]);
                            chnum++;
                        }
                    }
                }
            }
        } while (ch!='#');
        fclose(fo);
        fclose(fc);
    }
    void Decoding(HNodeType huffnode[],int n)   //译码
    {
        FILE *fc=NULL,*fd=NULL;
        if((fc=fopen("compressed.txt","r"))==NULL)
        {
            printf("Fail to open compressed.txt!\n");
            exit(0);
        }
        if((fd=fopen("decoding.txt","w"))==NULL)
        {
            printf("Fail to open decoding.txt!\n");
            exit(0);
        }
        char code[100000];
        fscanf(fc,"%s",code);
        int i=0,j=0,temp;
        for(i=0;code[i]!='\0';i++);
        while(j<i)
        {
            temp=2*n-2;
            while(huffnode[temp].lchild!=-1&&huffnode[temp].rchild!=-1)
            {
                if(code[j]=='0')
                    temp=huffnode[temp].lchild;
                else
                    temp=huffnode[temp].rchild;
                j++;
            }
            fprintf(fd,"%c",huffnode[temp].value);
        }
        fclose(fc);
        fclose(fd);
    }
    void Display(CHARACTER chars[],int n)   
    {
        int total=0;
        double f=0;
        for(int i=0;i<n;i++)
        {
            total=total+chars[i].count;
        }
        for(int i=0;i<n;i++)
        {
            printf("frequency of %c is %f\n",chars[i].ch,chars[i].count*1.0/total);
        }
    }
    void Calculate(CHARACTER chars[],int n,int chnum)   //计算压缩率
    {
        int total=0;
        for(int i=0;i<n;i++)
        {
            total+=chars[i].count;
        }
        printf("Compression rate is %f%%",chnum*1.0/8/total*100);
    }
    void Insert(HEAP &heap,HNodeType item)
    {
        int i;
        if(heap.n<MAXNODE-1)
        {
            i=heap.n+1;
            while(i!=1&&item.weight<heap.node[i/2].weight)
            {
                heap.node[i]=heap.node[i/2];
                i/=2;
            }
            heap.node[i]=item;
            heap.n++;
        }
    }
    HNodeType Delete(HEAP &heap)
    {
        int parent=1,child=2;
        HNodeType item,temp;
        if(heap.n>0)
        {
            item=heap.node[1];
            temp=heap.node[heap.n--];
            while(child<=heap.n)
            {
                if(child<heap.n&&heap.node[child].weight>heap.node[child+1].weight)
                    child++;
                if(temp.weight<=heap.node[child].weight) break;
                heap.node[parent]=heap.node[child];
                parent=child;
                child*=2;
            }
            heap.node[parent]=temp;
            return item;
        }
    }
    

    测试数据与运行结果:
    输入格式:输入一篇英文文本,以#结尾
    输入:
    在这里插入图片描述

    各字符出现的频率:
    在这里插入图片描述

    在这里插入图片描述

    字符集的哈夫曼编码表:

    在这里插入图片描述
    在这里插入图片描述

    哈夫曼编码文件:

    在这里插入图片描述

    哈夫曼编码文件的压缩率:
    在这里插入图片描述

    译码结果:

    在这里插入图片描述

    展开全文
  • 哈夫曼编码c语言实现,代码中有注释。有编码和译码功能,能输出每个字符Huffman码。可以输入一段Huffman码反应成文本,也可以输入一段文本翻译成Huffman码。计算了信源熵,编码效率,和平均编码长度。
  • 哈夫曼编码/译码

    2021-02-16 17:47:35
    (1)读取一个待压缩的文本文件SourceTextFile.txt,统计文本文件中各字符个数作为权值,生成哈夫曼树,并将对应哈夫曼编码存入文件HFMCodeFile.txt打印到屏幕上; (2)编码(Encoding)。利用所得哈夫曼编码...

    问题描述

    利用哈夫曼进行通信可以在对信息加密的同时,大大提高信道利用率,缩短信息传输时间,降低传输成本。设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件;反过来,可将一个压缩(编码)文件译码还原为原来的文本文件。

    基本要求

    (1)读取一个待压缩的文本文件SourceTextFile.txt,统计文本文件中各字符的个数作为权值,生成哈夫曼树,并将对应的哈夫曼编码存入文件HFMCodeFile.txt和打印到屏幕上;
    (2)编码(Encoding)。利用所得哈夫曼编码对文本文件SourceTextFile.txt进行编码,然后将结果存储到压缩文件EncodedFile.txt中,同时打印到屏幕上;
    (3)译码(Decoding)。利用所得哈夫曼编码对(2)中的压缩文件进行译码,结果存入新的文本文件DecodedFile.txt中,同时打印到屏幕上。

    详细设计

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define  N 256
    typedef struct 
    {
    	int weight;
    	int parent, lchild, rchild;  //儿子节点的parent存放父节点的下标  父节点的lchild和rchild存放儿子节点的下标
    }HTNode, * HuffmanTree;  //动态分配数组,存储赫夫曼树
    
    typedef char** HuffmanCode;//动态分配数组存储赫夫曼编码表
    
    //一、读取文件,统计字符个数,返回值为字符个数n
    char fileDQ(char(&t)[N],char (&s)[N],int (&v)[N],int &i)
    {
    	int k = 0, j = 0,n=0;
    	FILE* fp;
    	char ch;
    	//1、打开文件
    	if ((fp = fopen("\SourceTexFile.txt", "r")) == NULL)
    	{
    		printf("无法打开文件");
    		exit(0);
    	}
    	//2、读取文件.保存到指针数组c中
    	t[i] = fgetc(fp);
    	printf("            (1):读取文件内容:");
    	while (t[i] !=EOF)
    	{
    		printf("%c", t[i]);
    		i++;
    		t[i] = fgetc(fp);
    		
    	}
    	printf("                   读入%d个字符\n\n", i-1);
    	fclose(fp);
    	//3、将数组c[N]的各元素保存到s[N]中  每个字符不重复
    	while (k < i-1)
    	{
    		for (j = 0; j < n &&  s[j]!= t[k]; j++,s+1);//从0开始循环比较,每次c[k]与v[j]比较,j<k
    		if (j == n)
    		{
    			s[j] = t[k];
    			n++;	
    		}
    		k++;
    	}
    	//4、用数组v来计数s[N]对应元素的个数
    	for (j = 0; j < n; j++) {
    		int	cnt = 0;//每一轮计算的一个字符初始个数0 
    		for (k = 0; k <= i-1; k++)
    		{
    			if (s[j] == t[k])
    				cnt++;
    		}
    		v[j] = cnt;
    	}
    	printf("            (2):不同字符和对应的个数\n");
    	//5、打印不同字符和对应的个数
    	for (j = 0; j < n; j++)
    	{
    		printf("                   %c--%d\n", s[j], v[j]);
    	}
    	return n;
    }
    
    
    //从树种选择两个比较小的树
    void select(HuffmanTree Ht, int n, int& s1, int& s2)
    {
    	int i, min;
    	for (i = 1; i <= n; i++)
    	{
    		if (Ht[i].parent == 0)
    		{
    			min = i;
    			break;
    		}
    	}
    	for (i = 1; i <= n; i++)
    	{
    		if (Ht[i].parent == 0)
    		{
    			if (Ht[i].weight < Ht[min].weight)
    				min = i;
    		}
    	}
    	s1 = min;
    
    	for (i = 1; i <= n; i++)
    	{
    		if (Ht[i].parent == 0 && i != s1)
    		{
    			min = i;
    			break;
    		}
    	}
    	for (i = 1; i <= n; i++)
    	{
    		if (Ht[i].parent == 0 && i != s1)
    		{
    			if (Ht[i].weight < Ht[min].weight)
    				min = i;
    		}
    	}
    	s2 = min;
    }
    
    //二、 w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
    void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)
    {
    	int i, m, s1, s2, start;
    	char* cd;
    	int c, f;
    	if (n <= 1) return;
    	m = 2 * n - 1;  //共需要m个节点
    	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));  // 0号单元未用
    	for (i = 1; i <= n; i++) { //初始化前n个节点
    		HT[i].weight = w[i - 1];
    		HT[i].parent = 0;
    		HT[i].lchild = 0;
    		HT[i].rchild = 0;
    	}
    	for (i = n + 1; i <= m; i++) { //初始化n+1到m个节点
    		HT[i].weight = 0;
    		HT[i].parent = 0;
    		HT[i].lchild = 0;
    		HT[i].rchild = 0;
    	}
    
    	for (i = n + 1; i <= m; i++) {  // 建哈夫曼树
    	  // 在HT[1..i-1]中选择parent为0且weight最小的两个结点,
    	  // 其序号分别为s1和s2。
    		select(HT, i - 1, s1, s2);
    		HT[s1].parent = i;  HT[s2].parent = i;  //改变s1 和s2的节点的父节点的值
    		HT[i].lchild = s1;  HT[i].rchild = s2;
    		HT[i].weight = HT[s1].weight + HT[s2].weight;
    	}
    
    	//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
    	HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));  //分配n个编码的头指针
    	cd = (char*)malloc(n * sizeof(char));    // 分配求当前编码的工作空间
    	cd[n - 1] = '\0';                         // 编码结束符。
    	for (i = 1; i <= n; ++i) 
    	{                  // 逐个字符求哈夫曼编码
    		start = n - 1;                          // 编码结束符位置
    		for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)  //获得parent中值并判断值是否为零 依次后移
    		  // 从叶子到根逆向求编码
    			if (HT[f].lchild == c) cd[--start] = '0';
    			else cd[--start] = '1';
    		HC[i] = (char*)malloc((n - start) * sizeof(char)); //为第i个编码分配空间
    			 // 为第i个字符编码分配空间
    		strcpy(HC[i], &cd[start]);    // 从cd复制编码(串)到HC
    	}
    	free(cd);   // 释放工作空间
    }
    //三、输出哈夫曼编码及文件存储
    void putout(HuffmanCode HC, char c[], int n) 
    {
    	FILE* fp;
    	int i; 
    	printf("\n             (3):字符对应的哈夫曼编码为\n");
    	for (i = 1; i <=n; ++i) 
    	{
    		printf("                   %c:%s", c[i-1],HC[i]);
    	}
    	//1、打开文件
    	if ((fp = fopen("\HFMCodeFile.txt", "w")) == NULL)
    	{
    		printf("无法打开文件");
    		exit(0);
    	}
    	for (i = 0; i < n; i++) 
    	{
    		fprintf(fp,"%c ", c[i]);
    		fputs(HC[i + 1],fp);
    		fputc('\n', fp);
    	}
    	fclose(fp);
    }
    //四、编码
    //、利用所得哈夫曼编码对文本文件SourceTextFile.txt进行编码
    void Encoding(HuffmanCode HC, char T[], char c[], int& i, int &n)
    {
    	FILE* fp;
    	int j,k=1,s=0;
    	if ((fp = fopen("\EncodedFile.txt", "w")) == NULL)
    	{
    		printf("无法打开文件");
    		exit(0);
    	}
        printf("             (1):文本文件SourceTextFile.txt的内容:");
    	for (j = 0; j < i; j++)
    	{
    		printf("%c", T[j]);
    	}
    	printf("\n             (2):对文本文件SourceTextFile.txt的内容进行编码:\n                   ");
    	while( k <= n)
    	{
    		for(j=0;j < i;j++ )
    		{
    
    			if (T[j] == c[k - 1])
    			{
    				printf("%s", HC[k]);
    				fputs(HC[k], fp);
    			}
    			else
    				continue;
    		}
    		k++;
    	}		
    	fclose(fp);
    }
    //五、译码
    //利用所得哈夫曼编码对EncodedFile.txt进行译码,结果存入新的文本文件DecodedFile.txt中,同时打印到屏幕上。
    void Decoding(HuffmanTree HT,char *r, char *c, int& n)
    {
    	FILE* fp,*fp1;
    	int p = 2*n-1;//HT的最后一个节点是根节点,前n个节点是叶子节点
    	int i = 0,j = 0,v,len=0;//指示测试串中的第i个字符,指示结果串中的第j个字符 
    	char k[N];
    	if ((fp = fopen("\EncodedFile.txt", "r")) == NULL)
    	{
    		printf("无法打开文件");
    		exit(0);
    	}
    	printf("\n             (1):读取EncodedFile.txt文件内容:");
    	k[len]=fgetc(fp);
    	while (k[len]!=EOF) 
    	{
    		printf("%c",k[len]);
    		len++;
    		k[len] = fgetc(fp);
    	}
    	printf("\n");
    	fclose(fp);
    	while (i<=len) 
    	{
    		if (k[i] == '0')
    		{
    			p = HT[p].lchild;
    		}
    		if (k[i] == '1')
    		{
    			p = HT[p].rchild;
    		}
    		if (p <= n) 
    		{//p<=n则表明p为叶子节点,因为在构造哈夫曼树HT时,HT的m个节点中前n个节点为叶子节点
    			r[j] = c[p-1];
    			j++;
    			p = 2*n-1;//p重新指向根节点
    		}
    		i++;
    	}
    	r[j] = '\0';//结果串的结束符
    	if ((fp1 = fopen("\DecodedFile.txt", "w")) == NULL)
    	{
    		printf("无法打开文件");
    		exit(0);
    	}	
    	printf("\n             (2):译码文件内容:");
    	for (i = 0; i <=j; i++)
    	{
    		printf("%c", r[i]);
    		fputc(r[i], fp);
    	}
    	fclose(fp1);
    }
    int main()
    {
    	int n = 0,j=0,v[N],i=0,m=0;
    	char S[N],t[N];
    	char r[N];
    	char* c ,*T;
    	int* w ;
    	c = S;
    	w = v;
    	T = t; 
    	HuffmanTree HT;
    	HuffmanCode HC;
    	printf("——————————————————————哈夫曼编码/译码器————————————————————————————\n");
    	printf("                                                                                                                   \n");
    	printf("       1:读取文件SourceTextFile.txt,打印文件内容,统计文本文件中各字符的个数作权值,生成哈夫曼树和哈夫曼编码。       \n\n");
    	n = fileDQ(t, S, v, i);
    	HuffmanCoding(HT, HC, w, n);
    	putout(HC, c, n);
    	printf("                                                                                                                   \n\n");
    	printf("       2:编码 对文本文件SourceTextFile.txt进行编码,将结果存储到压缩文件EncodedFile.txt,并打印到屏幕上。            \n\n");
    	Encoding(HC, T, c, i, n);
    	printf("                                                                                                                   \n\n");
    	printf("       3:译码 利用所得哈夫曼编码对2-2中的压缩文件进行译码,结果存入文本文件DecodedFile.txt中并打印到屏幕上。     \n");
    	Decoding(HT, r, c, n);
    	printf("                                                                                                                   \n");
    	printf("\--------------------------------------------------------------------------------———————————————————\n");
    	return 0;
    }
    
    

    测试与结果

    (1)SourceTextFile
    在这里插入图片描述
    (2)HFMCodeFile
    在这里插入图片描述
    (3)EncodedFile
    在这里插入图片描述
    (4)DecodedFile
    在这里插入图片描述
    (5)控制台输出
    在这里插入图片描述

    展开全文
  • 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼...(4)显示指定的编码文件和文本文件; (5)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。(此选项选作)
  • 设计一个哈夫曼编码/译码系统,对一个文本文件中字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。 【基本要求】 (1) 输入一个待压缩的文本...
  • 数据结构——Huffman编码译码

    千次阅读 2018-10-23 16:33:21
    Huffman编码及译码 1.掌握二叉树的二叉链表存贮结构。 2.掌握Huffman算法。   ...使用文件保存初始的文本数据及最终的... 文件名为outputfile1.txt的文件保存各字符的出现次数对应的编码; 文件名为outputfi...
  • 哈夫曼树、哈夫曼编码译码实现(c语言)

    千次阅读 多人点赞 2019-12-27 17:18:26
    注:因为当时时间有限,故其实该代码还有优化空间,且输出文件是0/1字符串文本(UTF-8)并不是ASCII码编码文件,计算压缩率除以8即可。 实验项目:哈夫曼编码译码方法 哈夫曼编码是一种以哈夫曼树(最优二叉树,...
  • 当然,还有编码和译码部分。本系统前端开发工具是Visual C++6.0。具有输入字符集大小及权值大小,构造哈夫曼树,并对用户输入字符串进行编码以及译码还有退出四种功能。本程序经过测试后,功能均能实现,运行...
  • 1)从键盘上输入要进行哈夫曼编码的字符集对应权值。 2)构造哈夫曼树算法 3)完成哈夫曼编码的算法 4)完成哈夫曼译码算法。 5)利用编译码算法,对给定的文本文件t1.txt英语内容进行编码,保存到指定...
  • 数据结构与算法/哈夫曼编码译码

    千次阅读 2018-01-18 20:53:20
    (1)输入一个需要压缩的文本文件名,统计该文件中各字符的个数作为...(4)显示指定的编码文件和文本文件。(5)把赫夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。#include#inclu
  • 关于哈弗曼树的编码和译码器的详细描述,可以用英文文本的内容进行测试
  • 编码过程中的状态转移网格图表示如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必...
  • 定义广义的二进制文件...文本文件的编码基于字符定长,译码相对要容易一些;二进制文件编码是变长的,灵活利用率要高,而译码要难一些,不同的二进制文件译码方式是不同的。从本质上来说他们之间没有什么区别,因为...
  • 广义的二进制文件即指文件...文本文件的编码基于字符定长,译码相对要容易一些;二进制文件编码是变长的,灵活利用率要高,而译码要难一些,不同的二进制文件译码方式是不同的。 从本质上来说他们之间没有什么区别,
  • 我通过编码,对一个含有一大段字符串的文本得到了一个dict一段编码完成01字符串,dict中Keys为字符,value为权,不用树,怎么直接根据dict01字符串译码回去? 比如 ...
  • 其中编码要求正向与逆向两种方式? 要求实现两个方案:从键盘输入进行解码译码和对已有文件中一串英文进行编译码
  • 信息论实验要求: 我用cpp和java都写了一份程序,java是带有有图形化界面。cpp程序是要在当前目录下创建words.txt,java是直接图形化界面输入,加入了其他一些功能更加...(二)信道编码和译码 1)哈夫曼编
  • 广义上二进制文件包括文本文件,这里讨论是狭义上二进制文件与文本文件比较: ...以ASCII为例,每条数据(每个字符)都是1个字节,而文本文件编码基于字符定长,因此译码容易。 二进制文件每条数据不固定。如s
  •   掌握Huffman树建立以及Huffman编码和解码 任务   应用Huffman编码实现简单文本文件压缩和解压缩 要求   利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。综合设计...
  • 哈夫曼编码

    千次阅读 多人点赞 2019-01-10 13:12:38
    1. 问题描述 假设某文本文档只包含26个英文字母,应用哈夫曼算法对该文档进行压缩和解压缩操作,使得该文档占用较少...根据上述问题描述,可以看出编写程序是通过利用二叉树结构实现哈夫曼编码和译码,并且程序...
  • 用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。 字符 A B C D E F G H I J K L M N O P Q 频度:186 64 13 22 32 103 21 15 47 57 1 5 32 20...
  • Huffman编码

    2012-05-18 20:38:49
    (1)统计(Statistics):统计输入的文本的单词/Unicode字符频率。 (2) 初始化(Initialization):从终端读入字符集大小n,以及n个单词n个权值,建立哈夫曼树. (3) 编码(Encoding):利用已建立好的哈夫曼树,对输入...
  • 这将保留所有格式,包括段落分隔符,文本样式链接。 或者在发布之前使用它来加密文本。 在任何输入字段中键入您文本,将其选中,然后从右键单击菜单中选择Rot13。 文本将被编码并准备提交。 支持语言:English
  • 1 需求分析 1.1 程序功能需求 ...对于给定的文章选段,可以统计出字符分布和出现数量,并且利用哈夫曼树算法进行相应的编码和译码工作;根据文本中的词频统计结果显示排序结构和相关信息。 将所有的文本文...

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

文本的编码和译码