Flexible Pattern Matching in Strings

Rating:
Summary: Thin but useful
Review: Don't let its small size (~200 pages) fool you. There's a lot of good material here, and in very usable form. In fact, that's the whole focus of the book: practical, efficient implementations.

The main topics, chapter by chapter, are simple matching of one desired word to a string, matching of multiple words, two levels of complexity in wildcards and regular expressions, and approximate matching. A number of important and historical algorithms are discussed in each chapter, in great detail. There's pseudo-code for the most important algorithms. Quite a few also have examples worked in detail. The mechanics are tedious and somewhat bulky, but anyone actually trying to implement these techniques will appreciate the examples.

What's really interesting is what's not in this book. You won't find a lot of theory, and you won't find some of the most famous algorithms in string matching. The authors make it clear that this is about practical algorithms with efficient implementations. Lots of the algorithms beloved by theoreticians are impractically complex or just plain slow. Those may be mentioned in passing or as the base for more practical algorithms, but are not welcome on these pages.

It's not an easy read, but it's not a book for people with easy problems. It discusses tradeoffs, like when one technique works well for short strings but another works better on long strings. It addresses the different needs of English-language processing and bioinformatics - just the different numbers of letters in each alphabet make a difference, in some cases.

This is a good one for anyone who takes string processing seriously. There's no cut&paste code here, but plenty for a knowledgable programmer to use. Even better, it offers references to the literature and to working code, and pointers to some books on related topics. I expect to get a lot of use out of this one.

//wiredweird

Rating:
Summary: Solid Theory
Review: This is an excellent book for someone with a strong foundation in computer science wanting to learn about regular expression and string matching. It is not for the feint-hearted, and would not be recommended to computer science novices. Written by one of the world experts in the field, the relatively thin book is packed with theory and comments on application. The algorithms are presented in a very concise form which often requires a fair amount of thought when trying to implement. However once understood, the book makes an excellent reference for the various algorithms.