字幕组成品列表（Beta）
  • 写在前面
  • Android 平台
    • Game On! 游戏开发系列 - 031
      • Pie Noon - 1503060393
      • The Death of Base Game Activity - 1504030543
      • Surviving OpenGL Context Loss - 1504030546
      • WebP for Game Devs - 1504030547
      • Saved Games In-Depth (Part 1) - 1504070556
      • Saved Games In-Depth (Part 2) - 1504030548
      • Smaller Flipbook Textures with CRABBY - 1504030544
      • Google Tag Manager - 1504030545
      • Flatbuffers - 1505050794
      • Achievement Point Pointers - 1505050796
      • Frequency Scaling - 1505050797
      • Meet the Management APIs - 1501140367
      • Y U Ship Broken Games - 1505050795
    • Android 性能优化 - 088
      • Garbage Collection in Android - 1503170425
      • Performance Cost of Memory Leaks - 1503170424
      • Rendering Performance 101 - 1501130351
      • Understanding Overdraw - 1501130352
      • Understanding VSYNC - 1501130353
      • Tool - Profile GPU Rendering - 1501130354
      • Why 60fps? - 1501130355
      • Android UI and the GPU - 1501130356
      • Invalidations, Layouts, and Performance - 1501130357
      • Overdraw, Cliprect, QuickReject - 1501130358
      • Tool - Memory Monitor - 1501130363
      • Battery Performance 101 - 1501130364
      • Understanding Battery Drain on Android - 1501130365
      • Battery Drain and WakeLocks - 1501130366
      • Memory Performance 101 - 1504170661
    • I/O 2014 Android 开发专题 - 089
      • Activity Transitions - 1504020505
      • Building Apps For Android TV - 1504020520
      • Building great Android media experiences - 1504020510
      • Building a quality app from start to finish - 1504020515
      • App Indexing API - 1504020507
      • What's new in WebView - 1504010484
      • Bluetooth Low Energy - 1504010486
      • Building impressive Android media experiences - 1504010493
      • The next Generation of Authentication - 1504020497
      • Don't Alpha That Pixel! - 1504020523
      • NFC + HCE Your phone in an interactive world - 1504020509
      • Demystifying encodes and decodes of WebM - 1504020521
      • Google Cloud Messaging - 1504020524
      • Getting your Game on the Big Screen - 1504020518
      • I hear you like realtime memes - 1504020511
      • Offerize your App - 1504020506
      • Using the Android Job Scheduler - 1504020504
      • From Holo to Material - 1504020526
      • Under the Hood of Android Auto - 1504020501
      • Isolation for Android App Developers - 1504020498
      • Android Work - 1504010496
      • ExoPlayer: Adaptive video streaming on Android - 1504010489
      • Sample rates and resampling: Why can't we all just agree? - 1504010488
      • Drive Android API - 1504010485
    • Android Studio - 004
      • Layout Editor (Ep 3, Android Studio) - 1503290479
      • Introducing Gradle (Ep 2, Android Studio) - 1503170426
    • I/O 2014 Android 分发主题 - 091
      • Introduction to Google Play - 1504030534
      • Google Play: building your user community - 1504030535
      • Optimizing Apps for Education - 1504030536
      • Succeeding in Education Technology - 1504030530
      • Subscriptions Made Easy with Google Play - 1504030531
      • The world is your playground - go global with Google - 1504030533
      • Maximizing discoverability on Google Play - 1504030538
    • Android Auto - 003
      • Introduction to Android Auto - 1504130615
      • Android Auto Messaging - 1504130617
      • Android Auto Audio - 1504130616
    • Android Wear - 006
      • Designing for Android Wear - 1503210448
      • How We Customized Google Apps for Android Wear - 1503210450
      • Fullscreen apps for Android Wear - 1503210445
      • New Notification Features for Android Wear - 1503210446
      • Building Cloud-powered wearable Apps - 1503210449
      • An Introduction to Android Wear - 1503190435
      • Google I/O 2014 - Android Wear: The developer's perspective - 1503210442
      • Devoxx 2014 Interviews: Android Wear - 1503210440
      • DevBytes: Watch Faces for Android Wear - 1503210439
    • Android TV - 005
      • Using the Leanback library - 1504080588
      • Beach Buggy Racing Multiplayer with Nearby Connections (Play Services) - 1503060387
    • Android for Work - 106
      • Android for Work for Developers - 1503060390
      • App Configurations, Testing and Launchers - 1504110590
    • IO Bytes 2014 - Android - 066
      • Chrome Apps on Android and iOS - 1501080014
      • Perf Primer CPU, GPU and your Android game - 1501080017
  • Chrome 平台
    • IO Bytes 2014 - Chrome and Web - 067
      • Using the PageSpeed API - 1505070815
      • Fabulous Forms for the multi-device web - 1505070816
      • Testing multi-screen web pages - 1505070817
      • Responsive images today - 1505070819
      • Web Performance Testing at YouTube - 1505070828
      • Building sites for the multi-device web - 1505070820
      • Deep dive: Google Cloud Messaging for Chrome - 1505070827
  • Google 创业者资源
    • Coffee with a Googler - 012
      • Chat with Allen Huang of AndroidTV - 1503040384
      • Chat with Fred Chung about developer advocacy - 1503070395
      • Google Fit platform with Michelle Haq - 1503210443
      • Android Auto Product Manager Andrew Brenner - 1501120027
      • Chat with Francis Ma about Google Play services - 1501120028
    • Root Access For Startups - 077
      • What we learned building plug-ins for Android, with startup Magnet - 1503230453
      • How to use crowdfunding to your advantage, with startup Hale Devices - 1503280462
      • How to overcome customer objections when selling tech, with startup Guesswork - 1503280458
    • First Things First - 029
      • Getting started with Android: A crash-course in developing for Android - 1504120601
      • How to ask a question: conducting research for your startup - 1504120603
      • MVP Design Hacks: transform your hot idea into a validated prototype - 1504120602
      • Build something people want: Solving real problems - 1504120605
    • How I - 061
      • Use BigQuery to find my most valuable customers - 1504070573
      • Manage beta testing communities using Google Play - 1504070572
      • Use paper wireframing to build native prototypes - 1504070570
      • Used social media and $0 marketing to get 68 million users - 1504070568
      • Prep to fundraise with four questions - 1504070564
      • Validated my idea in 2 days (with no code) - 1504070562
      • Build open platforms on Android - 1504120596
      • Get cheap, automatic analytics for my business using BigQuery - 1504070571
      • Write press releases to get international media coverage - 1504070569
      • Test beta-product features using Google Apps - 1504070563
      • Use URL builder to measure ROI on social media - 1504070561
      • Use events to build DeadSocial's brand - 1504070557
      • Use BigQuery to visualize streaming data - 1503220452
      • Find, screen, and hire developers - 1503120406
      • Drive engagement with social challenges - 1504070558
  • 设计
    • DesignBytes - 017
      • Paper and Ink: The Materials that Matter - 1505050793
  • 云计算
    • DevBytes: Google Cloud Platform - 021
      • Powering the next killer app with the Google Cloud Platform - 1504210672
      • Introduction to Google Cloud Endpoints - 1504210675
      • The Beauty of Scale with Google Cloud Platform - 1504210678
    • Google Cloud Platform - Big Data - 105
      • GDELT & BigQuery: Understand the world - 1502200379
    • Uncategorized - 999
      • Introducing Google Cloud Platform Resources - 1501190370
  • Google 应用开发
    • Launchpad Online - 072
      • The Setup: Creating new apps using Google APIs - 1503190428
      • Listing your files in Google Drive - 1503190429
      • Customizing Google Analytics for your startup - 1503290473
      • The Launchpad Online series - 1503190427
      • Getting started with Google Analytics - 1503290472
      • Accessing Google Maps from a spreadsheet?!? - 1502220381
      • Change the world in 10 lines of code - 1503080398
    • Google Play Services - 054
      • Google Play services 6.1 - 1503290481
      • Google Play Services 7.0 - 1503200437
      • Google Play Services 6.5 - 1501080015
    • 谷歌地图 iOS SDK - 053
      • Maps Live: New Features in the Google Maps Mobile APIs for Android and iOS - 1504300777
    • Google 移动搜索开发 - 055
      • Is your app in the Google index? - 1504120598
      • Get more engaged users with Google Search for Developers - 1503070397
    • DevBytes: Google Cast - 020
      • Google Cast SDK for Android - 1504180666
      • Media Router Framework - Part 1 - Media Router API - 1504180667
      • Overview for Google Cast Receivers - 1504180664
      • Google Cast SDK for iOS - 1504180663
    • Getting Started with the Google Maps SDK for iOS - 035
      • Getting started with the Google Maps SDK for iOS, Part 1 - 1504270757
    • IO Bytes 2014 - Wearables - 070
      • Voice Driven GDK Glassware - 1505280836
    • Route 85 - 078
      • Introducing Route 85 - 1501120022
      • Quick Tip: Don't Default that Switch! - 1501190371
      • OpenInChrome on iOS, Part 1 - 1501120023
      • OpenInChrome on iOS, Part 2 - 1501120024
      • OpenInChrome on iOS, Part 3 - 1501120025
      • OpenInChrome on iOS, Part 4 - 1501120026
    • DevBytes 2014 - 019
      • Web Components - Template - 1505040789
      • Wearable DataLayer API - 1505050792
      • Using srcset for responsive images - 1505050790
      • The picture element for art direction - 1505050791
    • Uncategorized - 999
      • Sun Surveyor brings augmented reality to photographers using Google Maps APIs - 1504200668
      • Snappy travels with the Roads API - 1503060392
      • Easy Maps Apps in Java and Python - 1501140030
  • Google 广告平台
  • Polymer
    • Polycasts - 076
      • The Awesome Power of Auto-Binding Templates -- Polycasts #08 - 1502220382
      • Content Switcheroo with Core-Pages -- Polycasts #09 - 1502200380
      • Core Iconset -- Polycasts #02 - 1505040788
  • Web 平台
    • HTTP 203 - 062
      • Gotchas - 1501140368
      • Font Rendering - 1501080016
    • Web Components - 081
      • DevBytes: Web Components - Overview - 1504250709
  • 宣传视频
    • Uncategorized - 999
      • Google Developers - 1501150369
      • I/O Extended 2014 - Join me - 1502220383
  • Google 各类开发者会议
    • 2014 Chrome 开发者高峰会议 - 009
      • Keynote - Chrome Dev Summit 2014 (Darin Fisher) - 1503120407
      • TLS All the Things! - Security with Performance(Chris Palmer) - 1503140412
      • Let’s build some apps with Polymer!(Rob Dodson) - 1503150415
      • Day One Closing Remarks(Sundar Pichai) - 1503150417
      • Chrome Leadership panel - 1503160422
      • Fundamentals of Mobile Web Development(Matt Gaunt) - 1503150416
    • 2015 游戏开发者大会中 - 039
      • FlatBuffers - 1504150640
      • Games for Google Cast - 1504150637
      • Top 10 Things Android Game Developers Should Know v 3.0 - 1504150643
      • Automate Publishing for Google Play APIs - 1504150639
      • 3 Game Design Mistakes You're Making - 1504150636
      • Android TV - 1504150638
      • How to Go Viral Without Really Trying - 1504150641
    • Devoxx 2014 Interviews - 024
      • What's new in Android 5.0 Lollipop - 1504260740
      • Android Tools - 1504260743
      • BigQuery and user-defined functions - 1504260744
    • IO Bytes 2014 - 065
      • Dart in Google Cloud - 1505070810
      • Big genomic data on Google Cloud Platform - 1505070811
      • Easy International Checkout with Chrome - 1505070802
      • Google developer tools and APIs for iOS - 1503190436
      • Whet your appetite with IO Bytes - 1501080021
    • PlayTime@Shanghai - 095
      • 主题演讲 Chris Yerga - 1504060549
      • 如何成功地开发你的应用 Ellie Powers - 1504060550
      • 在Google上营利 Brahim Elbouchikhi - 1504060551
      • Playtime Shanghai event sizzle reel - 1504070552
    • Project Google I/O 2015 - 098
      • Project Tango Mobile 3D tracking and perception - 1506120857
      • Democratizing Education - 1506120868
      • Improve your Android app’s accessibility - 1506120864
      • Google Cloud Messaging 3.0 - 1506120844
      • Developers connecting the world through Google Play - 1506120862
  • 开源开放技术
    • Compressor Head - 013
      • The Trailer, Season 2 - 1503060385
      • Behind the Scenes - 1503210441
      • Arithmetic Compression (Ep 5, Compressor Head) Google - 1503070394
      • Introducing Compressor Head - 1502120372
      • Episode 1 (Variable Length Codes) - 1502120373
      • Episode 2 (The LZ77 Compression Family) - 1502120374
      • Episode 3 (Markov Chain Compression) - 1502120375
