Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010192412 | QA76.9.A43 C76 2007 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
The book is intended for lectures on string processes and pattern matching in Master's courses of computer science and software engineering curricula. The details of algorithms are given with correctness proofs and complexity analysis, which make them ready to implement. Algorithms are described in a C-like language. The book is also a reference for students in computational linguistics or computational biology. It presents examples of questions related to the automatic processing of natural language, to the analysis of molecular sequences, and to the management of textual databases.
Reviews 1
Choice Review
A string is a finite sequence of characters. For example, the word "string" is a string consisting of the five characters s, t, r, i, n, g, in that order. It is evident that string recognition and matching is essential in computer science. To look up Google, one's computer has to recognize the string "Google." Text editing would be hopeless without the ability to locate strings within text and to check against a list of correct spellings. String matching is also essential in the field popularly known as DNA. The Human Genome Project would still be in its early stages without the sophisticated algorithms used to convert laboratory data into searchable strings representing DNA. Algorithms on Strings is a welcome addition to the literature. Crochemore (Universite de Marne-la-Vallee, France) and Hancart and Lecroq (both, Universite de Rouen, France) present all the standard "stringology" material in a concise mathematical form. They prove and analyze algorithms from automata to dynamic programming, and present appropriate data structures to support various classes of queries. Applications are mentioned, but not really covered. The overly complicated explanations and francophone English make this fairly intuitive material rather difficult to understand. Still, advanced-level computer science students will find this a useful resource. Summing Up: Recommended. Graduate students. P. Cull Oregon State University
Table of Contents
| 1 Introduction |
| 2 Foundations |
| 3 Basic String-Matching Algorithms |
| 4 The Boyer-Moore Algorithm and its Variations |
| 5 Suffix Trees |
| 6 Subword Graphs |
| 7 Automata-Theoretic Approach |
| 8 Regularities in Texts: Symmetries and Repetitions |
| 9 Almost Optimal Parallel Algorithms |
| 10 Text Compression Techniques |
| 11 Approximate Pattern Matching |
| 12 Two-Dimensional Pattern Matching |
| 13 Time-Space Optimal String Matching |
| 14 Time-Processors Optimal String Matching |
| 15 Miscellaneous |
