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.
Author(s): Paolo Ferragina
Edition: 1
Publisher: Cambridge University Press
Year: 2023
Language: English
Commentary: Publisher's PDF
Pages: 326
City: Cambridge, UK
Tags: Algorithms; Algorithms Design Techniques; Algorithm Analysis; Compression Algorithms; Huffman Coding; Algorithm Complexity; Sorting Algorithms; String Algorithms; Lists
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
