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排序算法之选择排序

    以下是关于“Python排序算法之选择排序”的完整攻略: 简介 选择排序是一种简单的排序算法,它的基本思想是每次从未排序的元素中选择最小的元素,将其放到已排序的元素末尾。在本教程中,我们将介绍如何使用Python实现选择排序,并提供一些示例说明。 Python选择排序实现 以下是使用Python实现选择排序的示例: def selection_sort(ar…

    python 2023年5月14日
    00
  • 在Python中实现贪婪排名算法的教程

    在Python中实现贪婪排名算法的教程 贪婪排名算法是一种常用的排序算法,其基本思想是根据每个元素的权重值进行排序,从而得到排名列表。在Python中可以使用sorted()函数实现贪婪排名算法。本文将详细讲解Python实现贪婪排名算法的完整攻略,包算法原理、Python实现过程和示例。 算法原理 贪婪排名算法的基本思想是:根据每个素的权重值进行排序,从而…

    python 2023年5月14日
    00
  • C语言类的双向链表详解

    C语言类的双向链表详解 基本概念 什么是双向链表? 双向链表是链表的一种,它有两个指针域:一个指向前一个结点,一个指向后一个结点。每个结点包含两个部分:数据和指针域,指针域分别指向前一个结点和后一个结点,所以每个结点都是由数据和两个指针域构成的。 双向链表的作用? 双向链表可以支持O(1)时间复杂度的在任何一个结点前或后插入一个结点。 双向链表的实现方式? …

    数据结构 2023年5月17日
    00
  • K最近邻算法(KNN)—sklearn+python实现方式

    以下是关于“K最近邻算法(KNN)—sklearn+python实现方式”的完整攻略: 简介 K最近邻算法(KNN)是一种用于分类和回归的机器学习算法,它可以根据最近的K个邻居来预测新数据点的标签或值。在本教程中,我们将介绍如何使用Python和sklearn库实现KNN算法,并提供两个示例说明。 实现KNN算法 以下是使用Python和sklearn库…

    python 2023年5月14日
    00
  • 【ACM博弈论】SG函数入门(1):从巴什博奕到尼姆游戏

    在我小时候以前做题的时候,遇到博弈题往往都是漫无目的地打表找规律,或者找一些特殊情况但是没有很好的分析方法。 其实博弈题是有比较套路的解题方法的,那就是利用SG函数,第一节不会讲到SG函数的具体用法,我们先来博弈入个门,学习一下最基本的博弈类型:Nim游戏。 ? 作者:Eriktse? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式…

    算法与数据结构 2023年4月17日
    00
  • python实现感知器算法详解

    下面是关于“Python实现感知器算法详解”的完整攻略。 1. 感知器算法理论基础 感知器算法是一种二分类算法,它可以用来将数据分为两类。感知器法的基本思想是,将输入数据通过一个线性函数进行加权求和,然后通过一个阈值函数进行分类。感知器算法训练过是通过不断调整权重和阈值来实现的,以达到最优的分类效果。 2. Python实现 下是使用Python实现感知器算…

    python 2023年5月13日
    00
  • C语言数据结构 快速排序实例详解

    C语言数据结构 快速排序实例详解 什么是快速排序? 快速排序(Quicksort)是一种采用分治法(Divide and Conquer)的排序算法,通过将一个大问题逐步分解为小问题来解决的一种工具。 快速排序是一个比较快的排序算法,在平均状况下,排序n个项目要 O(n log n) 次比较,最坏情况下需要O(n^2)次比较,但这种状况并不常见。 快速排序算…

    数据结构 2023年5月17日
    00
  • 用Python给图像算法做个简单应用界面

    下面是详细讲解“用Python给图像算法做个简单应用界面”的完整攻略,包含两个示例说明。 应用界面的作用 应用界面是一种非常有用的工具,可以帮助用户更方便地使用图像算法。应用界面可以提供以下功能: 显示图像 提供算法选项 显示算法结果 保存算法结果 应用界面可以使用户更轻松地使用图像算法,而不需要编写代码或使用命令行界面。 Python实现应用界面 Pyth…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部