热门标签 | 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


推荐阅读
  • Redis哈希数据结构入门指南
    Redis的哈希数据结构与Java中的HashMap类似,采用数组加链表的方式实现。数组用于存储哈希值的位置,而链表则用于处理哈希冲突的情况。此外,Redis的哈希数据结构还支持高效的字段操作和内存优化,适用于多种应用场景,如缓存和会话管理。 ... [详细]
  • 在 Angular Google Maps 中实现图片嵌入信息窗口的功能,可以通过使用 `@agm/core` 库来实现。该库提供了丰富的 API 和组件,使得开发者可以轻松地在地图上的信息窗口中嵌入图片。本文将详细介绍如何配置和使用这些组件,以实现动态加载和显示图片的功能。此外,还将探讨一些常见的问题和解决方案,帮助开发者更好地集成这一功能。 ... [详细]
  • 探索聚类分析中的K-Means与DBSCAN算法及其应用
    聚类分析是一种用于解决样本或特征分类问题的统计分析方法,也是数据挖掘领域的重要算法之一。本文主要探讨了K-Means和DBSCAN两种聚类算法的原理及其应用场景。K-Means算法通过迭代优化簇中心来实现数据点的划分,适用于球形分布的数据集;而DBSCAN算法则基于密度进行聚类,能够有效识别任意形状的簇,并且对噪声数据具有较好的鲁棒性。通过对这两种算法的对比分析,本文旨在为实际应用中选择合适的聚类方法提供参考。 ... [详细]
  • 在CodeIgniter框架中集成新库文件的过程中,我遇到了一些困惑。具体来说,在跟随nettuts的认证教程时,对于在Welcome控制器中添加的构造函数代码,特别是关于Session的验证部分,我感到不太理解。这部分内容涉及如何确保Session已经初始化并具备相应的功能,这对于实现用户认证至关重要。为了更好地掌握这一知识点,我计划深入研究CodeIgniter的官方文档,并参考更多相关资源,以确保能够正确地集成和使用新库文件。 ... [详细]
  • PHP 数组逆序排列方法及常用排序函数详解 ... [详细]
  • 在GitHub上克隆vue-element-admin项目时遇到依赖安装错误
    在 GitHub 上克隆 vue-element-admin 项目后,使用 `npm install` 安装依赖时遇到了未知的 Git 错误。具体错误信息为 `npm ERR! code 128`,提示命令执行失败。这可能是由于网络问题、Git 配置不正确或某些依赖包的仓库地址无效导致的。建议检查网络连接、更新 Git 版本并确保所有依赖项的 URL 正确无误。 ... [详细]
  • 本文深入解析了计算力扣平台上汉明距离问题的官方解法,并通过优化算法提高了计算效率。具体而言,我们详细探讨了如何利用位运算技巧来高效计算数组中所有数对之间的汉明距离,从而在时间和空间复杂度上实现了显著改进。通过实例代码演示,使读者能够更直观地理解这一优化方法。 ... [详细]
  • 设计模式详解:模板方法模式的应用与实现
    模板方法模式是一种行为设计模式,通过定义一个操作中的算法骨架,将具体步骤的实现延迟到子类中。本文详细解析了模板方法模式的类图结构、实现方式以及挂钩机制,并结合实际案例进行了深入探讨。此外,文章还提供了丰富的参考资料,帮助读者更好地理解和应用这一设计模式。对于手机用户,建议横屏阅读以获得更佳的阅读体验。 ... [详细]
  • 计算机图形学基础:辐照度学原理与应用综述
    辐照度(irradiance)是指单位面积上接收到的电磁辐射功率,可视为入射点处的能量密度。在计算机图形学领域,辐照度计算是确定场景中每个位置光照效果的关键步骤。通过对辐照度的精确建模,可以实现更加逼真的光照渲染,提升视觉效果的真实感和沉浸感。本文综述了辐照度的基本原理及其在计算机图形学中的多种应用,探讨了当前研究的热点和技术挑战。 ... [详细]
  • 在PHP的设计中,预定义了9个超级全局变量、8个魔术变量和13个魔术函数,这些变量和函数无需声明即可在脚本的任意位置使用。这些特性在PHP开发中极为常见,能够显著提升开发效率和代码的灵活性。相比之下,Java并没有类似的内置机制,但通过其他方式如上下文对象和反射机制,也可以实现类似的功能。本文将详细探讨这两种语言中这些特殊变量和函数的使用方法及其应用场景。 ... [详细]
  • 本文探讨了基于点集估算图像区域的Alpha形状算法在Python中的应用。通过改进传统的Delaunay三角剖分方法,该算法能够生成更加灵活和精确的形状轮廓,避免了单纯使用Delaunay三角剖分时可能出现的过大三角形问题。这种“模糊Delaunay三角剖分”技术不仅提高了形状的准确性,还增强了对复杂图像区域的适应能力。 ... [详细]
  • 在晴朗天气条件下,对一种神奇的魔法现象进行了深入分析。该题目为原创,基准时间限制为1秒,空间限制为131072KB,分值20,属于3级难度的算法题。研究发现,这种魔法现象在阳光明媚的环境中表现得尤为显著,进一步探讨了其背后的科学原理和技术实现方法。 ... [详细]
  • React 实现 Post 请求下载 PDF 文件的解决方案
    在 React 应用中实现通过 POST 请求下载 PDF 文件的功能,本文提供了完整的代码示例。具体实现包括设置状态以显示加载提示,并通过控制台日志记录下载索引,确保请求的正确性和用户体验。此外,还详细介绍了如何处理响应流并将其转换为可下载的 PDF 文件,适用于需要安全传输数据的场景。 ... [详细]
  • 公司计划部署邮件服务器,考虑到已有域名,决定自行搭建内部邮件服务器。经过综合考量,最终选择在Linux环境中进行搭建,并记录了相关配置和实践过程。本文将详细介绍Postfix的基本设置步骤和实践经验,帮助读者快速掌握邮件服务器的搭建方法。 ... [详细]
  • 深入探索Node.js新框架:Nest.js第六篇
    在本文中,我们将深入探讨Node.js的新框架Nest.js,并通过一个完整的示例来展示其强大功能。我们将使用多个装饰器创建一个基本控制器,该控制器提供了多种方法来访问和操作内部数据,涵盖了常见的CRUD操作。此外,我们还将详细介绍Nest.js的核心概念和最佳实践,帮助读者更好地理解和应用这一现代框架。 ... [详细]
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社区 版权所有