计算机算法:数据压缩之前缀编码(5)

概述

前缀编码,有时也被称为前向编码,是另一个通过移除冗余数据来降低数据量的算法。思想非常简单,但算法实现比较困难。要了解原因,首先我们来看一看它的原理。

请看下面的字典。

为了不使用纯文本保存这些单词或者在网络上传输,我们可以用前缀编码进行压缩(编码)。

很明显,每一个单词都以表中的第一个单词“use”为前缀。所以我们很容易将它们压缩成下面的数组。

显然这并不是最佳的压缩结果,在不仅仅使用第一个词作为前缀的情况下,我们可以更进一步压缩。

此时的压缩更好,好消息是解码是一个相对简单的过程。但棘手的部分在于压缩本身。问题是选择合适的前缀非常困难。第一个例程的前缀选择很简单,但事实上,大多时候数据很混乱。的确,对于随机产生的数据压缩过程将非常困难,算法过程不仅很慢,而且难以实现。

好的方面是,如果我们事先知道数据的格式,该算法可以用于多种情况。那么,让我们看看下面三个例子,该算法可能会很方便。

应用

以下是三个前缀编码的例子。前面我说随机数据的压缩过程会很难,如果你事先知道输入数据的格式,这将会是一个很好的练习。

日期和时间前缀

我们通常会忽略年份的前两个数字,例如我们通常不会写1995或1996,而是使用更短的——‘95’和‘96’。这样年份就被编码成更短的字符串。

问题在于输入流发生很小的变动,解码就会出错。如果我们加上21世纪的年份,我们将失去数据的唯一性。

此时,解码器肯会将最后两个数值解码成(1911, 1912),因为“19”被认为是前缀。所以,我们事先必须知道前缀与每一个数值绝对平等。如果没有编码格式,必须不同。例如我们可以使用一些特殊标识和前缀一起编码。

一旦解码器读到#字符,它就知道下面的数为前缀。

事实上,这种方法可用于日期和时间格式的编码。假设我们有一些日期时间值,而且我们知道所有数据都是在同一天。

显然,我们可以忽略这些字符串的时间部分,仅发送(保存)时间。当然,我们必须确定所有的这些数值都是在同一天。如果不是,我们可以使用上例中的方法。

电话号码

电话号码是前缀编码的典型应用。不仅仅是国际代码,移动网络运营商的电话号码也使用前缀编码。如果我们要传输电话号码,假设是英国的,我们可以用一些更短的东西替换开头的“+44”。

如果你要给移动设备编写电话簿,你可以通过前缀编码压缩数据,节省部分空间,这样用户将拥有更多空间,也可以在手机上存储更多电话号码。

电话号码前缀也适用于数据库标准化。这样你可以将它们存储在单独的数据库表中,不用电话簿中唯一的号码。

地理坐标

对于我之前帖子中使用的例子,可以在一定范围内去掉通用前缀来发送地理坐标。的确,在必须传送大量坐标到地图应用时,你可以预期这些标记在一定范围内彼此间相当靠近。

在一定范围内,可以预期这些标记都有相同的前缀。

那些点的坐标有共同的前缀,就像下面地铁站的例子一样。

我们可以发现所有的地理坐标点有相同的前缀(40.76x, -73.98x),所以我们只需要发送一次前缀。

以上是前缀编码的三个例子,该算法在传输均匀数据是非常有用。

后缀编码

后缀编码和前缀编码几乎相同,区别在于编码重复后缀。如下例,后缀编码替换最后重复的后缀,这非常有用。

或者公司名称。

这里我们可以使用一些其他更短的东西来替换“Inc”。

1 收藏 1 评论

关于作者:汤晓

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

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部