Pearls of Algorithm Engineering

Description

There are many textbooks on algorithms focusing on big-O notation and basic design principles. This book offers a unique approach to taking the design and analyses to the level of predictable practical efficiency, discussing core and classic algorithmic problems that arise in the development of big data applications, and presenting elegant solutions of increasing sophistication and efficiency. Solutions are analyzed within the classic RAM model, and the more practically significant external-memory model that allows one to perform I/O-complexity evaluations. Chapters cover various data types, including integers, strings, trees, and graphs, algorithmic tools such as sampling, sorting, data compression, and searching in dictionaries and texts, and lastly, recent developments regarding compressed data structures. Algorithmic solutions are accompanied by detailed pseudocode and many running examples, thus enriching the toolboxes of students, researchers, and professionals interested in effective and efficient processing of big data. Contents Preface page xi 1 Introduction 1 2 A Warm-up 10 2.1 A Cubic-Time Algorithm 11 2.2 A Quadratic-Time Algorithm 12 2.3 A Linear-Time Algorithm 14 2.4 Another Linear-Time Algorithm 16 2.5 A Few Interesting Variants1 17 3 Random Sampling 23 3.1 Disk Model and Known Sequence Length 24 3.2 Streaming Model and Known Sequence Length 26 3.3 Streaming Model and Unknown Sequence Length 28 4 List Ranking 32 4.1 The Pointer-Jumping Technique 33 4.2 Parallel Algorithm Simulation in a Two-Level Memory 34 4.3 A Divide-and-Conquer Approach 37 5 Sorting Atomic Items 44 5.1 The Merge-Based Sorting Paradigm 45 5.2 Lower Bounds 52 5.3 The Distribution-Based Sorting Paradigm 57 5.4 Sorting With Multi-Disks1 67 6 Set Intersection 72 6.1 Merge-Based Approach 74 6.2 Mutual Partitioning 75 viii Contents 6.3 Doubling Search 77 6.4 Two-Level Storage Approach 79 7 Sorting Strings 82 7.1 A Lower Bound 83 7.2 RADIXSORT 84 7.3 Multi-key QUICKSORT 90 7.4 Some Observations on the Two-Level Memory Model1 94 8 The Dictionary Problem 96 8.1 Direct-Address Tables 97 8.2 Hash Tables 98 8.3 Universal Hashing 101 8.4 A Simple (Static) Perfect Hash Table 106 8.5 Cuckoo Hashing 111 8.6 More on Static and Perfect Hashing: Minimal and Ordered 116 8.7 Bloom Filters 121 9 Searching Strings by Prefix 128 9.1 Array of String Pointers 129 9.2 Locality-Preserving Front Coding1 134 9.3 Interpolation Search 136 9.4 Compacted Trie 138 9.5 Patricia Trie 142 9.6 Managing Huge Dictionaries1 145 10 Searching Strings by Substring 153 10.1 Notation and Terminology 153 10.2 The Suffix Array 154 10.3 The Suffix Tree 172 10.4 Some Interesting Problems 181 11 Integer Coding 194 11.1 Elias Codes: and 197 11.2 Rice Code 198 11.3 PForDelta Code 199 11.4 Variable-Byte Code and (s, c)-Dense Codes 200 11.5 Interpolative Code 203 11.6 Elias–Fano Code 205 12 Statistical Coding 210 12.1 Huffman Coding 210 12.2 Arithmetic Coding 221 12.3 Prediction by Partial Matching1 234 Contents ix 13 Dictionary-Based Compressors 240 13.1 LZ77 241 13.2 LZ78 244 13.3 LZW 246 13.4 On the Optimality of Compressors1 248 14 Block-Sorting Compression 252 14.1 The Burrows–Wheeler Transform 253 14.2 Two Other Simple Transforms 258 14.3 The bzip Compressor 264 14.4 On Compression Boosting1 267 14.5 On Compressed Indexing1 268 15 Compressed Data Structures 274 15.1 Compressed Representation of (Binary) Arrays 274 15.2 Succinct Representation of Trees 284 15.3 Succinct Representation of Graphs 291 16 Conclusion 299 Index 302