【算法】记录一下最近实现的哈夫曼编码压缩文本

本贴最后更新于 309 天前,其中的信息可能已经时移世易
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <fstream>

using namespace std;

struct HuffmanTreeNode{
    char ch_;
    int freq_;
    HuffmanTreeNode* left_,* right_;

    HuffmanTreeNode(char ch, int freq): ch_(ch), freq_(freq) {
        left_ = nullptr;
        right_ = nullptr;
    }

    bool isLeaf() const {
        return left_ == nullptr && right_ == nullptr;
    }
};

//用于HuffmanTreeNode在优先队列的比较
struct Compare {
    bool operator()(HuffmanTreeNode* l, HuffmanTreeNode* r) {
        return l->freq_ > r->freq_;
    }
};

struct BitCharBuffer {
    vector<char>* buffer;
    int bit_length;
};

HuffmanTreeNode* buildTree(string str) {
    int freq[256]{0};
    for (auto it = str.begin(); it != str.end(); ++it) {
        freq[(*it) + 128]++;
    }

    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> que;
    for (int i = 0; i < 256; i++) {
        if (freq[i] != 0) {
            que.push(new HuffmanTreeNode(i - 128, freq[i]));
        }
    }

    while (que.size() > 1) {
        HuffmanTreeNode* left = que.top(); que.pop();
        HuffmanTreeNode* right = que.top(); que.pop();
        HuffmanTreeNode* node = new HuffmanTreeNode('\0', left->freq_ + right->freq_);
        node->left_ = left;
        node->right_ = right;
        que.push(node);
    }

    return que.top();
}

void treeToMap(HuffmanTreeNode* root, vector<bool>& code, unordered_map<char, vector<bool>>& code_map) {
    if (root == nullptr) return;

    if (!root->left_ && !root->right_) {
        code_map[root->ch_] = code;
    }
    code.push_back(0);
    treeToMap(root->left_, code, code_map);
    code.pop_back();

    code.push_back(1);
    treeToMap(root->right_, code, code_map);
    code.pop_back();
}

void treeToMap(HuffmanTreeNode* root, unordered_map<char, vector<bool>>& code_map) {
    vector<bool> code;
    treeToMap(root, code, code_map);
}

void writeBuffer(const vector<bool>& code, BitCharBuffer& char_buffer, int offset, int length) {
    int index = char_buffer.bit_length / 8;
    int alpha = char_buffer.bit_length % 8;
    for (int i = offset; i < offset + length; i++) {
        if (alpha == 0) {
            char_buffer.buffer->push_back(0);
        }
        (*(char_buffer.buffer))[index] += ((char)code[i] << (7 - alpha));
        char_buffer.bit_length++;
        alpha++;
        if (alpha == 8) {
            index++;
            alpha = 0;
        }
    }
}

void writeBuffer(const vector<bool>& code, BitCharBuffer& char_buffer, int offset = 0) {
    writeBuffer(code, char_buffer, offset, code.size() - offset);
}

void encode(const string& str, ostream& os, unordered_map<char, vector<bool>>& code_map) {
    int max_length = 1 << 15; //缓冲区大小,单位bit,需要为 1 << 4 的整数倍,小于int最大值
    BitCharBuffer char_buffer;
    char_buffer.buffer = new vector<char>(0);
    char_buffer.bit_length = 0;

    for (auto it = str.begin(); it != str.end(); ++it) {
        char ch = *it;
        const vector<bool>& code = code_map[ch];
        //如果达到长度上限,写入output stream,然后重开缓冲区
        if (max_length - code.size() < char_buffer.bit_length) {
            int temp = char_buffer.bit_length;
            //先把当前的buffer写满
            writeBuffer(code, char_buffer, 0, max_length - char_buffer.bit_length);
            //输出到os
            os.write(char_buffer.buffer->data(), char_buffer.buffer->size());
            //释放旧缓冲区,分配新缓冲区
            delete char_buffer.buffer;
            char_buffer.buffer = new vector<char>(0);
            char_buffer.bit_length = 0;
            //将超长的部分写进新缓冲区
            writeBuffer(code, char_buffer, max_length - temp);
        }
        else
            writeBuffer(code, char_buffer);
    }

    os.write(char_buffer.buffer->data(), char_buffer.buffer->size());
}

