第三章:数字魔法

本文与前期推送“你真的理解数码技术吗?”“字节的秘密”是同一系列。

3.1压缩魔法

在数码世界中,容量和速度总是紧缺资源,我们总是希望能用尽量少的字节,装下更多的内容;我们的硬盘总是不够用;我们的网络总是不够快。这一切,都需要使用一些数字魔法来帮助我们——压缩算法。

3.1.1通用压缩算法原理

如何用尽量少的空间来存放尽量多的信息,这个问题一直是所有软件工程师都希望解决的。因此,首先有一些通用的压缩方法被提出来,虽然这些算法被应用的非常广泛,但是其原理确实非常简单的。我们常用的压缩软件,比如ZIP/RAR都会用到;我们上网的时候,传输的数据也大多数都经过压缩。

第一个要介绍的压缩方法叫RLF,说起来也很简单,其实就针对那些“连续重复”的信息做压缩。比方说有一串数字1,2,3,4,4,4,4,4,4,5,如果要压缩它,最容易发现的是这串数字中的数字4重复了很多遍,因此我们可以用0,4,6这三个数字来代表4,4,4,4,4,4,这里的0,4,6,表示的意思是:0-从这里开始有重复数字;4-这个是重复的数字;6-重复了6次。这样压缩之后的数字就是1,2,3,0,4,6,5这样一串数字。从10个数字就压缩成了7个数字,如果重复的内容越长,压缩率越高。这种依赖连续重复的算法是不是很简单呢?

第二个要介绍的方法叫哈夫曼算法,这个算法简单来说,就是查字典。举个例子,我如果要压缩一片文章,那么我可以找一本《现代汉语词典》,然后把文章中的每个词,都改写成它在《现代汉语词典》中的序号,最后改写完,把词典和文章一起打包就可以了。这种算法在我们的软件中使用的非常广泛,但是也有很大的缺点,就是那个压缩的词典可能会很大,因为文章中可能重复的词汇只有2处,但就需要占用一个词典中的条目,在压缩和解压的过程中,查询一个巨大的词典很耗费时间。

由于哈夫曼算法有上面的缺点,人们发明了另外一种算法,叫LZ77,这种算法改进了哈夫曼算法,它并不把整个压缩内容的词汇都编到一个词典里面。而是使用一段固定长度的词典,这段词典的内容就是刚刚处理被压缩后的原文。比如我们要压缩abcdbbccaa abaeaaabaee这样一串数字,前面的abcdbbccaa是已经被压缩处理过的文字,它们会用来作为处理后面字符的字典。当我们压缩abaeaaabaee的时候,我们发现第一个和第二字母ab是可以从字典abcdbbccaa中匹配到头两个字符的,所以就可以记录成:0,2,a。意思是匹配了字典的第0个字符后2个字符,匹配完的下个字符是a。后续的压缩就是不断的移动压缩的位置和字典的位置,就能形成一个压缩串,这个串既带了表示重复字符的数字,也包含了字典的内容,而字典则是固定长度的。这种算法的好处是压缩和解压的速度都比较快,如果要增加压缩比,就要增加字典的长度就可以了,是一种可以调节压缩比的算法。

通用压缩算法基本上都是一个原理,就是减少重复部分。思想其实是非常简单的,但是为了更好的识别出重复的部分,以及减少压缩、解压时间的消耗,使用了很多复杂的方法。

3.1.2图形压缩

图形文件一直是数码产品中占用容量的大户。为了降低图像信息的占用空间,人们发明了很多种方法。我们使用图像文件时,会发现有JPG/GIF/BMP/PNG/TIFF等很多种格式,这些格式往往都是对图像进行压缩的不同方案。

图像压缩技术一般分为两类,一类是有损压缩,原理是利用人眼不够犀利的特性,把图像中不太容易被关注的部分的信息去掉。一类是无损压缩,原理是针对图像的数据特点,来对数字信息进行压缩。一般来说有损压缩会损失画质,但是却能大幅度降低图像占用的空间;无损压缩对于某些特定图像的压缩效果可能很好,比如卡通画,但是对于照片这种没有什么特点的图像压缩效果可能很差。

