String Algorithms in C : Efficient Text Representation and Search

Implement practical data structures and algorithms for text search and discover how it is used inside other larger applications. This unique in-depth guide explains string algorithms using the C programming language. String Algorithms in C teaches you the following algorithms and how to use them: classical exact search algorithms; tries and compact tries; suffix trees and arrays; approximative pattern searches; and more. In this book, author Thomas Mailund provides a library with all the algorithms and applicable source code that you can use in your own programs. There are implementations of all the algorithms presented in this book so there are plenty of examples. You'll understand that string algorithms are used in various applications such as image processing, computer vision, text analytics processing from data science to web applications, information retrieval from databases, network security, and much more. What You Will Learn Use classical exact search algorithms including naive search, borders/border search, Knuth-Morris-Pratt, and Boyer-Moor with or without Horspool Search in trees, use tries and compact tries, and work with the Aho-Carasick algorithm Process suffix trees including the use and development of McCreight's algorithm Work with suffix arrays including binary searches; sorting naive constructions; suffix tree construction; skew algorithms; and the Borrows-Wheeler transform (BWT) Deal with enhanced suffix arrays including longest common prefix (LCP) Carry out approximative pattern searches among suffix trees and approximative BWT searches Who This Book Is For Those with at least some prior programming experience with C or Assembly and have at least prior experience with programming algorithms. Table of Contents 4 About the Author 7 About the Technical Reviewer 8 Chapter 1: Introduction 9 Notation and conventions 9 Graphical notation 10 Code conventions 11 Reporting a sequence of results 13 Chapter 2: Classical algorithms for exact search 19 Naïve algorithm 20 Border array and border search 22 Borders and border arrays 23 Exact search using borders 26 Knuth-Morris-Pratt 29 Boyer-Moore-Horspool 36 Extended rightmost table 43 Boyer-Moore 46 Jump rule one 48 Computing the Z array 55 Z-based jump table 59 Second jump table 61 Combining the jump rules 63 Aho-Corasick 66 Tries 66 Preprocessing 80 The algorithm with iterators 87 Comparisons 91 Chapter 3: Suffix trees 95 Compacted trie and suffix representation 96 Naïve construction algorithm 101 Suffix trees and the SA and LCP arrays 109 Constructing the SA and LCP arrays 109 Constructing the suffix tree from the SA and LCP arrays 112 McCreight’s algorithm 118 Searching with suffix trees 131 Leaf iterators 133 Comparisons 139 Chapter 4: Suffix arrays 147 Constructing suffix arrays 150 Trivial constructions—Comparison-based sorting 150 The skew algorithm 153 Constructing SA3 156 Recursively sorting sa12 162 Merging arrays 168 Construction function 172 The SA-IS algorithm 175 Remapping 184 Implementing the algorithm 187 Memory reduction 201 Searching using suffix arrays 214 Binary search 214 Burrows-Wheeler transform–based search 222 C and O tables 223 Building the C and O tables 224 Searching 227 Getting the longest common prefix (LCP) array 229 Comparisons 233 Chapter 5: Approximate search 243 Local alignment and CIGAR notation 243 Brute force approach 246 Building an edit cloud 246 Suffix trees 258 The Li-Durbin algorithm 266 Comparisons 277 Chapter 6: Conclusions 280 Appendix: Fundamental data structures 281 Vectors 281 Lists 287 Queues 288 Index 293 Implement practical data structures and algorithms for text search and discover how it is used inside other larger applications. This unique in-depth guide explains string algorithms using the C programming language. "String algorithms in C" teaches you the following algorithms and how to use them: classical exact search algorithms; tries and compact tries; suffix trees and arrays; approximative pattern searches; and more. In this book, author Thomas Mailund provides a library with all the algorithms and applicable source code that you can use in your own programs. There are implementations of all the algorithms presented in this book so there are plenty of examples. You'll understand that string algorithms are used in various applications such as image processing, computer vision, text analytics processing from data science to web applications, information retrieval from databases, network security, and much more. You will: use classical exact search algorithms including naive search, borders/border search, Knuth-Morris-Pratt, and Boyer-Moor with or without Horspool ; Search in trees, use tries and compact tries, and work with the Aho-Corasick algorithm ; Process suffix trees including the use and construction with McCreight's algorithm ; Work with suffix arrays including binary searches; sorting naive constructions; suffix tree construction; skew algorithms; and the Borrows-Wheeler transform (BWT) ; Deal with enhanced suffix arrays including longest common prefix (LCP) ; Carry out approximative pattern searches among suffix trees and approximative BWT searches