用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网科技动向学人动向
关键字  范围   
 
两个老头儿写的神奇算法,统治了全世界!
作者:liuxin | 2024/4/23 10:50:01 | 浏览:1083 | 评论:0

作为普通人,你在浏览网页的时候,你并不会意识到,服务器发给你的网页,其实都是压缩过的。

如果你像程序员一样,在浏览器中按一下F12,就能找到这样的东西:

两个老头儿写的神奇算法,统治了全世界!


它的意思是:为了节省带宽提供网速,我(服务器)把内容用gzip做了压缩,你(浏览器)得解压缩一下才能看啊!

在HTTP压缩中,除了gzip之外,还有compress、deflate、br等算法,让人眼花缭乱。

但是,这些压缩算法,都有一个老祖宗:LZ算法。

LZ来自两个人的名称:Abraham Lempel,Jacob Ziv。

两个老头儿写的神奇算法,统治了全世界!


两个人于2023年相继去世,都很长寿,Lempel活了86岁,Ziv一个活了91岁。


01起源

数据压缩分为两种,一种是有损压缩,如MP3、JPEG,一些不重要的数据在压缩时会被删除。

另外一种是无损压缩,二进制位神奇的消失,文件显著变小,方便存储和传输。

1948年,香农创立了信息论以后,大家一直在折腾一件事情:如何找到最优编码,压缩一段信息。

香农和法诺率先出手,提出了香农-法诺编码。

两个老头儿写的神奇算法,统治了全世界!

它通过符号分组的方式,自顶向下构建了一个二叉树。

两个老头儿写的神奇算法,统治了全世界!


但是这种方式不是最优解,并且编码不是前缀码,容易产生歧义。

法诺后来在麻省理工教信息论时,给学生们提出了一个挑战:要么参加期末考试,要么改进现有的数据压缩算法。

一个叫霍夫曼的研究生不喜欢考试,决定走后一条路。

霍夫曼并不知道,就连大名鼎鼎的香农也在这个问题上苦苦挣扎。他研究了几个月,开发了多种方法,都没有用

就在他要放弃,把笔记扔到垃圾桶的那一刻,一个美妙而优雅的算法划过了他的脑海:按照字符出现的频率,从下往上构建二叉树,这就是著名的霍夫曼算法。

霍夫曼的算法被称为“最佳编码”,实现了两个目标:


(1)任何一个字符编码,都不是其他字符编码的前缀。

(2)信息编码的总长度最小。


霍夫曼算法虽然很好,但有个巨大的限制:需要先获得所有字符出现的概率,然后才能编码压缩,这在很多情况下是做不到的。

上世纪70年代,互联网出现以后,这个问题变得更为突出。

能不能实现一边读取数据,一边压缩?


02突破


以色列理工学院的Ziv和Lempel一起向这一问题发起了挑战。

两人是很好的搭档,Ziv擅长统计学和信息论,Lempel则擅长布尔代数和计算机科学。

两个老头儿写的神奇算法,统治了全世界!

1977年,他们俩都来到了贝尔实验室做学术休假。

学术休假又称为“知识人才休假”,每工作几年就有一段很长的假期(比如半年),这段假期里想干什么就干什么,还是带薪的。

大佬们的学术休假很有意思,比如Unix发明人Ken Thomson在休假时就回到了母校伯克利,把Unix传播到了那里,启发Bill Joy等人开发了BSD。

Ziv和Lempel也是这样,他们到美国贝尔实验室去学术休假,在“休假”期间合作发表了一篇论文:《顺序数据压缩的通用算法》,提出了基于“滑动窗口”的算法,它不直接考虑字符频率,而是寻找重复的数据块(如字符串、字节序列等)并引用这些数据块之前出现的位置。

两个老头儿写的神奇算法,统治了全世界!

这算法就是LZ77,它适用于任何类型的数据,不需要做预处理(统计字符出现的概率),只需要一次遍历就可以实现极高的压缩比。

第二年,他们再接再厉,改进了LZ77,变成了LZ78,能够从压缩数据中完美实现数据解压重构,并且比以往的算法效率更高。


03乱战


LZ算法这样的宝贝,居然停留在理论界好几年,没有大规模使用。

直到1984年,DEC公司的Terry  Welch在LZ基础上,创造了LZW算法,用到了Unix的compress程序中

伴随着Unix的广泛传播,LZ算法开始进入飞速发展的快车道。

但是,也进入了群雄并启的乱战时代。

1985年,Thom Henderson在BBS下载文件时,发现总得一个一个地下载,拨号上网太慢了,于是他写了一个叫做ARC的软件,可以将多个文件压缩成一个,这就方便多了。

