Huffman实现

Huffman编码树

秒懂:【算法】Huffman编码_哔哩哔哩_bilibili

Huffman实现

约定:字符x的编码长度 就是其对应叶节点的深度;

在一个字符集中,每个字符出现的次数有多有少,那么若都采用固定长度编码的话,那么编码长度会非常大,并且搜索时间复杂度都非常高;若采用非固定编码,出现次数多的字符编码长度小一些,并且放在树深度小的地方,提高搜索时间效率;这样带权平均编码长度(weight average leaf depth)就会达到最优;同时为了避免歧义,任何字符不能是其他字符的编码前缀;还有一点就是没有度为1的节点,也就是说是一颗满二叉树;

个人理解:

没有前缀:在具体实现时,由 priority_queue 排序完成后的 节点权值树 再转存在map中时,不会存储根节点,只会存叶子节点,就能避免前缀相同的情况;还有一点就是第一个设置为0,而不是1,1的话就会成为其他字符的前缀;

没有度为1 的节点 和 无前缀相同编码 的不一定是Huffman,还需满足 ald 最短;

时间复杂度:对于出现次数多的字符,让它在靠近根节点位置,这样就能接近O(1)时间复杂度;而对于出现次数少的字符,就靠近树的最底部位置;

具体实现

代码参考:Canonical Huffman Coding - GeeksforGeeks

1、实现一个struct,保存字符出现的次数,以及字符本身,还有左右子节点;

2、写一个路径长度模块函数,create_code();

3、写一个Huffman编码函数,create_huffman(); 其中, 先按频率从小到大排列,然后取最小的两个合并为一大的,在继续合并直至成为一个根节点,再将字符树存进map中;接着实现Huffman编码;

  ①在编码时,利用路径长度信息,和bitset<32>类,实现位操作,并且利用成员函数to_string()转化为字符串,左边为高位,右边为低位;substr函数第二个参数长度设置为32,默认到头;

Huffman实现

  ②怎么利用路径长度信息的? 比如说代码中 给出的例子c,编码为0,假设还有叶子节点,那么当前编码值加上1,然后再左移(下一层的深度 - 当前层的深度)位,即 0 +1 = 12,再左移(2-1)位,变成102;在内层循环中,当是同一层的最后两个叶子节点时,即110 和 111 , 不做左移,只做值加一操作,代码这儿用了一个next_len 和 cur_len 相减实现左移的次数值;(非常巧妙);

  ③学到了一个next 函数,和 bitset 位操作;

#include <bits/stdc++.h>
using namespace std;

/*Huffman codes : a lossless data compression algorithm; weighted average leaf depth(带权平均深度最小)*/
struct Node{
    int data;
    char c;
    Node* left, *right;
};

struct mycomp{
    bool operator()(Node* a, Node* b){
        return a->data > b->data;
    }
};

class huffman{
private:
    map<int, set<char>> data;
public:
    huffman(){}
    void create_code(Node* root, int code_len){
        if(root == nullptr){
            return;
        }
        /*only store leaf node*/
        if(root->left == nullptr && root->right == nullptr){
            data[code_len].insert(root->c);
        }
        create_code(root->left, code_len + 1);
        create_code(root->right, code_len + 1);
    }
    void create_huffman(int n, char arr_char[], int freq[]){
        /* 小顶堆  取堆顶 freq 小的两个合并*/
        priority_queue<Node*, vector<Node*>, mycomp>que;
        for(int i = 0;i < n;++i){
            Node* newnode = new Node();
            newnode->c = arr_char[i];
            newnode->data = freq[i];
            newnode->left = nullptr;
            newnode->right = nullptr;
            que.push(newnode);
        }
        /*Node Tree*/
        Node* root = nullptr;
        while(que.size() > 1){
            Node* tmp1 = que.top();
            que.pop();
            Node* tmp2 = que.top();
            que.pop();
            Node* mergeNode = new Node();
            mergeNode->data = tmp1->data + tmp2->data;
            mergeNode->c = '-';
            mergeNode->left = tmp1;
            mergeNode->right = tmp2;
            root = mergeNode;
            que.push(mergeNode);
        }
        huffman obj = huffman();
        create_code(root, 0);
        int cur_code = 0, cur_len = 0, next_len = 0;
        for(map<int, set<char>>::iterator it = data.begin(); it != data.end(); ++it){
            set<char> s = it->second;
            cur_len = it->first;
            for(auto i = s.begin(); i != s.end(); ++i){
                cout << *i << " : ";
                /* coding */
                cout << bitset<32>(cur_code).to_string().substr(32 - cur_len, 32) << endl;
                
                /* 相同长度 有一个以上叶子节点时 : 这种情况只出现在 尾部的那俩个元素*/
                if(next(i) != s.end() || next(it) == data.end()) next_len = cur_len;
                else next_len = next(it)->first;
                
                cur_code = (cur_code + 1) << (next_len - cur_len);
            }
        }
    }
};