Powered by GitBook
On this page
  • 译者信息
  • 解说词中文版：

Was this helpful?

  1. 开源开放技术
  2. Compressor Head - 013

Episode 2 (The LZ77 Compression Family) - 1502120374

PreviousEpisode 1 (Variable Length Codes) - 1502120373NextEpisode 3 (Markov Chain Compression) - 1502120375

Last updated 5 years ago

Was this helpful?

视频发布时间

2014年5月20日

视频介绍

The LZ77 Compression Family from the late 70s have become the most dominant dictionary encoding schemes in compression. Colt McAnlis walks us through why the Lempel-Ziv algorithms are so dominant, in this episode of Compressor Head

视频推介语

暂无，待补充。

译者信息

翻译

润稿

终审

原始链接

中文字幕

翻译流水号

加入字幕组

周亿

——

——

1502120374

解说词中文版：

在这个数据压缩的领域

每个分支都有他自己的霸主

但是在一段时间之后

有一个家族用霸权

统治了压缩领域

这个统治阶级也就是压缩界的

Lempel-Ziv家族

并且它有跨代的血统

与长期不和的兄弟姐妹

和堂兄弟 甚至隔代阿姨

这颗家族树是如此的错综复杂以至于使得

权力的游戏看起来仅仅是一个本地披萨

