算法科普:有趣的游程编码

简介: 在这个大数据时代,我们保存的数据量有时候往往是非常庞大的,存储它将会耗费非常多的内存,读取速度也相对减慢了。因此常常需要对数据进行压缩编码存储,等到要用到这个数据的时候再解压缩就行,这样不仅可以节约大量的存储空间,而且节省了系统读取和反应的时间。

原文链接

在这个大数据时代,我们保存的数据量有时候往往是非常庞大的,存储它将会耗费非常多的内存,读取速度也相对减慢了。

因此常常需要对数据进行压缩编码存储,等到要用到这个数据的时候再解压缩就行,这样不仅可以节约大量的存储空间,而且节省了系统读取和反应的时间。

栅格数据压缩编码的方法有很多种,包括链式编码、行程编码、块式编码和四叉树编码。今天我们就来讲一下行程编码(也叫游程编码)。

首先从一个简单的例子开始:编码一个在 5 * 5 方块上使用三种颜色绘制的图像。

image.png

图1

根据方块不同的颜色匹配不同的字母。这里使用 Y 代表黄色,使用 G 代表绿色,使用 B 代表蓝色。

那么,根据这样的规则,图 1 的图形编码就变成了 25 个字母,如图 2 所示。
image.png

图2

接下来,我们通过使用 游程编码 的方式来表示这个图像,以便使用 25 个字符以下的字符来表示。

游程编码是一种将代码和重复的次数作为一组来编码的方法。

例如,我们可以通过将第一个 “YYYY” 的部分表示未 “Y4”,这样就可以将其 缩短两个字符 。

按照这种操作,图 2 的 25 个字符就能缩短为 20 个字符了。
1.gif

图 3


这样,如果我们知道每行有 5 个方块,原始图像就可以从代码中提取出来了。这种还原的操作也就是我们俗称的 解压。

当然,游程编码也不是万能的,它也有它的适用性与局限性。
image.png

图 4


观察图 4 的图像与对应的代码,可以发现:虽然使用 游程编码 使得总体的字符数减少,但对于那些不具备相同颜色的部分,在进行游程编码后,字符数反而会增加。
image.png

图 5


特别的,如果对连续性极其差的数据进行游程编码,字符数不减反增:数据翻倍到 50 个字符了。

当然,对于具有连续性的数据进行游程编码,那压缩量就十分可观了。
image.png

图 6


因此,根据要编码的数据,游程编码可能具有压缩效果,也可能不具有压缩效果。

所以,对一定数量连续的数据使用游程编码才是正确的使用时机。

再举个例子,考虑一下在单色传单上使用游程编码。
4.gif

动图 7


如动图 7 所示,使用 W (White)和 B(Black)字母来表示每个方块。

按照这样的逻辑,一开始只需要 25 个字符就能表示完毕。

如果使用 游程编码,那么最终的表达结果是需要 26 个字符表示。所以,在这种情况下,使用 游程编码 是没有意义的。

但仔细观察,在黑白图像中仅仅使用了黑和白这两种颜色。因此,在连续的白色方块之后必定出现的是黑色方块。那么即使没有字母 W 和字母 B,依旧可以通过代码还原恢复图像。
image.png

图 8


如图 8 所示,通过省略字母 W 和字母 B,仅仅只需要 13 个字符就能表示图像,相对于之前的需要 26 个字符表示压缩了一半的大小。

当然,这样显示是有一个要求的,那就是 代码的第一个数字必须是白色方块的连续数。只有使用了这个规则,才能通过代码还原出之前的图像。
image.png

图 9


所以,对于图 9 这种开头是黑色方块的图像的代码,需要在代码的开头处添加 0 ,这样就也遵守了 代码的第一个数字必须是白色方块的连续数这条规则。

来源 | 五分钟学算法
作者 | 程序员吴师兄