先说说有损压缩,最简单的做法,就是把附近几个差不多的颜色的点,全部改成同样一个颜色的点。这样本来需要多个不同数字来表示不同的颜色,就全部变成了一个颜色,这样重复的数字就变多了,容量自然就能变小了。——这个只是个最简单的思路,真正的有损压缩算法比如JPEG,并不是简单的抹平成一种颜色,而是通过一种算法,来修改靠近的一小片8x8个像素的图像的颜色,让这些颜色数值的重复率变高而得到的。

[JPG高度压缩后的图像]

下面说说无损压缩。无损压缩其中一个最简单的做法就是使用“调色板”,思路和通用压缩算法中的“查字典”是一样的。也就是把整个图像中所有的颜色都抽取出来编上号,然后重复颜色的点就可以用这个简单的编号来代替,而不需要具体记录红蓝绿三种色点的深浅了。这种算法对于颜色简单的图像非常有效,比如卡通画往往最大色彩只有256种,这样调色板之需要256个数字,也就是一个字节就能装下了。每个点记录色彩从12个字节直接降到了1个字节。容量一下就减少了十二分一。

[一副图像的颜色表]

3.1.3视频压缩

说到视频压缩,大家最熟悉的就是MPEG这个名次,我们以前看的VCD就是MPEG算法做压缩的。那么他的原理是什么呢?说起来也非常简单。其实就是2个方面的压缩:

一个是所谓空间相关性:视频是由很多帧画面组成的一个动画片,每一帧画面里面,每一行之间的图像,都有一定的重复,所以对一个单独的画面,我们可以发现大量的靠近的、重复内容的点,这些重复的内容可以用来压缩。这和图像压缩的原理是一样的。

另外一个是所谓时间相关性:我们看的画面,每一帧之间变化的部分其实往往不是那么大,比如一个人说话的视频,大部分都是嘴巴部分的画面在动,其他部分的不动,我们就可以只记录那些有变化的部分,而不需要把每帧画面都完整的记录下来,这也可以大大减少需要记录的数据量。我们在看VCD的时候,有时候会卡顿,看到一堆马赛克。这个时候如果细心观察,你会发现,马赛克的位置往往是画面有变化的部位,这就是压缩算法只记录了变化部分的一个证明啦。

3.2加密魔法

加密这个行当,在计算机诞生之前就已经存在了数千年。第一代的计算机,就是为了破解密码而产生的。二战时期英国海军部的情报部门,使用计算机破解了号称无法破解的德军密码机,取得了无数的战果,甚至日本海军头子山本五十六大将,就是因为密码电报被破解而被击毙。现代,加密算法又成为了互联网世界中安全的基石,可以说是最重要的算法之一。

3.2.1福尔摩斯和跳舞小人

《福尔摩斯》小说中曾经提到一个案子,内容说的是,有一天,一个人发现自己家里,到处被画上了很多跳舞小人,看的他毛骨悚然,于是请来了福尔摩斯破案。最后福尔摩斯看出了这些跳舞小人,其实是一段加密后的文字,每个小人都代表着一个字母。当福尔摩斯破解了这些小人的含义后,这些图画最后就能被解读成一段文字了。

其实这就是一种最简单的加密方法,又叫做罗马法加密。具体做法就是用一张不为人知的字母表(密码表),去改写现成的文字。由于拉丁文文字都是拼音文字,所以一张不大的密码表就可以用来改写任意的文字。罗马人是最早使用这种方法来加密军事情报的,他们的密码表当然不是这些怪模怪样的小人,而是一个打乱了顺序的罗马字母表。

举个例子,比如密码表中A对应正常字母表中F的位置,那么所有明文中的F都要写成A。解密的时候,再把密文中的A改写成F就可以看了。但是这种加密方法也很容易被破解,破解的方法叫做“词频分析法”,原理就是:在英文(或者其他拉丁语言)中,字母表中的各个字母的,在正常文章中,出现的频率是固定,比如大家都会发现字母S的频率出现很高,而Z的频率很低,因此我们可以通过统计密文中所有字符的频率,然后比对正常的字母的频率,从而猜出哪个密文字符是代表哪个明文字符。

为了改变加密字符的频率,后来的德国人发明了一种新的加密方法,就是动态的密码表,原理就是,每加密一个字符,密码表的顺序都会产生变化,一般变化是把密码表的顺序单向的增加。这样加密出来的每个字符,就算明文是一样的,其密文都可能不一样的。这种密文就无法简单的进行频率统计了。更有甚者还加上2套密码表嵌套使用,进一步打乱了字符的出现频率。

