## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

How do you distinguish a cat from a dog by their DNA? Did Shakespeare really write all of his plays? Pattern matching techniques can offer answers to these questions and to many others, from molecular biology, to telecommunications, to classifying Twitter content. This book for researchers and graduate students demonstrates the probabilistic approach to pattern matching, which predicts the performance of pattern matching algorithms with very high precision using analytic combinatorics and analytic information theory. Part I compiles known results of pattern matching problems via analytic methods. Part II focuses on applications to various data structures on words, such as digital trees, suffix trees, string complexity and string-based data compression. The authors use results and techniques from Part I and also introduce new methodology such as the Mellin transform and analytic depoissonization. More than 100 end-of-chapter problems help the reader to make the link between theory and practice.

1. Coverpage
2. Halftitle page
3. Title page
5. Dedication page
6. Contents
7. Foreword
8. Preface
9. Acknowledgments
11. I ANALYSIS
1. Chapter 1 Probabilistic Models
1. 1.1 Probabilistic models on words
2. 1.2 Probabilistic tools
3. 1.3 Generating functions and analytic tools
4. 1.4 Special functions
5. 1.5 Exercises
6. Bibliographical notes
2. Chapter 2 Exact String Matching
1. 2.1 Formulation of the problem
2. 2.2 Language representation
3. 2.3 Generating functions
4. 2.4 Moments
5. 2.5 Limit laws
6. 2.6 Waiting times
7. 2.7 Exercises
8. Bibliographical notes
3. Chapter 3 Constrained Exact String Matching
4. Chapter 4 Generalized String Matching
1. 4.1 String matching over a reduced set
2. 4.2 Generalized string matching via automata
3. 4.3 Generalized string matching via a language approach
4. 4.4 Exercises
5. Bibliographical notes
5. Chapter 5 Subsequence String Matching
12. II APPLICATIONS
1. Chapter 6 Algorithms and Data Structures
2. Chapter 7 Digital Trees
1. 7.1 Digital tree shape parameters
2. 7.2 Moments
3. 7.3 Limiting distributions
4. 7.4 Average profile of tries
5. 7.5 Exercises
6. Bibliographical notes
3. Chapter 8 Suffix Trees and Lempel–Ziv’77
1. 8.1 Random tries resemble suffix trees
2. 8.2 Size of suffix tree
3. 8.3 Lempel–Ziv’77
4. 8.4 Exercises
5. Bibliographical notes
4. Chapter 9 Lempel–Ziv’78 Compression Algorithm
1. 9.1 Description of the algorithm
2. 9.2 Number of phrases and redundancy of LZ’78
3. 9.3 From Lempel–Ziv to digital search tree
4. 9.4 Proofs of Theorems 9.2.1 and 9.2.2
5. 9.5 Exercises
6. Bibliographical notes
5. Chapter 10 String Complexity
1. 10.1 Introduction to string complexity
2. 10.2 Analysis of string self-complexity
3. 10.3 Analysis of the joint complexity
4. 10.4 Average joint complexity for identical sources
5. 10.5 Average joint complexity for nonidentical sources
6. 10.6 Joint complexity via suffix trees
7. 10.7 Conclusion and applications
8. 10.8 Exercises
9. Bibliographical notes
13. Bibliography
14. Index