相关文章
|
3月前
|
算法 5G vr&ar
基于1bitDAC的MU-MIMO的非线性预编码算法matlab性能仿真
在现代无线通信中,1-bit DAC的非线性预编码技术应用于MU-MIMO系统,旨在降低成本与能耗。本文采用MATLAB 2022a版本,深入探讨此技术,并通过算法运行效果图展示性能。核心代码支持中文注释与操作指导。理论部分包括信号量化、符号最大化准则,并对比ZF、WF、MRT及ADMM等算法,揭示了在1-bit量化条件下如何优化预编码以提升系统性能。
|
3月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
|
4月前
|
机器学习/深度学习 存储 算法
编码之舞:从算法到应用的探索之旅
在数字化时代的浪潮中,编程技术如同一种语言,连接着人类与机器。本文将带领读者踏上一场自数据结构基础至高级算法应用的探索旅程,通过实际案例分析,揭示算法在现代软件开发中的重要作用,并分享作者在编程实践中的心得体会,旨在为初学者和资深开发者提供有价值的参考与启示。
|
4月前
|
机器学习/深度学习 算法 计算机视觉
通过MATLAB分别对比二进制编码遗传优化算法和实数编码遗传优化算法
摘要: 使用MATLAB2022a对比了二进制编码与实数编码的遗传优化算法,关注最优适应度、平均适应度及运算效率。二进制编码适用于离散问题,解表示为二进制串;实数编码适用于连续问题,直接搜索连续空间。两种编码在初始化、适应度评估、选择、交叉和变异步骤类似,但实数编码可能需更复杂策略避免局部最优。选择编码方式取决于问题特性。
|
5月前
|
存储 算法
贪心算法的高逼格应用——Huffman编码
贪心算法的高逼格应用——Huffman编码
60 8
|
5月前
|
缓存 算法
基于机会网络编码(COPE)的卫星网络路由算法matlab仿真
**摘要:** 该程序实现了一个基于机会网络编码(COPE)的卫星网络路由算法,旨在提升无线网络的传输效率和吞吐量。在MATLAB2022a中测试,结果显示了不同数据流个数下的网络吞吐量。算法通过Dijkstra函数寻找路径,计算编码机会(Nab和Nx),并根据编码机会减少传输次数。当有编码机会时,中间节点执行编码和解码操作,优化传输路径。结果以图表形式展示,显示数据流与吞吐量的关系,并保存为`R0.mat`。COPE算法预测和利用编码机会,适应卫星网络的动态特性,提高数据传输的可靠性和效率。
|
5月前
|
算法 C++
【洛谷 P1090】[NOIP2004 提高组] 合并果子(贪心算法+哈夫曼编码+优先队列)
该编程题目要求设计算法,将不同种类的果子合并成一堆,使得消耗的体力最小。给定果子种类数`n`(1至10000)和每种果子的数量,需输出合并的最小体力值。使用优先队列(最小堆),每次取出两个数量最少的果子堆合并,并更新总体力消耗。样例输入为3种果子(1, 2, 9),输出最小体力耗费为15。提供的AC代码采用C++实现,通过优先队列优化合并顺序。
58 0
|
5月前
|
存储 算法 数据挖掘
【贪心算法经典应用】哈夫曼编码原理与算法详解 python
【贪心算法经典应用】哈夫曼编码原理与算法详解 python
|
6月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于有序抖动块截断编码的水印嵌入和提取算法matlab仿真
这是一个关于数字图像水印嵌入的算法介绍。使用MATLAB2022a,该算法基于DOTC,结合抖动和量化误差隐藏,确保水印的鲁棒性和隐蔽性。图像被分为N*N块,根据水印信号进行二值化处理,通过调整重建电平的奇偶性嵌入水印。水印提取是嵌入过程的逆操作,通过重建电平恢复隐藏的水印比特。提供的代码片段展示了从块处理、水印嵌入到噪声攻击模拟及水印提取的过程,还包括PSNR和NC的计算,用于评估水印在不同噪声水平下的性能。