不 这个家族不仅仅是这样

它巧妙 有活力 高效率

这使得它无可争辩的统治这个

压缩领域长达超过三十多年

但是要了解什么使得这个家族如此强大

我们不得不回到之前 换一种方式来

了解数据 并且挑战我们对于

熵的基本理解

这将是一个困难的任务

但是不用担心 年轻的程序猿

我就是来帮助你的

我是Colt McAnlis

这里是压缩头

Claude Shannon开发的熵的概念

是数据流中的信息内容的一种度量

或换句话说

熵是表示数据流中的信息

所需要的平均最小值的估计值

例如 你的熵值乘以

数据流的长度 你就能得到

根据信息论压缩

你的数据之后的理论最小值

注意 这里说的是信息理论 而不是信息定律

所以我们可以打破规则

例如 如果我们把这个排序

得到线性增长的序列

其熵值是大约4位一个字符

然而 如果我们使用δ编码

也就是只编译后一个字符

和前一个不一样的情况

我们得到一个全是1的数据流

也就是他的熵值是0

我们所做的是把数据流转化成字符

不相同的频率

抽象一下 也就是说这样改变了熵

使得能够更进一步压缩

将数据转换为状态可以更好的

压缩这种思想是

所有现代压缩理论的核心

但它并不像它看起来那样简单

