Analytic Pattern Matching from DNA to Twitter

Description

Contents......Page 3 Foreword......Page 7 Preface......Page 8 --- Analysis......Page 14 Probabilistic Models......Page 15 Probabilistic models on words......Page 16 Probabilistic tools......Page 20 Generating functions and analytic tools......Page 25 Special functions......Page 28 Exercises......Page 31 Bibliographical notes......Page 33 Formulation of the problem......Page 34 Language representation......Page 36 Generating functions......Page 39 Moments......Page 42 Limit laws......Page 44 Waiting times......Page 54 Exercises......Page 55 Bibliographical notes......Page 56 Constrained Exact String Matching......Page 57 sequences......Page 58 Moments......Page 64 The probability count......Page 67 Central limit law......Page 70 Large deviations......Page 71 Application: significant signals in neural data......Page 80 Bibliographical notes......Page 83 Generalized String Matching......Page 85 String matching over a reduced set......Page 86 Generalized string matching via automata......Page 92 Generalized string matching via a language approach......Page 103 Exercises......Page 116 Bibliographical notes......Page 117 Subsequence String Matching......Page 119 Problem formulation......Page 120 Mean and variance analysis......Page 122 Central limit laws......Page 128 Limit laws for fully constrained pattern......Page 132 Generalized subsequence problem......Page 133 Exercises......Page 139 Bibliographical notes......Page 142 --- Applications......Page 143 Algorithms & Data Structures......Page 144 Tries......Page 145 Suffix trees......Page 149 Lempel–Ziv’77 scheme......Page 152 Digital search tree......Page 153 Parsing trees and Lempel–Ziv’78 algorithm......Page 156 Bibliographical notes......Page 162 Digital Trees......Page 164 Digital tree shape parameters......Page 165 Moments......Page 168 Limiting distributions......Page 194 Average profile of tries......Page 206 Exercises......Page 219 Bibliographical notes......Page 225 Suffix Trees & Lempel-Ziv'77......Page 227 Random tries resemble suffix trees......Page 230 Size of suffix tree......Page 251 Lempel–Ziv’77......Page 256 Exercises......Page 273 Bibliographical notes......Page 274 Lempel-Ziv'78 Compression Algorithm......Page 275 Description of the algorithm......Page 277 Number of phrases and redundancy of LZ’78......Page 279 From Lempel–Ziv to digital search tree......Page 287 Proofs of Theorems 9.2.1 and 9.2.2......Page 298 Exercises......Page 315 Bibliographical notes......Page 317 String Complexity......Page 318 Introduction to string complexity......Page 319 Analysis of string self-complexity......Page 321 Analysis of the joint complexity......Page 322 Average joint complexity for identical sources......Page 329 Average joint complexity for nonidentical sources......Page 330 Joint complexity via suffix trees......Page 347 Conclusion and applications......Page 350 Exercises......Page 351 Bibliographical notes......Page 353 Biblio......Page 354 Index......Page 369