热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Golomb编码解析:利用零位标识商与余数的高效算法

Golomb编码是一种高效的变长编码技术,专门用于整数的压缩。该方法通过预定义的参数\(M\)将输入整数分解为商\(q\)和余数\(r\)两部分。具体而言,输入整数除以\(M\)得到商\(q\)和余数\(r\),其中商\(q\)采用一元编码表示,而余数\(r\)则使用二进制编码。这种编码方式在数据压缩和信息传输中具有显著的优势,特别是在处理具有特定概率分布的数据时表现出色。

哥伦布编码是一个针对整数的变长编码方式,详细介绍可以看维基百科。这里简单介绍下:

哥伦布编码使用指定的整数 M 把输入的整数分成两部分:商数 q、余数 r。 商数当做一元编码,而余数放在后面做为可缩短的二进制编码。

将整数变为一元编码非常简单:q 的一元编码结果就是 q 个 1 加上 1 个 0。如下表:

整数一元编码
00
110
2110
31110
411110
5111110
61111110

一元编码可以用以下代码实现;

function unary_encoding(q) {return (1 <<(q &#43; 1)) - 2; }

将 M 选为 64 时&#xff0c;余数取值区间为 [0, 64)&#xff0c;只需要用 6 位二进制表示。将待处理的数组每一项都除以 64&#xff0c;并将商数和余数分别做一元编码和二进制编码&#xff0c;得到如下结果&#xff1a;

整数商数余数商数一元编码余数二进制编码
151223110010111
410410101001
160160010000
610610111101
192301110000000
     

表格中每一行后两列拼起来就是该整数对应的哥伦布编码&#xff0c;可以看到&#xff0c;64 以下的整数编码后会变短。

这段代码运行结果如下&#xff1a;

["110010111", "0101001", "0010000", "0111101", "1110000000"]


摘自&#xff1a;https://imququ.com/post/golomb-coded-sets.html

go语言的实现&#xff1a;
https://github.com/tcnksm/go-casper/blob/master/internal/encoding/golomb/golomb.go

https://github.com/dave-andersen/deltagolomb/blob/master/deltagolomb.go

 

GOLOMB-RICE 编码

Golomb-Rice是Golomb编码的一个变种&#xff0c;它给Golomb编码的参数m添加了个限制条件&#xff1a;m必须是2的次幂。这样有两个好处&#xff1a;

不需要做模运算即可得到余数r&#xff0c;r &#61; N & (m - 1) 对余数r编码更为简单&#xff0c;只需要取r二进制的低\(\log_2(m)\)位即可。

则Golomb-Rice的编码过程更为简洁&#xff1a;

初始化参数m&#xff0c;m必须为2的次幂 计算q和r&#xff0c;q &#61; N / m ; r &#61; N & (m - 1) 使用一元编码编码q 取r的二进制位的低\(\log_2(m)\)位作为r的码字。

转载于:https://www.cnblogs.com/bonelee/p/6878992.html


推荐阅读
  • 如何高效解决Android应用ANR问题?
    本文介绍了ANR(应用程序无响应)的基本概念、常见原因及其解决方案,并提供了实用的工具和技巧帮助开发者快速定位和解决ANR问题,提高应用的用户体验。 ... [详细]
  • 问题描述现在,不管开发一个多大的系统(至少我现在的部门是这样的),都会带一个日志功能;在实际开发过程中 ... [详细]
  • Requests库的基本使用方法
    本文介绍了Python中Requests库的基础用法,包括如何安装、GET和POST请求的实现、如何处理Cookies和Headers,以及如何解析JSON响应。相比urllib库,Requests库提供了更为简洁高效的接口来处理HTTP请求。 ... [详细]
  • 深入探讨前端代码优化策略
    本文深入讨论了前端开发中代码优化的关键技术,包括JavaScript、HTML和CSS的优化方法,旨在提升网页加载速度和用户体验。 ... [详细]
  • Go从入门到精通系列视频之go编程语言密码学哈希算法(二) ... [详细]
  • 在OpenCV 3.1.0中实现SIFT与SURF特征检测
    本文介绍如何在OpenCV 3.1.0版本中通过Python 2.7环境使用SIFT和SURF算法进行图像特征点检测。由于这些高级功能在OpenCV 3.0.0及更高版本中被移至额外的contrib模块,因此需要特别处理才能正常使用。 ... [详细]
  • Bootstrap Paginator 分页插件详解与应用
    本文深入探讨了Bootstrap Paginator这款流行的JavaScript分页插件,提供了详细的使用指南和示例代码,旨在帮助开发者更好地理解和利用该工具进行高效的数据展示。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • AI炼金术:KNN分类器的构建与应用
    本文介绍了如何使用Python及其相关库(如NumPy、scikit-learn和matplotlib)构建KNN分类器模型。通过详细的数据准备、模型训练及新样本预测的过程,展示KNN算法的实际操作步骤。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • 本文介绍如何使用JavaScript中的for循环来创建一个九九乘法表,适合初学者学习循环结构的应用。 ... [详细]
  • protobuf 使用心得:解析与编码陷阱
    本文记录了一次在广告系统中使用protobuf进行数据交换时遇到的问题及其解决过程。通过这次经历,我们将探讨protobuf的特性和编码机制,帮助开发者避免类似的陷阱。 ... [详细]
  • 汇编语言:编程世界的始祖,连C语言都敬畏三分!
    当C语言还在萌芽阶段时,它首次接触到了汇编语言,并对其简洁性感到震惊。尽管汇编语言的指令极其简单,但它却是所有现代编程语言的基础,其重要性不言而喻。 ... [详细]
  • c语言二元插值,二维线性插值c语言
    c语言二元插值,二维线性插值c语言 ... [详细]
  • 嵌套列表的扁平化处理
    本文介绍了一种方法,用于遍历嵌套列表中的每个元素。如果元素是整数,则将其添加到结果数组中;如果元素是一个列表,则递归地遍历这个列表。此方法特别适用于处理复杂数据结构中的嵌套列表。 ... [详细]
author-avatar
小寒风
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有