1986年,Phillip  Katz发现了ARC,喜欢的同时又觉得这玩意儿压缩速度太慢,于是就卷起袖子把关键的压缩和解压缩用汇编重写,形成了PKARC,开始卖钱


两个老头儿写的神奇算法,统治了全世界!


两个老头儿写的神奇算法,统治了全世界!


Thom Henderson看到自己的生意被抢,一气之下把Phillip  Katz告上法庭,理由很充分:你PKARC中的注释、拼写错误都和我的ARC一样,你这是在抄袭!还有,我的ARC虽然是开源的,但是协议规定只能看,不能改!

最终ARC胜诉,Phillip  Katz赔了几万美元。

天才Phillip  Katz当然不服,他研究了LZ77算法和Huffman算法,将二者结合,创造了新的压缩算法(deflate)和新的文件格式(zip),以及新软件PKZIP。

两个老头儿写的神奇算法,统治了全世界!

PKZIP无论是在压缩比,还是在解压缩速度上都把ARC打得找不着北,迅速统治了DOS时代。

由于ZIP格式是公开的,开源界info-zip小组也发布了开源、免费的unzip和zip,实现了deflate算法。

随后,Jean-loup Gailly和 Mark Adler基于deflate又开发了著名的gzip(文件格式+实用程序),替换了Unix上的compress。


两个老头儿写的神奇算法,统治了全世界!


gzip就是在文章开头看到的那个HTTP压缩格式。

1991年,Nico Mak 觉得PKZIP的命令行实在是不爽,他就基于PKZIP开发了一个Winodws3.1的前端(后来用开源的info-zip替换了PKZIP),让大家可以用图形界面的方式来压缩文件,这就是著名的WinZip。

两个老头儿写的神奇算法,统治了全世界!

两个老头儿写的神奇算法,统治了全世界!


用户发现WinZip界面精美,操作友好,根本不用记忆那些烦人的参数,点几下鼠标就完成压缩了。

WinZip迅速占据了所有的PC,成为成为90年代最流行的共享软件之一。

不过WinZip再辉煌,毕竟是“寄生”在Windows平台上。

Windows出手,干脆把Zip的功能内置到了操作系统中,终结了一切。


两个老头儿写的神奇算法,统治了全世界!


04结语


从LZ77开始,到LZW,compress,Deflate,gzip ...... 无损压缩算法不断地修修补补,逐渐形成了一个庞大的家族,但是无论怎么改,它们的原理和思想都和最早的LZ算法没什么差别。

这些算法帮助我们压缩图像,压缩文本,压缩互联网传输的内容,成为我们日常生活中不可或缺的一部分。

毫不夸张地说,LZ算法和它的子孙们已经统治了全世界。

相关栏目:『学人动向
他,80后“三院”院士,他引超10万次,最新Nature Materials! 2024-06-10 [95]
汤涛反驳丘成桐,称中国数学人才培养相当成功,提及哪七位中国科大白银一代? 2024-06-10 [137]
博士生抓住同门往自己培养基里倒酒精,整个实验室被拖垮,自己延毕 2024-06-10 [67]
知名教授疯狂压榨学生,反遭自己导师吐槽:你当年周末也出去撩妹 ... 2024-06-07 [121]
博士生唯一一作发顶刊!与导师约定:发表前严守秘密 2024-06-07 [88]
大学教授实验室“制冰毒”被捕,辩称只为给学生科普制毒,结果被判无罪... 2024-06-07 [83]
清华教授:学术研讨会,学术最不重要 2024-06-07 [145]
平均两三天发表一篇论文,这位高产学者惹了众怒 2024-06-04 [180]
从数学到哲学,王浩的爱智之旅 2024-06-04 [180]
中国最年轻女院士!38岁当选,拿奖到手软,却因太年轻遭到质疑... 2024-06-04 [244]
相关栏目更多文章
最新图文:
:中国336个国家重点实验室布局 :中澳政府联合出手打击洗钱和逃税漏税 大量中国居民海外账户遭冻结 :摄影师苏唐诗与寂寞百年的故宫对话6年,3万张照片美伦美奂 :大数据分析图解:2019中国企业500强 张梦然:英国惠康桑格研究所:人体内的微生物与出生方式有关 :美众议院将调查华裔部长赵小兰“利用职权为家族谋利“ :UCLA CCS 2019 Fall Quarter Lecture Series Overview 谭晶晶:美国科技界高度关注中国科技创新进展
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2024 ScholarsUpdate.com. All Rights Reserved.