3.2.2异或

我们知道,计算机处理的是数字信息,但是说到加密,计算机又是如何使用一段“密码表”来加密一段明文的呢?其实也非常简单,就是用到“异或”这个二进制算法。简单来说,“异或”的运算规则就是:对于第一个数来说,如果碰到第二个数字0就不变,碰到1就翻转。

异或用来做加密非常简单,如果把运算的一个数作为明文,另外一个数作为密码表,那么异或的运算结果就是密文,反过来则是解密的过程。我们可以把明文切成和密码表一样长度的数字串,然后一段段和密码表做异或操作,就能得到加密串了。当然,这个过程中,你还可以加入如修改密码表(也是一串数字)的字符顺序这种变化,就能得到类似德国人的循环加密机的效果。

由于这种加密算法,在加密和解密的时候,使用的是同一份密码表,所以被叫做对称加密法,英文缩写叫DES。这也是计算机中最常见的一种加密方法。

3.2.3不对称加密

对称加密算法有一个缺点,就是密码表一旦泄露,获得密码表的人就可以使用这份密码表,冒充加密人来制造、串改密文。在互联网世界里,串改的数据往往比泄露的数据更可怕,这意味着可以冒充别人的身份。

因此,人们又发明出了“不对称加密”的算法。这种算法的密码表是分两套的,一份叫“公钥”,一份叫“私钥”。其中“公钥”是用来解密的,而“私钥”是用来加密的。你通过“公钥”是很难猜测出“私钥”的。这样,一份用来解密的公钥,就能成为证明这份密文出处的证明。这也是现代互联网中应用最广的一种的加密算法,英文叫做RSA加密。

当我们需要加密传输的时候,我们使用不同的密码表来进行加解密,可以让密文在解密端是安全的,因为公钥被知道的话,也仅仅是能解读内容,而不能生成内容。比如我们需要远程控制一台计算机,我们发出的指令就无法被伪造和串改,这对于互联网远程安全有至关重要的作用。

3.3其他数字魔法

3.3.1数字隐身术:隐写

我们在一些电视剧里面,往往会看到一些关于黑客的描述,比如一个普通的视频文件,经过特殊处理后,居然能出现一段隐藏的文字。就好像古老的谍战电影中,情报人员用特殊墨水来写信,需要用特殊的方法,比如泡水,才能看到内容。其实这种把信息隐藏起来的技术,在数码技术中,是非常容易做到的。最简单的是利用一种数字编码格式的去隐藏另外一种数字编码。比如我们可以把一段TXT文本编码数字,加到一张图片里面。如果这个图片的解像度非常高,这段TXT文本的数字,只是很不起眼的几个像素点而已。或者我们可以把一段文本信息的数字,变成某个视频点出现的频率,在一段视频里面,特定位置的点的变化频率更是难以用肉眼看到。可以说只要你了解一些数字编码规则,你都可以想办法隐藏一些信息。

3.3.2数字封印术:校验

在数字技术中,我们还可以通过一些算法,来检查数据在传输、存储的过程中有没有出错。最普通的做法就是所谓奇偶校验。比如我们在磁盘存放了0100 1100八个位的数字,我们可以发现1的个数是3个,是奇数,我们在记录0100 1100 1这九个数字到磁盘。最后的1表示前面八个位中,1的格式是奇数。如果我们读取的时候读到0100 1000 1这九个数字,发现前八位中1只有2个,是偶数,和最后的1所代表的含义对不上,就知道出错了,可能需要重新读取一次,或者提示用户磁盘坏了。

另外一种校验算法,也可以用来快速的判断一段数据是否相同。它就是大名鼎鼎的md5算法。这种算法可以把任意长度的数字,运算出固定的一串16字节长的一个数字。这个16字节的数字,代表了被运算的原文的摘要信息,如果原文有一个位不一样,这个运算的结果,都会有非常大的差别(一半以上的位翻转)。我们在下载了一个大文件之后,往往可以用md5来校验一下,和原来的文件的md5运算结果是否一致,就知道这个文件有没有在下载过程中出错了。一般来说,我们很难通过修改预算的原文,来凑出一个自己想要的md5运算结果,所以很长一段时间内md5被认为是“单向”的算法。但是2009年谢涛和冯登国仅用了220.96的碰撞算法复杂度,破解了MD5的碰撞抵抗,该攻击在普通计算机上运行只需要数秒钟。