void decode(const string& str, ostream& os, HuffmanTreeNode* root) {
    HuffmanTreeNode* current = root;
    char camp = 1 << 7;
    for (auto it = str.begin(); it != str.end(); ++it) {
        char byte = *it;
        for (int i = 0; i < 8; i++) {
            if (camp & byte) {
                current = current->right_;
            }
            else {
                current = current->left_;
            }
            if (current->isLeaf()) {
                os << current->ch_;
                if (current->ch_ == '\0') return; //特殊地,输出结尾标记后停止译码
                current = root;
            }
            byte = byte << 1;
        }
    }
}

int main() {
    ifstream ifs("source.txt");
    if (!ifs.is_open()) {
        cout << "打开sources.txt输入流失败" << endl;
        return 0;
    }

    string str((std::istreambuf_iterator<char>(ifs)), std::istreambuf_iterator<char>());
    str += '\0';  //哈夫曼编码是变长的,但文件操作的最小单位是byte(定长8bit),因此需要一个结尾标记。
    HuffmanTreeNode* root = buildTree(str);
    unordered_map<char, vector<bool>> map;
    treeToMap(root, map);

    ofstream ofs("code.dat", ios::binary);
    if (!ofs.is_open()) {
        cout << "打开code.dat输出流失败" << endl;
    }
    else{
        encode(str, ofs, map);
        ofs.close();
    }

    ifstream difs("code.dat", ios::binary);
    if (!difs.is_open()) {
        cout << "打开code.dat输入流失败" << endl;
    }
    else {
        string code_str((std::istreambuf_iterator<char>(difs)), std::istreambuf_iterator<char>());
        decode(code_str, cout, root);
        difs.close();
    }

    delete root;
    ifs.close();
}

是快速实现,没有弄接口,直接用 main 函数测试的。转发随意。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 101 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    565 引用 • 3532 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 684 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • Sillot

    Insights(注意当前设置 master 为默认分支)

    汐洛彖夲肜矩阵(Sillot T☳Converbenk Matrix),致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点。其中汐洛绞架(Sillot-Gibbet)基于自思源笔记(siyuan-note),前身是思源笔记汐洛版(更早是思源笔记汐洛分支),是智慧新录乄终端(多端融合,移动端优先)。

    主仓库地址:Hi-Windom/Sillot

    文档地址:sillot.db.sc.cn

    注意事项:

    1. ⚠️ 汐洛仍在早期开发阶段,尚不稳定
    2. ⚠️ 汐洛并非面向普通用户设计,使用前请了解风险
    3. ⚠️ 汐洛绞架基于思源笔记,开发者尽最大努力与思源笔记保持兼容,但无法实现 100% 兼容
    29 引用 • 25 回帖 • 78 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • JetBrains

    JetBrains 是一家捷克的软件开发公司,该公司位于捷克的布拉格,并在俄国的圣彼得堡及美国麻州波士顿都设有办公室,该公司最为人所熟知的产品是 Java 编程语言开发撰写时所用的集成开发环境:IntelliJ IDEA

    18 引用 • 54 回帖
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 127 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 6 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 47 关注
  • BAE

    百度应用引擎(Baidu App Engine)提供了 PHP、Java、Python 的执行环境,以及云存储、消息服务、云数据库等全面的云服务。它可以让开发者实现自动地部署和管理应用,并且提供动态扩容和负载均衡的运行环境,让开发者不用考虑高成本的运维工作,只需专注于业务逻辑,大大降低了开发者学习和迁移的成本。

    19 引用 • 75 回帖 • 632 关注
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 53 关注
  • PostgreSQL

    PostgreSQL 是一款功能强大的企业级数据库系统,在 BSD 开源许可证下发布。

    22 引用 • 22 回帖 • 1 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    107 引用 • 295 回帖
  • 自由行
    3 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 257 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    124 引用 • 580 回帖
  • 脑图

    脑图又叫思维导图,是表达发散性思维的有效图形思维工具 ,它简单却又很有效,是一种实用性的思维工具。

    25 引用 • 83 回帖 • 1 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 383 关注
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖
  • 学习

    “梦想从学习开始,事业从实践起步” —— 习近平

    168 引用 • 504 回帖
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 2 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 533 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    46 引用 • 25 回帖
  • Pipe

    Pipe 是一款小而美的开源博客平台。Pipe 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    131 引用 • 1114 回帖 • 131 关注
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