精华内容
下载资源
问答
  • 哈夫曼编码

    2018-06-07 20:00:47
    2. 哈夫曼算法的应用 (1) 假设文档内容从文件读取; (2) 设计哈夫曼算法的存储结构; (3) 设计哈夫曼编码和解码算法; (4) 分析算法的时间复杂度
  • 5.哈夫曼编码

    千次阅读 2020-04-07 21:49:33
    哈夫曼编码1.哈夫曼编码的原理2....在算法导论中,哈夫曼编码使用优先队列管理结点序列,如果优先队列使用最小堆来维护,这样哈夫曼编码算法时间复杂度为O(n*lgn); 哈夫曼编码主要用于数据压缩,...

    1.哈夫曼编码的原理

    • 构建哈夫曼树的步骤:
      1.对于给定个m个权值,从中选出权值最小和次小的两个树,将其作为左右子树,其根节点的值为子树节点的值的和; 重复上面操作直到所有节点都并入树中;
      在这里插入图片描述
    • 在算法导论中,哈夫曼编码使用优先队列管理结点序列,如果优先队列使用最小堆来维护,这样哈夫曼编码算法时间复杂度为O(n*lgn);

    哈夫曼编码主要用于数据压缩,通常可以节省20%~90%的空间,具体的压缩依赖与数据的特性;

    参考

    注意:哈夫曼树的形态不是唯一的,但是它的带权路径长度WPL是唯一的;
    最佳二叉树指的是哈夫曼树,但是哈夫曼树不一定就是平衡二叉树;

    2.代码实现

    /***************************************
    目的:1.根据输入的字符代码集及其权值集,
    构造赫夫曼树,输出各字符的赫夫曼编码
    2.输入赫夫曼码序列,输出原始字符代码
    作者:Dmego       时间:2016-11-11
    ****************************************/
    #include<iostream>
    #include<cstring>
    #define MAX_MA 1000
    #define MAX_ZF 100
    using namespace std;
    
    //哈夫曼树的储存表示
    typedef struct
    {
        int weight;  //结点的权值
        int parent, lchild, rchild;//双亲,左孩子,右孩子的下标
    }HTNode,*HuffmanTree;  //动态分配数组来储存哈夫曼树的结点
      
    //哈夫曼编码表的储存表示
    typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码
    
    //返回两个双亲域为0且权值最小的点的下标
    void Select(HuffmanTree HT, int n, int &s1, int &s2)
    {
        /*n代表HT数组的长度
        */
    
       //前两个for循环找所有结点中权值最小的点(字符)
        for (int i = 1; i <= n; i++)
        {//利用for循环找出一个双亲为0的结点
            if (HT[i].parent == 0)
            {
                s1 = i;//s1初始化为i
                break;//找到一个后立即退出循环
            }
        }
        for (int i = 1; i <= n; i++)
        {/*利用for循环找到所有结点(字符)权值最小的一个
         并且保证该结点的双亲为0*/
            if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
                s1 = i;
        }
        //后两个for循环所有结点中权值第二小的点(字符)
        for (int i = 1; i <= n; i++)
        {//利用for循环找出一个双亲为0的结点,并且不能是s1
            if (HT[i].parent == 0 && i != s1)
            {
                s2 = i;//s2初始化为i
                break;//找到一个后立即退出循环
            }    
        }
    
        for (int i = 1; i <= n; i++)
        {/*利用for循环找到所有结点(字符)权值第二小的一个,
         该结点满足不能是s1且双亲是0*/
            if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
                s2 = i;
        }
    
    }
    
    //构造哈夫曼树
    void CreateHuffmanTree(HuffmanTree &HT, int n)
    {
    /*-----------初始化工作-------------------------*/
        if (n <= 1)
            return;
        int m = 2 * n - 1;
        HT = new HTNode[m + 1];
        for (int i = 1; i <= m; ++i)
        {//将1~m号单元中的双亲,左孩子,右孩子的下标都初始化为0
            HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
        }
        for (int i = 1; i <= n; ++i)
        {
            cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
        }
    /*-----------创建工作---------------------------*/
        int s1,s2;
        for (int i = n + 1; i <= m; ++i)
        {//通过n-1次的选择,删除,合并来构造哈夫曼树
            Select(HT, i - 1, s1, s2);
            /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
            /*将s1,s2的双亲域由0改为i
            (相当于把这两个结点删除了,这两个结点不再参与Select()函数)*/
            HT[s1].parent = i;
            HT[s2].parent = i;
            //s1,与s2分别作为i的左右孩子
            HT[i].lchild = s1;
            HT[i].rchild = s2;
            //结点i的权值为s1,s2权值之和
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    //从叶子到根逆向求每个字符的哈夫曼编码,储存在编码表HC中
    void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
    {
        HC = new char*[n + 1];//分配储存n个字符编码的编码表空间
        char *cd = new char[n];//分配临时存储字符编码的动态空间
        cd[n - 1] = '\0';//编码结束符
        for (int i = 1; i <= n; i++)//逐个求字符编码
        {
            int start = n - 1;//start 开始指向最后,即编码结束符位置
            int c = i;
            int f = HT[c].parent;//f指向结点c的双亲
            while (f != 0)//从叶子结点开始回溯,直到根结点
            {
                --start;//回溯一次,start向前指向一个位置
                if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子,则cd[start] = 0;
                else cd[start] = '1';//否则c是f的右孩子,cd[start] = 1
                c = f;
                f = HT[f].parent;//继续向上回溯
            }
            HC[i] = new char[n - start];//为第i个字符编码分配空间
            strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
        }
        delete cd;
    }
    
    //哈夫曼译码
    void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
    {
        /*
        HT是已经创建好的哈夫曼树
        a[]用来传入二进制编码
        b[]用来记录译出的字符
        zf[]是与哈夫曼树的叶子对应的字符(叶子下标与字符下标对应)
        n是字符个数,相当于zf[]数组得长度
        */
    
        int q = 2*n-1;//q初始化为根结点的下标
        int k = 0;//记录存储译出字符数组的下标
        int i = 0;
        for (i = 0; a[i] != '\0';i++)
        {//for循环结束条件是读入的字符是结束符(二进制编码)
            //此代码块用来判断读入的二进制字符是0还是1
            if (a[i] == '0')
            {/*读入0,把根结点(HT[q])的左孩子的下标值赋给q
             下次循环的时候把HT[q]的左孩子作为新的根结点*/
                q = HT[q].lchild;
            }
            else if (a[i] == '1')
            {
                q = HT[q].rchild;
            }
            //此代码块用来判断HT[q]是否为叶子结点
            if (HT[q].lchild == 0 && HT[q].rchild == 0)
            {/*是叶子结点,说明已经译出一个字符
            该字符的下标就是找到的叶子结点的下标*/
                b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]
                q = 2 * n - 1;//初始化q为根结点的下标
                //继续译下一个字符的时候从哈夫曼树的根结点开始
            }
        }
        /*译码完成之后,用来记录译出字符的数组由于没有结束符输出的
        时候回报错,故紧接着把一个结束符加到数组最后*/
        b[k] = '\0';
    }
    //菜单函数
    void menu()
    {
        cout << endl;
        cout << "       ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
        cout << "       ┃      ★★★★★★★哈夫曼编码与译码★★★★★★★        ┃" << endl;
        cout << "       ┃                   1.  创建哈夫曼树                       ┃" << endl;
        cout << "       ┃                   2.  进行哈夫曼编码                     ┃" << endl;
        cout << "       ┃                   3.  进行哈夫曼译码                     ┃" << endl;
        cout << "       ┃                   4.  退出程序                           ┃" << endl;
        cout << "       ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
        cout << "                       <><注意:空格字符用'- '代替><>" << endl;
        cout << endl;
    }
    int main()
    {
        int falg;//记录要编码的字符个数
        char a[MAX_MA];//储存输入的二进制字符
        char b[MAX_ZF];//存储译出的字符
        char zf[MAX_ZF];//储存要编码的字符
        HuffmanTree HT = NULL;//初始化树为空数
        HuffmanCode HC = NULL;//初始化编码表为空表
        menu();
        while (true)
        {
            int num;
            cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";
                cin >> num;
                switch (num)
                {
                case 1 :
                    cout << "<><请输入字符个数><>:";
                    cin >> falg;
                    //动态申请falg个长度的字符数组,用来存储要编码的字符
                    /*char *zf = new char[falg];*/
                    cout << "<><请依次输入" << falg << "个字符:><>: ";
                    for (int i = 1; i <= falg; i++)
                        cin >> zf[i];
                    cout << "<><请依次输入" << falg << "个字符的权值><>: ";
                    CreateHuffmanTree(HT, falg);//调用创建哈夫曼树的函数
                    cout << endl;
                    cout << "<><创建哈夫曼成功!,下面是该哈夫曼树的参数输出><>:" << endl;
                    cout << endl;
                    cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩子" << "\t" << "右孩子" << endl;
                    for (int i = 1; i <= falg * 2 - 1; i++)
                    {
                        cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl;
                    }
                    cout << endl;
                    break;
                case 2:
                    CreatHuffmanCode(HT, HC, falg);//调用创建哈夫曼编码表的函数
                    cout << endl;
                    cout << "<><生成哈夫曼编码表成功!,下面是该编码表的输出><>:" << endl;
                    cout << endl;
                    cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl;
                    for (int i = 1; i <= falg; i++)
                    {
                        cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HC[i] << endl;
                    }
                    cout << endl;
                    break;
                case 3:
                    cout << "<><请输入想要翻译的一串二进制编码><>:";
                    /*这样可以动态的直接输入一串二进制编码,
                    因为这样输入时最后系统会自动加一个结束符*/
                    cin >> a;
                    TranCode(HT, a, zf, b, falg);//调用译码的函数,
                     /*这样可以直接把数组b输出,因为最后有
                     在数组b添加输出时遇到结束符会结束输出*/
                    cout << endl;
                    cout << "<><译码成功!翻译结果为><>:" << b << endl;
                    cout << endl;
                    break;
                case 4:
                    cout << endl;
                    cout << "<><退出成功!><>" << endl;
                    exit(0);
                default:
                    break;
                }
        }
        
        //-abcdefghijklmnopqrstuvwxyz
        //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
        //000101010111101111001111110001100100101011110110
        return 0;
    }
    
    

    代码链接

    展开全文
  • 努力把它的时间复杂度变成了线性。 首先怎么生成一棵哈夫曼树(人工运算)我们是知道的吧。 计算机上。 我的做法分成了3步,准确说是4步。去生成一棵哈夫曼树,其复杂度控制在O(n) 然后我用哈夫曼树去进行编码其...

    最近多媒体布置了一个哈夫曼树的压缩算反的题目。然后我觉得我里面用了不少算法。努力把它的时间复杂度变成了线性。
    首先怎么生成一棵哈夫曼树(人工运算)我们是知道的吧。
    计算机上。
    我的做法分成了3步,准确说是4步。去生成一棵哈夫曼树,其复杂度控制在O(n)
    然后我用哈夫曼树去进行编码其复杂度我也把它降成了O(n)这两部都是线性就能解决问题。
    最后一个解码。没办法只能变成O(KN),K是哈夫曼编码时的字典大小。字典是变得。我没办法降低算法复杂度了。

    给一个String串。我们第一步肯定是吧字符数量从小到大排序。为了求出存在的比例嘛~

    先介绍下节点

    class Node
    {
        int number;//存放多少个数。就是指里面value有多少次出现在string里
        char value;//存放string里每个出现的char。唯一的
        Node(){}
        Node(char temp,int number)
        {
            value=temp;
            this.number=number;
        }
        //这里是后面用于生产树时在用的。
        String code="";//存放哈西曼编码
        Node left=null;
        Node right=null;
        Node(Node a,Node b)//吧两个出现频率小的节点结合。
        {
            number=a.number+b.number;
            left=a;
            right=b;
            value='#';//中间节点
        }
    }

    此处我用map去数数。是为了降低时间复杂度。
    如果直接开一个结点然后把结点放到列表里去,下次查找时就得从列队的第一个结点查到最后一个。
    这样时间复杂度就是n^2了,而用map可以减低时间复杂度。因为它是HashMap时间复杂度是1。总复杂度就变成了n
    这一步时间复杂度是O(N)

    private static List<Node> count(String src)
        {
            /*
             *此处我用map去数数。是为了降低时间复杂度。
             *如果直接开一个结点然后把结点放到列表里去,下次查找时就得从列队的第一个结点查到最后一个。
             *这样时间复杂度就是n^2了,而用map可以减低时间复杂度。因为它是HashMap时间复杂度是1
             */
            Map<Character,Integer> map=new HashMap<Character,Integer>();
            char[] charArray=src.toCharArray();
            for(Character c:charArray)
            {
                if(!map.containsKey(c))
                {
                    map.put(c,0);
                }
                map.put(c, map.get(c)+1);
            }
    
            //这是我们再把map里的字符和数量导入到结点里存储。这样就可以把这个函数的算法复杂度降低了
            List<Node> list=new ArrayList<Node>();
            for(Map.Entry<Character, Integer> entry:map.entrySet())
            {
                Node temp=new Node(entry.getKey(),entry.getValue());
                list.add(temp);
            }
            Collections.sort(list,(Node a,Node b)->(a.number<b.number?b.number:a.number));
            Collections.reverse(list);
            return list;
        }
    
    

    然后是生成一棵哈夫曼树(并编码。这里其实可以生成两步的,我合并了下)
    规则就是我们熟知的。左边填1,右边填0
    先选出数量少的去生成一棵树,然后最后把多的给嫁接上
    这一步时间复杂度是O(N)

    private static Node buildTree(List<Node> list)
        {
            while(!(list.size()==1))
            {
                Node left=list.get(0);//先选出里面数量最少的当作左边节点
                left.code=left.code+"1";
                list.remove(0);//拿出来后记得删除它。便于下次再拿出一个头
    
                Node right=list.get(0);//由于前面的第一少的已经拿掉了。那么这个就变成第一少的了
                right.code=right.code+"0";
                list.remove(0);
    
                Node root=new Node(left,right);//然后生成一个新节点。把它放入数组中
    
                int index=0;//把索引定位。找到它在第几个数前面,为了插入回原来的列表。使这个列表的顺序还是有序的。这里其实是一遍插入排序
                while(list.size()-1>index&&root.number>(list.get(index)).number)
                {
                    index++;
                }
    
                list.add(index,root);//插入列表中
            }
    
    /* 树已经建好了。但是还没编码。
             * 我之前对树做了点手脚
             * 让它每个节点记下自己当前处在左边还是右边。
             * 就像我们人工做时,左右写1和0一样。
             * 然后我们只要通过一次广度搜索并且把节点从上往下的加就好了
             * 广度收索为了减少回溯等时间。我们采取队列去做
             */
            Queue<Node> queue=new LinkedList<Node>();
            queue.add(list.get(0));
            while(!queue.isEmpty())
            {
                Node temp=queue.poll();
                if(temp.left!=null)
                {
                    temp.left.code=temp.code+temp.left.code;
                    queue.add(temp.left);
                }
                if(temp.right!=null)
                {
                    temp.right.code=temp.code+temp.right.code;
                    queue.add(temp.right);
                }
            }
            return list.get(0);//传出来应该就一个根节点了。
        }
    

    到上面为止一棵哈夫曼树就建好了。然后我们要把它变成字典。为了方便查找嘛
    采用广度收索的方式去查找
    这一步时间复杂度是O(N)

    //之前已经生成了一棵哈夫曼树,现在把这课哈夫曼树变成个字典。便于我们查找
        private static Map<Character,String> dictionary(Node root)
        {
            //把节点存放到map里方便查找(预处理)
            //这里通过广度搜索的方式存放节点
            Map<Character,String> map=new HashMap<Character,String>();
            Queue<Node> queue=new LinkedList<Node>();
            queue.add(root);
            while(!queue.isEmpty())
            {
                Node temp=queue.poll();
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
                if(temp.value=='#')
                    continue;
                map.put(temp.value, temp.code);
            }
            return map;
        }
    

    之后还得有转码字符串吧。吧字符串通过哈希表转码

    private static String createString(Map<Character,String> dictionary,String src)
        {
    
            StringBuilder answer=new StringBuilder();
            char[] array=src.toCharArray();
    
            //利用字典去查找检索
            for(int i=0;i<array.length;i++)
            {
                answer.append(dictionary.get(array[i]));
            }
            return answer.toString();
        }
    
    

    最后是解码
    /* 这里没办法减小算法复杂度了好像。就行查字典几个必须步骤好久就是这样
    * 需要全部遍历一下数组,同时每次找都得遍历下字典。
    * 为了尽可能的减少不必要的查找,我们用字典去找字符串
    * 看看传出来第一个找到的是不是第0位来加快速度
    */
    这一步时间复杂度是O(KN) K是字典大小。是个不定的东西

    private static String readString(Map<Character,String> dictionary,String src)
        {
            StringBuilder temp=new StringBuilder(src);//临时存放数据的
            StringBuilder result=new StringBuilder();
            while(temp.length()>0)
            {
                for(Map.Entry<Character, String> entry: dictionary.entrySet())
                {
                    if(temp.indexOf(entry.getValue())==0)//是不是第一位
                    {
                        result.append(entry.getKey());
                        temp.delete(0, entry.getValue().length());
                        break;
                    }
                }
            }
            return result.toString();
        }
    

    结束。
    下面是全部代码

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Queue;
    import java.util.Scanner;
    
    //用于哈夫曼树
    class Node
    {
        int number;//存放多少个数。就是指里面value有多少次出现在string里
        char value;
        Node(){}
        Node(char temp,int number)
        {
            value=temp;
            this.number=number;
        }
    
        String code="";//存放哈西曼数
        Node left=null;
        Node right=null;
        Node(Node a,Node b)
        {
            number=a.number+b.number;
            left=a;
            right=b;
            value='#';//中间节点
        }
    }
    
    public class Huffman 
    {
        public static void main(String[] argc)
        {
            Scanner cin=new Scanner(System.in);
            String code=cin.next().trim();
            huffmancoding(code);
        }
    
    
        //哈夫曼树部分
        //第一步计算所有的字符数量并按小到大排序
        private static List<Node> count(String src)
        {
            /*
             *此处我用map去数数。是为了降低时间复杂度。
             *如果直接开一个结点然后把结点放到列表里去,下次查找时就得从列队的第一个结点查到最后一个。
             *这样时间复杂度就是n^2了,而用map可以减低时间复杂度。因为它是HashMap时间复杂度是1
             */
            Map<Character,Integer> map=new HashMap<Character,Integer>();
            char[] charArray=src.toCharArray();
            for(Character c:charArray)
            {
                if(!map.containsKey(c))
                {
                    map.put(c,0);
                }
                map.put(c, map.get(c)+1);
            }
    
            //这是我们再把map里的字符和数量导入到结点里存储。这样就可以把这个函数的算法复杂度降低了
            List<Node> list=new ArrayList<Node>();
            for(Map.Entry<Character, Integer> entry:map.entrySet())
            {
                Node temp=new Node(entry.getKey(),entry.getValue());
                list.add(temp);
            }
            Collections.sort(list,(Node a,Node b)->(a.number<b.number?b.number:a.number));
            Collections.reverse(list);
            return list;
        }
    
        /*生成一棵哈夫曼树,并编码
         * 规则就是我们熟知的。左边填1,右边填0
         * 先选出数量少的去生成一棵树,然后最后把多的给嫁接上
         */
        private static Node buildTree(List<Node> list)
        {
            while(!(list.size()==1))
            {
                Node left=list.get(0);//先选出里面数量最少的当作左边节点
                left.code=left.code+"1";
                list.remove(0);//拿出来后记得删除它。便于下次再拿出一个头
    
                Node right=list.get(0);//由于前面的第一少的已经拿掉了。那么这个就变成第一少的了
                right.code=right.code+"0";
                list.remove(0);
    
                Node root=new Node(left,right);//然后生成一个新节点。把它放入数组中
    
                int index=0;//把索引定位。找到它在第几个数前面,为了插入回原来的列表。使这个列表的顺序还是有序的
                while(list.size()-1>index&&root.number>(list.get(index)).number)
                {
                    index++;
                }
    
                list.add(index,root);//插入列表中
            }
    
            /* 树已经建好了。但是还没编码。
             * 我之前对树做了点手脚
             * 让它每个节点记下自己当前处在左边还是右边。
             * 就像我们人工做时,左右写1和0一样。
             * 然后我们只要通过一次广度搜索并且把节点从上往下的加就好了
             * 广度收索为了减少回溯等时间。我们采取队列去做
             */
            Queue<Node> queue=new LinkedList<Node>();
            queue.add(list.get(0));
            while(!queue.isEmpty())
            {
                Node temp=queue.poll();
                if(temp.left!=null)
                {
                    temp.left.code=temp.code+temp.left.code;
                    queue.add(temp.left);
                }
                if(temp.right!=null)
                {
                    temp.right.code=temp.code+temp.right.code;
                    queue.add(temp.right);
                }
            }
            return list.get(0);//传出来应该就一个根节点了。
        }
    
        //之前已经生成了一棵哈夫曼树,现在把这课哈夫曼树变成个字典。便于我们查找
        private static Map<Character,String> dictionary(Node root)
        {
            //把节点存放到map里方便查找(预处理)
            //这里通过广度搜索的方式存放节点
            Map<Character,String> map=new HashMap<Character,String>();
            Queue<Node> queue=new LinkedList<Node>();
            queue.add(root);
            while(!queue.isEmpty())
            {
                Node temp=queue.poll();
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
                if(temp.value=='#')
                    continue;
                map.put(temp.value, temp.code);
            }
            return map;
        }
    
        //Test函数
        private static void huffmancoding(String src)
        {
            //哈夫曼树的字典
            Map<Character,String> temp=dictionary(buildTree(count(src)));
            System.out.println("哈夫曼编码");
            System.out.println("原字符串:"+src);
            System.out.print("字典: ");
            int i=1;
            for(Map.Entry<Character, String> entry: temp.entrySet())
            {
                if(i++%4==0)
                    System.out.println();
                System.out.print(entry.getKey()+"值为"+entry.getValue()+" ");
            }
            System.out.println();
            String result=createString(temp, src);
            System.out.println("编码后为:"+result);
            System.out.println("解码后为:"+readString(temp,result));
        }
    
        //这一步就是利用这课哈夫曼树对字符串进行编码
        private static String createString(Map<Character,String> dictionary,String src)
        {
    
            StringBuilder answer=new StringBuilder();
            char[] array=src.toCharArray();
    
            //利用字典去查找检索
            for(int i=0;i<array.length;i++)
            {
                answer.append(dictionary.get(array[i]));
            }
            return answer.toString();
        }
    
        //解码哈西曼编码
        /* 这里没办法减小算法复杂度了好像。就行查字典几个必须步骤好久就是这样
         * 需要全部遍历一下数组,同时每次找都得遍历下字典。
         * 为了尽可能的减少不必要的查找,我们用字典去找字符串
         * 看看传出来第一个找到的是不是第0位来加快速度
         */
        private static String readString(Map<Character,String> dictionary,String src)
        {
            StringBuilder temp=new StringBuilder(src);//临时存放数据的
            StringBuilder result=new StringBuilder();
            while(temp.length()>0)
            {
                for(Map.Entry<Character, String> entry: dictionary.entrySet())
                {
                    if(temp.indexOf(entry.getValue())==0)//是不是第一位
                    {
                        result.append(entry.getKey());
                        temp.delete(0, entry.getValue().length());
                        break;
                    }
                }
            }
            return result.toString();
        }
    }
    
    
    
    
    展开全文
  • 哈夫曼编码详解(C语言实现)

    万次阅读 多人点赞 2018-12-21 21:28:43
    关于算法我们可以从如下几部分分析:算法的逻辑结构、算法的存储结构、以及算法本身考虑,同时也需要考虑时间和空间的复杂度,关于哈夫曼编码,我们尝试着这几方面分析这个问题 逻辑结构 我们采用的是树这种的逻...

    解决问题:在信息传输、数据压缩的问题中,我们总希望能够找到一种编码能够将待处理数据压缩得尽可能短。对于这类问题,我们可以采用哈夫曼编码解决。

    解决问题的方法:我们可以通过构建哈夫曼树来得到哈夫曼编码。

    关于算法我们可以从如下几部分分析:算法的逻辑结构、算法的存储结构、以及算法本身考虑,同时也需要考虑时间和空间的复杂度,关于哈夫曼编码,我们尝试着这几方面分析这个问题

    逻辑结构

    我们采用的是这种的逻辑结构来解决

    原因:因为树的根与左右结点之间的路径都是唯一确定的,所以由根结点到各个叶子结点的路径都是唯一确定的,并且从根结点开始可以到达多个不同的叶子结点,所以我们采用树这种逻辑结构来实现哈夫曼编码。

    在创建哈夫曼树的过程中,由于一般编码都是由0和1组成,所以我们创建的哈夫曼树是一颗二叉树,只有左右两个孩子结点。

    存储结构

    我们采用静态链表的方法来存储哈夫曼树

    原因:因为我们会多次删除,插入新的结点,为了方便操作,所以我们采用链式存储的方式存储。但是只要给定了结点的个数,我们可以很容易计算出额外花费的空间,所以我们可以采用静态链表的方式存储,并且我们常常需要为新创建的结点添加孩子结点,为孩子结点添加它的双亲,这样我们必须使用多余的指针来保证这类操作的正确,为了简化理解并且方便我们一般使用静态三叉链表来存储哈夫曼树

    静态三叉链表的组成部分

    由于使用了二叉树这种逻辑结构,所以我们会有左右孩子域,LChild和RChild,并且为了保证能够清楚直到结点的双亲是谁,我们会有一个Parent域来存储双亲结点。由于哈夫曼编码生成的编码是不等长编码,会根据各个字符的出现频率来生成不同的编码,频率大的编码短,频率小的编码长。所以我们会额外有一个Weight域,权值域来表示各个编码的频率。我们也可以为了直到各个字符的名称也可以加上一个名字域。

    所以我们知道了一个链表结点的组成部分有哪些,并且我们可以构建这样一个结构体来存储这些部分

    //一个链表结点的组成部分
    typedef struct 
    {
     //char code; 			//这项属于可选择的部分
     int Weight;
     int Parent;
     int LChild;
     int RChild;
    }HuffmanTree[MAXSIZE+1],TreeNode;
    

    算法

    哈夫曼树的创建不同于一般树的创建,树的创建一般是由根节点开始,由上往下的顺序创建各个结点。但是哈夫曼树不同,哈夫曼树不同,哈夫曼树是按由下往上的顺序创建(因为我们不清楚根节点的左右两个结点是是什么,我们只直到哈夫曼树的叶子结点)

    由于这个原因,在哈夫曼树的创建过程中,我们我们都是将编码最长的两个结点作为新子树的左右孩子(因为编码最长代表着一定是在树的最下边位置),由于编码的长度代表着字符的权值(频率)

    因此在操作中,我们先得到最小还有次小两个权值的结点,记为mMin和sMin。用这两个结点创建一个新的结点(构建了一颗子树)。

    之后就将这个结点添加到已有的结点中,再将之前的最小,次小结点从结点中删除

    之后就是重复上面的操作

    在已有的结点中(包括之前添加的新结点,但上次的最小值,次小值因为删除了,所以不在已有结点中)找到最小,次小两个结点,在组成一颗新的子树,添加到已有结点中,然后再将之前最小、次小结点从结点中删除…

    这样一直操作下去,直到最后只剩下一个结点(N个结点,进行N-1次操作,因为最后一个结点没办法找到另外一个结点合并,N的结点只会创建N-1个新树,即进行N-1次操作)

    这样一颗哈夫曼树就创建完毕了

    //哈夫曼树的创建
    void CreatHuffmanTree(TreeNode *ht)  //哈夫曼树的创建 
    {
     int MNum,SNum;
     InitHuffmanTree(ht);		//哈夫曼树的初始化
     InputWeight(ht);		//得到字符的数目和每个字符的权值(频率)
     for(int i=1;i<NodeNum;i++)		//进行N-1次操作构建哈夫曼树
     {
      Select(ht,&MNum,&SNum);		//在已知结点得到最小,次小值
      len++;	//len的初值是结点的数目,即N。由于每次添加结点都是添加再已有结点的最后一位,即len+1的位置,所以每次len自增1
      ht[len].Weight=ht[MNum].Weight+ht[SNum].Weight;		//新子树的权值会等于它左右子树的权值之和
      ht[len].LChild=MNum;		//存左孩子值,一般规定左子树的值会比右子树的值小
      ht[len].RChild=SNum;		//存右孩子值
      ht[MNum].Parent=len;		//左孩子的双亲修改为新子树的数组下标
      ht[SNum].Parent=len;		//修改右孩子的双亲
     }
     return ;
    }
    

    注意:

    上述的代码并没有删除最小,次小的结点的部分,因为数组的删除不太方便,所以由于最小,次小的结点的双亲已经被修改了,我们将查找最小,次小值的判断条件添加一个条件—结点的双亲域不为0(初始化时,所有结点的双亲,孩子域都为0),若不为0,则代表该结点已经被删除了

    同样我们并没有将新结点添加到已有结点中,由于我们定义了一个len(全局变量,代表数组的长度),我们将得到最小,次小操作的范围规定为1到len(个人习惯,数组下标从1开始),len一开始等于输入的结点数NodeNum,随着新结点的创建,len的值也会增加,所以我们通过len表示添加新结点这个操作

    哈夫曼编码

    尽管得到了哈夫曼树,但是我们并没有得到各个字符的哈夫曼编码,所以我们需要由哈夫曼树得到哈夫曼编码

    一般默认左0右1,我们需要注意一点,左0带的是走左孩子这条路径,同理右1代表走右孩子这条路径,即编码的0和1是指路径而不是结点,这点不要弄错了

    我们先从根开始遍历一次哈夫曼树,先找到哈夫曼树的根,由于新添加的结点是在len位置,所以最后添加的结点也是len位置(数组下标从1开始,len=2*N-1,N为字符数目),找到根节点后,按照树的遍历,从左结点开始,由于走左的那条路径,我们需要存储一个0,所以我们需要一个存储哈夫曼编码的空间,我们使用什么存储呢?

    我们可以使用一个来存储哈夫曼编码,为什么不用队列呢?

    因为我们如果一个结点的左结点遍历完,返回到结点本身之前会将代表该路径的0出栈(为什么在返回之前出栈后面会解释的),在遍历右结点的时候,再入栈一个1就可以完成这个操作

    但是当我们如何判断当前结点是我们需要编码的字符结点呢?由于我们需要编码的字符都相当于哈夫曼树的根节点,所以我们可以根据当前结点是否有左孩子或者有右孩子(即左孩子域或者右孩子域是否为0)

    如果在结构体内定义了一个编码名称,则可以判断当前字符是否有名称(初始化可以把名称一起定义为0,输入的时候再改)

    由于一个子树结点必定是由两个结点组成,所以不可能出现有一个结点其中一个域为空,另一个域不为空这种情形,所以再判断的过程中只需要判断结点的左孩子域是否为空或者右孩子域是否为空其中一种即可

    当我们知道了如何判断一个结点是否是编码字符之后,我们应该如何输出编码字符的哈夫曼编码呢?由于我们是用栈来存储的编码,所以我们只按顺序输出栈内的值(只需要输出,而不是出栈,若是出栈的话,其余结点的编码会被破坏)

    输出之后要在返回之前执行一次出栈操作,表示返回上一个结点,也表示这条路径已经结束

    0代表左路径,1代表右路径,若不出栈,当走完左路径的所有编码结点,要返回上一个结点,去访问右路径的所有编码结点的时候,返回上一个结点后,但是上一个结点的左路径还在栈中,这会导致右路径的编码全部出错。

    void PrintHuffmanTree(TreeNode *ht,int root)  //输出哈夫曼编码
    {
     int data;
     if(ht[root].code!=0)   //由于我的结构体带有名称,所以我使用了编码名判断,判断当前结点是否是编码的结点,若不是,由于初始化的code编码名为0,所以由此判断 
     {
      printf("%c:",ht[root].code);  //输出编码名 
      PrintStack();  //输出编码 
      PushStack(); //每一次返回上一步,即当前结点已经有了编码,所以将栈顶出栈,计算其余的编码 
      return ;  
     }
     PopStack(0);  //若计算左结点则入栈0.右结点要入栈1
     PrintHuffmanTree(ht,ht[root].LChild); 
     PopStack(1); 	//走完左就走右,右入栈1
     PrintHuffmanTree(ht,ht[root].RChild);
     PushStack();  //返回前出栈,代表当前路径结束,要开始其他路径的编码计算
     return ;
     }
     void PrintStack(void)  //输出编码,若需要翻译则需要用另外一个数组存储编码名和编码然后再进行翻译 
    {
     for(int i=0;i<s.top+1;i++) //不进行出栈操作,因为若其他的结点和该结点有相同的Parent,其前面一部分编码相同 
      printf("%d",s.data[i]);
     printf("\n");;
     return ;
    }
    

    给一串编码,要求输出编译后的结果

    我们知道哈夫曼树的每个叶子结点都代表了一个编码结点,所以我们只需要按照遇0走左,遇1走右,从根节点开始走一直走到叶子结点,再输出叶子节点的编码名并重新从根节点开始就可以了

    void Translate(TreeNode *ht)
    {
     char ch[80];
     int i=0,j=len;
     printf("请输入要进行编译的密码:");
     gets(ch);
     while(ch[i])
     {
      if(ch[i]=='0')   //先执行再判断,因为哈夫曼树第一个结点肯定不是编码结点,所以需要先做处理再进行判断是否是编码结点 
      {
       j=ht[j].LChild;  //若为0,走左分支 
      }
      if(ch[i]=='1')  //若为1,走右分支 
      { 
       j=ht[j].RChild;
      }
     
      if(ht[j].code!=0)   //判断当前哈夫曼树结点是否是编码结点,若是编码结点,则其code值为编码 
      {
       printf("%c",ht[j].code);
       j=len;  //将结点重新放到哈夫曼树的根节点位置,重新开始,直到所有密码编译完成 
      } 
      i++;  //i自增
     }
    }
    
    展开全文
  • 高效算法——06哈夫曼编码(Python)

    千次阅读 2019-07-15 20:44:30
    06哈夫曼编码 复杂度: O(nlogn) 算法: #coding=utf-8 """ 算法:哈夫曼编码 作者:lph-China 时间:2019/7/15 """ def huffman(freq): h = [] for a in freq: heappush(h, (freq[a], a)) while ...

    06哈夫曼编码

     

    复杂度: O(nlogn)

    算法: 

    #coding=utf-8
    """
        算法:哈夫曼编码
        作者:lph-China
        时间:2019/7/15
    """
    
    def huffman(freq):
    
       h = []
       for a in freq:
           heappush(h, (freq[a], a))
       while len(h) > 1:
           (fl, l) = heappop(h)
           (fr, r) = heappop(h)
           heappush(h, (fl + fr, [1, r]))
       code = {}
       extract(code, h[0][1])
       return code
    
    def extract(code, tree, prefix = ""):
        if isinstance(tree, list):
            l, r = tree
            extract(code, l, prefix + "0")
            extract(code, r, prefix + "1")
        else:
            code[tree] = prefix

     

    展开全文
  • 问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即...
  • 1. 该程序可对不含中文字符的...其中创建Huffman树的时间复杂度被优化为O(nlog2n),编码中根据字符查询对应的编码时间复杂度被优化为O(log2n) 4. 使用C++编写。 5. 模块之间低耦合,便于维护,代码可重用性高。
  • 1.题目 哈夫曼树的应用 要传输一则报文内容如下: “AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF” 请为这段报文设计哈夫曼编码...请分析算法的效率,至少包括时间复杂度和空间复杂度等。 2.分析
  • 草稿版代码 内容超详细 可压缩任何文件类型 本人亲测 但代码有些部分时间复杂度待优化
  • Huffman编码(哈夫曼编码),

    千次阅读 2015-12-13 16:27:22
    实现Huffman编码是用贪心算法来实现的,。实现Huffman最好的数据结构时优先级队列...但是这里的时间复杂度却提高了,因为操作set的选择时,时间复杂度时lgn,但是随着选择的,选择“未被访问的最高优先级的两个元素(fl
  • 在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 基于C++的哈夫曼编码

    2019-08-13 13:48:00
    通过综合设计,使学生学会分析研究数据结构的特征,以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法,掌握算法的时间复杂度分析技术。另一方面,综合设计也是复杂程序设计的训练过程,要求学生编写的...
  • 1) 问题描述设某编码系统共有n个字符,使用频率分别为{w1, w2, …, wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。2) 基本要求(1) 设计数据结构;...(3) 分析时间复杂度和空间复杂度。
  • 时间复杂度(一)

    2018-08-25 16:15:41
    二叉查找树——时间复杂度logN(N总数) 高度初值1 深度初值0   AVL高度平衡树 红黑树插入N个——时间复杂度NlogN 哈夫曼树,权值大的靠近根。应用于变长编码表中...
  • 什么是堆? 堆是按照一定顺序组织的完全二叉树 ...可以,查找与删除的时间复杂度均为以2为底n的对数即log(2)n 二叉搜索树? 如果采用二叉树结构,应更关注插入还是删除?(删除)  树结点顺序怎么...
  • 注:实现Huffman编码是用贪心算法来实现的,证明Huffman的贪心选择和最...整个算法的时间复杂度可以达到nlg(n),这里为了简单,没有实现最小堆,而使用的是STL中的set,通过实现正确的比较函数对象,每次可以取得优先级
  • # 求大佬看下这段代码的时间复杂度和空间复杂度,一直不太会算这个 ``` #include typedef struct { double weight; int parent; int lchild, rchild; }Node; typedef struct { int node[12]; int ...
  • 注:实现Huffman编码是用贪心算法来实现的,证明Huffman的贪心选择和最...整个算法的时间复杂度可以达到nlg(n),这里为了简单,没有实现最小堆,而使用的是STL中的set,通过实现正确的比较函数对象,每次可以取得优先级
  • 注:实现Huffman编码是用贪心算法来实现的,证明Huffman的贪心选择...整个算法的时间复杂度可以达到nlg(n),这里为了简单,没有实现最小堆,而使用的是STL中的set,通过实现正确的比较函数对象,每次可以取得优先级...
  • 通过综合设计,使学生学会分析研究数据结构的特征,以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法,掌握算法的时间复杂度分析技术。另一方面,综合设计也是复杂程序设计的训练过程,要求学生编写的...
  • 时间复杂度 空间复杂度 说明 Hanoi $ O(2^n) $ $ O(n) $ 递归使用 会场安排问题 \(O(nlogn)\) \(O(n)\) 贪心 哈夫曼编码 \(O(nlogn)\) \[O(n)\] 贪心 \[O(n^2) \](未采用特殊数据结构) dijkstra \(O(n...
  • ⑷ 分析时间复杂度和空间复杂度。 3. 设计思想 对于给定的文档,首先通过扫描确定文档中出现了哪些英文字母以及出现的次数,以出现的次数作为叶子结点的权值构造哈夫曼树,获得各字符的哈夫曼编码;然后再扫描一...
  • 数据结构——哈夫曼编/译码器

    千次阅读 2019-02-01 12:36:38
    在上交资料中请写明:存储结构、基本算法(可以使用程序流程图)、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息...
  • 题意:给一个长度为n的数列a,q组询问,每组询问求将li到ri的区间中的数哈夫曼编码的长度。莫队,对于每一个询问处理该区间内出现次数为x的字符个数。 对于次数小于n√\sqrt{n} 的字符,从小到大枚举出现次数,...
  • 「一本正经的聊数据结构(1):时间复杂度」 「一本正经的聊数据结构(2):数组与向量」 「一本正经的聊数据结构(3):栈和队列」 「一本正经的聊数据结构(4):树」 「一本正经的聊数据结构(5):二叉树的存储...
  • 我们知道堆的插入、删除操作的时间复杂度都是 O(logN)O(logN),自然优先队列的插入、删除操作的时间复杂度也都是 O(logN)O(logN)。堆中的堆顶元素就是优先队列的队首元素。对于大根堆实现的优先队列,总是优先级高的...
  • 【树】哈夫曼树(一)

    2016-12-09 19:39:49
    题目大意给你字母的个数n,然后各个字母在电文中的出现的频率,为这n个字母设计哈夫曼编码。用二进制数表示这n个字母的编码方案.(左子树根节点的权小于等于右子树根节点的权,按中序遍历输出)思路此题时间复杂度...

空空如也

空空如也

1 2 3 4
收藏数 76
精华内容 30
关键字:

哈夫曼编码时间复杂度