比如 这个只包含1和2的流

这里使用δ转换

并没有改变字符频率

熵值仍然是大概每个字符

1±1/4位

我们知道每种字符转换

不一定符合每一种数据类型

你需要理解你的数据

尽可能的明白哪种转换

能使你的数据产生更低的熵值

相信我 它比听起来要困难得多

现在 如果我们把索伦之眼

聚焦于压缩文本数据

那么有一种更流行的转换

叫做符号分组

你们看 直到现在

我们只是看着在一个流内的单一字符

但是在现实中

在相邻字符间经常会有许多关联

例如 你经常看到字母Q

紧跟着字母U 将字符分组

意味着着重于字符中的

字符对或者是相邻字符 而不仅仅是单个字符

少年们 我的遥控器坏了

能不能 谢谢

所以对于这个例子中的数据

你能够看出通过分组

新的模式出现了 正如我们所知

熵的值理所当然的发生了改变

下一页 谢谢

但悲剧的是 我们没有机会来

手动看看压缩数据

所以当你得到复杂的字符串时

写一个分组算法会变得很蛋疼

开玩笑啦 不管怎么样

我们要想办法来解决这个问题

你丫在自拍

帮忙翻一下

如果我们把每个字母都定义成

一个字符 那么我们的熵值

大约在2.38左右

对于这样的字符串来说不算太糟

但是我认为我们可以做得更好

下次动作能快点么

看这个流

