Understanding Compression

所需积分/C币:10 2016-11-24 08:47:40 11MB PDF
收藏 收藏

Understanding Compression
Understanding Compression Data Compression for Modern developers Colt Mcanlis and aleks hacky Beijing. Boston. Farnham. Sebastopol. Tokyo OREILLY Understanding compression by colt mcanlis and Aleks haeck Copyright C 2016 Colton McAnlis and Aleks Haecky. All rights reserved Printed in the united states of america Published by o reilly Media, InC,1005 Gravenstein Highway North, Sebastopol, CA 95472 O Reilly books may be purchased for educational, business, or sales promotional use. Online editions are alsoavailableformosttitles(http://safaribooksonline.com).Formoreinformationcontactourcorporate institutionalsalesdepartment800-998-9938orcorporate@oreilly.com Editor: Tim mcgovern Indexer: Ellen Troutman-Zaig Production Editor: Melanie Yarbrough Interior Designer: David Futato Copyeditor: Octal Publishing, Inc Cover Designer: Karen Montgomery Proofreader Jasmine kwityn Illustrator: Melanie yarbrough July 2016 First edition Revision history for the first edition 2016-07-11: First release Seehttp://oreilly.com/catalog/errata.csp?isbn=9781491961537forreleasedetails The O Reilly logo is a registered trademark of O'Reilly Media, Inc. Understanding Compression, the cover mage, and related trade dress are trademarks of o Reilly Media, Inc. While the publisher and the authors have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the authors disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights 978-1-491-96153-7 From CLM To JAM and MLM: I swear to Zuul, that if you don ' t eat your broccoli right now, I'm going to write a book. And in the dedication of that book, Im going to call you out as being afraid of a piece of foliage that humans have been eating for thousands of genera tions. Then, 20 years from now, when you have kids of your own, I'm going to pull that book out, and show you what I wrote, and laugh in your face, because you 'll know how crazy you re making me right now. #parenting To KMKM: How about another decade, just for good measure? From ah To AHS and GHS: I hoped you d learn to cook. Instead, you proved that humankind can survive on fresh apples and stale supermarket sushi Table of contents Foreword XI Preface Chapter Synopsis 18 1. Let's not be boring The Five Buckets of Compression Algorithms Claude Shannon Is Infuriating! The Only Thing You Need to Know about Data Compression A World Built on Data Compression 2. Do Not skip This chapter. 11234999 Understanding Binary Base 10 System Binary number system 10 Information Theory 13 An Excursion into Binary Search 14 Entropy: The Minimum Bits Needed to Represent a number 16 Standard Number Lengths 3. Breaking Entropy..,.... ,19 Understanding Entropy 19 What This Entropy Stuff Is Good For 21 Understanding Probability 22 Breaking Entropy 23 Example 1: Delta Coding 24 Example 2: Symbol grouping 25 Example 3 Permutations 26 Information Theory Versus Data Compression 31 4. Variable-Length Codes. 33 Morse Code Probability, Entropy, and Codeword Size 36 Variable-Length Codes 38 USing vlcs 38 Creating VLCs 42 A Handful of Example vlcs Finding the Right Code for Your Data Set 51 5. Statistical Encoding.,..................... Statistically Compressing to Entropy 53 Huffman Coding 55 Building a Huffman Tree 55 Generating Codewords 57 Encoding and decoder g 58 Practical Implementations 8 arithmetic Coding 60 Fi inain g the right Number 61 Encoding 62 Picking the Right Output value 64 Decoding 64 Practical Implementations 6 Asymmetric Numeral Systems Encoding and Decoding Using a Transform Table 70 Creating the Reference Table 71 Using ANS for Compression Decoding e nple So Where does the compression Come From? 76 Practical Compression: Which Statistical Algorithm Do I Choose? 6. Adaptive Statistical Encoding. 79 Locality Matters for Entropy 79 Adaptive VLC Encoding 81 Dynamically building a Vlc Table 81 Literals 84 Resets 87 Knowing When to Reset 88 Using This in Practic 89 Adaptive arithmetic Coding 89 Adaptive Huffman Coding 90 Table of contents The Modern Choice 91 7. Dictionary TransformS.......... A Basic Dictionary Transform 94 Finding the Right Words 95 The Lempel-Ziv algorithm 98 How LZ Works Encodins 104 Decoding 105 Compressing lz output 106 LZ Variants 107 Collect Them all 110 8. Contextual data transforms Run-Length Encoding 112 Dealing with Short Runs 112 Compressing 114 Delta coc g 115 XOR Delta Coding Frame of Reference Delta Coding Patched Frame of Reference Delta Coding 120 Compressing Delta-Encoded Data 123 Does it Work on text? 123 Move-to-Front Coding 123 Avoiding Rogue Symbols 125 Compressing M 126 Burrows-Wheeler Transform 126 Ordering Is Important 128 How bWt Works 128 Inverse bWt 130 Practical Implementations 132 Compressing BWT 132 9. Data Modeling The Chains of Markov 136 Markov and Compression 139 Practical Implementations 145 Prediction by Partial Matching 145 The Search Trie 147 Compressing a symbol 149 Choosing a Sensible n value 150 Dealing with Unknown Symbols 150 Table of contents|ⅶi Context Mixing 150 Types of models 151 Types of Mixing 153 The Next Big Thing? 154 10. Switching Gears 155 Media-Specific Compression 155 General-Purpose Compression 156 Compression in Practice 157 11. Evaluating〔 ompression..…, 159 Compression Usage Scenarios 159 Compressed Offline, Decompressed On-Client 159 Compressed On-Client, Decompressed In-Cloud 160 Compressed In-Cloud, Decompressed On-Client 160 Compressed On-Client, Decompressed On-Client 161 Compression Need 161 Compression ratio 162 Compression Performance 163 Decompression Performance 164 ability to Decode-Stream 164 Comparing Compressors 165 2. Compressing Image Data Types. ,167 Understanding Quality Versus File Size 167 What Reduces Image quality? 169 Measuring Image quality 171 Making this work 173 Image Dimensions are Important 173 Choosing the Correct Image Format PNG 175 JPG 176 IF 177 Webp 177 And Now for Choosing… 177 GPU Texture formats 179 Vector formats 180 Eyes on the prize 182 13. Serialized data ····春·。自·鲁 183 Understanding Common Use Cases 184 Dynamically Server-Built Data 184 I Table of Contents

试读 241P Understanding Compression
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
Understanding Compression 10积分/C币 立即下载
Understanding Compression第1页
Understanding Compression第2页
Understanding Compression第3页
Understanding Compression第4页
Understanding Compression第5页
Understanding Compression第6页
Understanding Compression第7页
Understanding Compression第8页
Understanding Compression第9页
Understanding Compression第10页
Understanding Compression第11页
Understanding Compression第12页
Understanding Compression第13页
Understanding Compression第14页
Understanding Compression第15页
Understanding Compression第16页
Understanding Compression第17页
Understanding Compression第18页
Understanding Compression第19页
Understanding Compression第20页

试读结束, 可继续阅读

10积分/C币 立即下载