计算机算法:数据压缩之相对编码(4)

概述

相对编码是另一种数据压缩算法。游程编码位图编码以及图编码和模式替换都基于减少重复数据实现,而相对编码目标略有不同。的确,游程编码要查找连续重复出现的元素,模式替换和位图编码要“映射”重复出现的位置。

这些算法的唯一问题在于输入数据并非总是由重复元素组成。很明显,如果输入数据流包含许多重复元素,必定能减少。然而,这并不意味着没有重复元素的数据就不能压缩。这取决于数据。假设我们要压缩的数据如下。

难以想象这个数据流能被压缩。压缩字母时可能存在同样的问题。的确,字母是构成单词的基础,是构成单词的最小单元而且很难再压缩。

幸运的是,事实并非如此。相对编码可以处理非重复数据。让我们看看下面的输入流——一段给定的年份(90年的)。

这里有39个字符,我们能够压缩它们。我们通常使用的方法是去掉前面的“19”。

现在我们得到一个更短的字符串,但在保留第一个年份的基础上可以更进一步的压缩。其余的年份均相对于该年份。

此时传输的数据量减少了很多(从39降至16——超过50%)。然而,我们首先需要考虑一些问题,因为数据流的格式不会总是如此巧合。下面字符流会怎样?

我们看到数值100在区间的中间,使用该值作为相对编码的基准很方便。那么上面的数据流就变成如下:

问题在于决定哪一个数值作为基准值并不容易。如果数据以不同方式排列会怎样。

此时,数值“100”不能作为基准值,因为以该值为基准将得到如下结果:

对某基准值附近的相对值分组将会更加方便。

然而,找出基准值并不那么容易。编码格式也并不那么重要。但是下面提到的这种情况,这种编码却很有用。

实现

该算法的实现取决于特定的任务和数据流格式。假设我们要使用JSON从web服务器传输年份数据流到浏览器,下面是一段简单的PHP片段。

应用

该算法在很多情况都很有效,以下是其中一例。网络上有很多地图应用。例如谷歌地图雅虎地图必应地图就是非常有名的应用,同时也有非常有用的开源项目OpenStreetMap。成千上万的网站使用这些应用。

典型的使用案例是使用JSON从服务器传输大量地理坐标到浏览器。的确,地球上任何地理坐标点都相对于非洲西海岸附近的(0,0)点而言,在一定范围内,当有大量标记时,我们可以使用相对编码来传输信息。

例如,下图为标识了一些点的旧金山地图。它们的坐标都是相对于地球的(0,0)点而言。

地图标记相对于地球的(0,0)点而言,有时没什么效果。

更加有效方式是相对市中心对那些标记进行编码,这样可以节省空间。

在一定范围内对地图标记使用相对编码非常有效!

然而,这种压缩类型可能会非常棘手,比如拖动地图和更新坐标数组时。此外,如果需要加载多个城市,我们必须对坐标进行分组。所以,在实现时必须谨慎。但另一方面,这也会很有用——例如在初始化加载地图时可以减少数据量,缩短加载时间。

使用相对编码,我们只要保存相对基准值(数据)的偏移量——就像版本控制系统一样,这样可以降低传输和加载的数据。这里有一个图形的例子。第一种情况下,我们看到以下图标中的每一项都是单独保存。它与相邻元素无关,可以独立与其他元素存在。

我们能只保存第一个元素,其余元素都相对与该元素,如下图标所示。

收藏 评论

关于作者:汤晓

(新浪微博:<a href="http://weibo.com/u/2151517721">@ashiontang</a>) 个人主页 · 我的文章 · 10

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部