int main(){
    int n = 4;
    char arr[] = {'a', 'b', 'c', 'd'};
    int fre[] = {10, 1, 15, 7};
    huffman obj;
    obj.create_huffman(n,arr,fre); 
    system("pause");
    return 0;
}
/*
c : 0
a : 10
b : 110
d : 111
*/

 

原文链接:https://www.cnblogs.com/xuan01/p/17317584.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Huffman实现 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • python中heapq堆排算法的实现

    以下是关于“Python中heapq堆排算法的实现”的完整攻略: 简介 堆排算法是一种常用的排序算法,它可以将一个无序的序列转换为一个有序的序列。Python中的heapq模块提供了堆排算法的实现。本教程将介绍如何使用Python中的heapq模块实现堆排算法,并提供两个示例。 heapq模块 heapq模块是Python中的一个标准库,它提供了堆排算法的实…

    python 2023年5月14日
    00
  • 数据结构 中数制转换(栈的应用)

    数据结构 中数制转换(栈的应用) 1. 什么是数制转换? 数制转换是从一种数字表示方式(即一种进位制,如二进制、八进制、十进制、十六进制等)转化为另一种数字表示方式的过程。在数制转换中,可以使用栈这种数据结构来进行转换的具体实现。 2. 根据位值权重的转换方法 2.1. 十进制转换为其他进制 2.1.1. 除余法 将十进制数不断除以目标进制的基数,比如2(表…

    数据结构 2023年5月17日
    00
  • 遗传算法之Python实现代码

    下面是详细讲解“遗传算法之Python实现代码”的完整攻略。 遗传算法 遗传算法是一种基于自然选择和遗传学原理的优算法,可以用于解决许多优化问题。其基本思想是通过模拟自然界中的进化过程,不断从种群中选择优秀的个体,并通过交叉和变异操作产生新的个体,最终得到最优解。 下面是一个Python实现遗传算法的示例: import random def fitness…

    python 2023年5月14日
    00
  • C#模拟链表数据结构的实例解析

    C#模拟链表数据结构的实例解析 简介 链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和指向下一个节点的指针。本篇文章将介绍如何使用 C# 来模拟链表数据结构,并通过两个示例展示如何实现链表的操作。 链表的基本结构 链表是由一系列节点组成的,每个节点包含一个数据元素和指向下一个节点的指针。我们可以通过以下代码定义一个链表节点的类: pu…

    数据结构 2023年5月17日
    00
  • 利用PyTorch实现爬山算法

    利用PyTorch实现爬山算法 爬山算法(Hill Climbing)是一种基于局部搜索的优化算法,它的主要思想是从当前解的邻域中选择一个更优的解作为下一次搜索的起点,直到找到最优解或达到最大迭代次数。本文将详细讲解如何使用PyTorch实现爬山算法,并提供两个示例说明。 爬山算法原理 爬山算法的基本思想是从当前解的邻域中选择一个更优的解作为下一次搜索的起点…

    python 2023年5月14日
    00
  • Python 实现数据结构-堆栈和队列的操作方法

    Python 实现数据结构-堆栈和队列的操作方法 在Python中,我们可以使用列表(List)数据类型来实现堆栈和队列的操作。 堆栈(Stack)的操作方法 堆栈数据结构可以理解为一种后进先出的数据存储方式,也就是说最后放入堆栈的元素最先被取出。下面介绍一下堆栈的操作方法。 创建一个堆栈 我们可以通过创建一个空的列表来实现一个堆栈。代码如下: stack …

    数据结构 2023年5月17日
    00
  • Python&Matlab实现灰狼优化算法的示例代码

    Python&Matlab实现灰狼优化算法的示例代码 灰狼优化算法(Grey Wolf Optimizer,GWO)是一种基于自然界中灰狼群体行为优化算法。该算法模拟了灰狼群体中的领袖、副领袖和普通狼的行为,通过不断地迭代找最优解。灰狼优化算法具有收敛速度快、全局搜索能力强等优点,在优化问题中得到了广泛的应用。 Python实现灰狼优化算法的示例代码…

    python 2023年5月14日
    00
  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 什么是KMP算法和Next()函数 KMP算法(Knuth-Morris-Pratt算法)是一种字符串匹配算法,能够解决的问题是,在一个文本串S中查找一个模式串P是否出现并且返回第一次出现的位置。而Next()函数则是在KMP算法中使用的一个关键的子函数,用于计算模式串P中每个前缀的最长相同真前缀和后…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部