3.3.3无限变大术:矢量图

一般来说,我们在存储图像的时候,都把图像分成很多个点,然后好像十字绣一样,拼成一个大的图像。但是这种图像在放大到一定程度之后,就看到一个个像素点,显得特别粗糙。因此有一些人另辟蹊径,他们在存储图像的时候,并不是拆分像素点,而是把图像中的线条,用数学公式来表达,创造出一种无论如何放大都不会“失真”的图像格式——矢量图格式。这种格式还有另外一个有点,就是容量大小也和解像度无关。不像一般的点阵图,解像度越大往往占用容量越大,而矢量图的容量大小仅仅和图像的线条复杂度有关,和解像度大小无关。因此在互联网上,矢量图和矢量动画更容易被下载,这也导致了FLASH格式的流行。

我们知道,数学函数是可以用图像来表达的,不同的函数可以构成不同弧度和变化的函数图像,而函数的内容本身,又可以控制函数图像的特征。因此,我们可以反过来,把图像“看成”是由一系列函数图像构成的,这样我们记录下这些函数,就能记录下图像本身了。而且由于函数本身和像素点无关,不过如何放大缩小(输入参数如何变化),图形都不会变化。

[鹅的矢量图]

矢量图被广泛用于游戏、卡通片、LOGO设计、印刷出版等领域,由于不受分辨率影响,矢量图可以被完美的输出到各种媒介上。但是矢量图也有缺点,如果图像的轮廓线条非常复杂,比如照片,矢量图就需要大量复杂的数据结构才能表达,这导致了计算机处理能力的沉重负载。而且矢量图很难从类似照相机、扫描仪这类采集设备获得,基本上需要人工描画,这也让这种格式的图形难以被简单的使用。

感谢大家的阅读,如觉得此文对你有那么一丁点的作用,麻烦动动手指转发或分享至朋友圈。如有不同意见,欢迎后台留言探讨。

原文发布于微信公众号 - 韩大(handa1740168)

原文发表时间:2016-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吴伟祥

学习数据结构的原因&方法 原

541
来自专栏小詹同学

Leetcode打卡 | No.011 盛最多水的容器

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1142
来自专栏desperate633

LintCode 不同的路径题目分析代码

有一个机器人的位于一个M×N个网格左上角(下图中标记为'Start')。 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角(下图中标记为'F...

402
来自专栏Script Boy (CN-SIMO)

魔法少女【动态规划问题】——NYOJ1204

912
来自专栏我有一个梦想

Python 项目实践二(生成数据)第二篇

接着上节继续学习,在本节中,我们将使用Python来生成随机漫步数据,再使用matplotlib以引人瞩目的方式将这些数据呈现出来。随机漫步是这样行走得到的路径...

1827
来自专栏北京马哥教育

黑科技 | 用Python只花十五分钟完成正则表达式五天任务量

数据清理是很多机器学习任务上我们遇到的首要问题。本文介绍的 FastText 是一个开源 Python 库,可用于快速进行大规模语料库的文本搜索与替换。该项目的...

3339
来自专栏机器之心

资源 | 十五分钟完成Regex五天任务:FastText,语料库数据快速清理利器

40811
来自专栏程序员的诗和远方

Canvas基础-粒子动画Part1

网页上各种酷炫的粒子动画看的人眼花缭乱,实际上原理却非常简单。 获取像素信息 首先我们需要画张图到Canvas上,这里因为我懒的扣图(实际上是不会),就找...

3016
来自专栏CSDN技术头条

大数据并行计算利器之MPI/OpenMP

1 背景 图像连通域标记算法是从一幅栅格图像(通常为二值图像)中,将互相邻接(4邻接或8邻接)的具有非背景值的像素集合提取出来,为不同的连通域填入数字标记,并且...

2286
来自专栏计算机视觉与深度学习基础

poj,zoj题目分类

ZOJ题目分类 初学者题: 1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241...

1959

扫码关注云+社区