我们发现单词 或者说已知词汇

能够更简单分组

所以对于生存还是毁灭这个流来说

我们能够得到一个更好的熵值1.98

这比之前优化了很多

但我认为我们仍然可以做得更好

让我们来试试

事实上 一个天真的方法也许会

做出些不同

也许我们实际应该使用可以匹配的

最长的字符串

对于这个例子 to be or not

实际上出现了两次

这一段也是最长的

这里的问题是 我们最终得到的是

单一字符成组

才能实现没有任何重复

和曲解的可能

然而这样做的熵值达到了2.5

你看 我们真正需要的是动态算法

这种动态算法能够在

最长链和最小熵之间找到一个平衡

如你所想 这是很难的一个问题

谢谢

你TM在逗我

让我们进入下一场景

我觉得是时候透漏

LZ王朝的创始人了

你看 早在1977年 在意外的带他出来

竞选冬季奥运会之后

Abraham Lempel和Jacob Ziv

发明了一种算法 能够找到最佳的标记流方式

最初的两种转换方式 叫LZ77和LZ78

它们很善于发现最佳的标记

以至于在30多年内 还没有另一个算法

来取代它们

LZ家庭仍然在所有现代的

支柱和有用的压缩法占用重要地位

LZ算法的工作原理是

把流分成两段

左边流被称为搜索缓冲

包含我们已经看到

和处理过的符号

流的右边是表示前瞻缓冲区

包含我们还没有见过的符号

在实际问题中 搜索缓冲区

非常非常大

而前瞻缓冲区则小上很多

编码器将从向前瞻缓冲区读取一个字符

并试图找到在搜索缓冲区

找到相应匹配

如果字符被找到了 然后编译器

将从前缓冲区读取更多的字符

并继续在搜索缓冲区向后搜索

直到找到最长的匹配

当匹配最终确定时

编译器将输出一个指令

这个指令有三个部分 一个偏移量

一个长度 和流中的下一个字母

在这个例子中

偏移量是9

长度是2

下一个字母是B

做完这些以后 窗口就会右移

如果回瞻搜索区没有找到给出的输入字符的匹配

或者是给出的字符时给出一个新的字符

不是输出一个有长度和偏移量的指令

而是输出一个空指令 也就是0, 0

然后是刚刚操作过的字符本身

压缩的过程其实就是创建整个数据集的

一个个指令列表

然后根据他们自己的关系混合

每一个链来实现压缩

现在我们已经实现了编码过程

是时候见见家族的其他人了

在我们的树顶是LZ78和LZ77

我们的族长算法

每一个只要稍稍改变一下

搜索搜索缓冲区的方法或者是输出指令的方式

都会产生其变种算法

比如 LZW算法总会运行一个

可变长度的字符字典

并且总是尝试找到最长匹配

LZSS则是会比较每一条

比你要比较的字符串

长度要长的指令

或者是我的最爱 LZMA

用马尔科夫链混合LZ算法来更好的压缩

事实上 LZMA是整个树里面的

比较酷的算法之一

他不仅很新潮 并且

混合了统计编码和LZ变换

事实上 大多数在这的

压缩算法都不是你想的那么好

而需要统计编码来实际的到你想要的值

事实上 如果你查看一下现代压缩算法

你会看到很多的LZ

比如 LZW是在90年代早期

很流行的PKZIP算法的中流砥柱

另一方面 LZSS在WINRAR中使用广泛

而这里的deflate算法 你可能认识

它掌握着现如今在大部分

网上运行的GZIP背后的一切

或者你可能知道它的另一个名字WINZIP

当然 是Windows的一个变种

当然 我最喜欢的LZMA是

随着现在7ZIP这种

现代的打包工具而逐渐流行的

事实上所有的LZ都是

高效动态算法

是如今使用最快速

使用最广的打包工具的中流砥柱

就算有其他的算法产生

LZ家族的统治也会比

你我想象的更久

在数据压缩领域

LZ家族仍然处于统治地位

他们是在外流行的被认可的

压缩算法的中流砥柱

但是这个领域也有麻烦

一种全新的算法Markov模型

正在威胁着LZ的统治地位

但是这不是这次我们要说的故事

我是Colt McAnlis

谢谢收看

Youtube
Youtube
加入 GDG 字幕组
video_screenshot