Text algorithms. (English) Zbl 0844.68101

New York, NY: Oxford Univ. Press. xii, 412 p. (1994).
The main goal of the book is three-fold: (1) to make an exposition of the text algorithmic techniques, (2) to discuss the foundations of these algorithms and their interconnections, and (3) to relate the text algorithm classification to some important complexity measures. The 15 chapters of the book (each one ending bibliographic notes and selected references) cover the following topics: Chapter 2 reviews the basic problems, their interaction, some combinatorics on words, and theoretical foundations: machine models and algorithmic efficiency. Chapters 3-4 deals with two famous string matching algorithms: Knuth-Morris-Pratt and Boyer-Moore algorithms. These chapters prepare the subsequent topics on parallel string-matching and two-dimensional pattern matching algorithms. Chapters 5-6 are the basic chapters of the book. They cover essential data structures to represent the subwords of a text, suffix trees and subword graphs, as well as their manipulation on trees, links, vectors, lists etc. Chapter 7 presents Aho-Corasick automata for multi-pattern matching, while Chapter 8 investigates regularities in texts: symmetries and repetitions. A basic new data structure, called the dictionary of basic factors, is considered. Chapter 9 introduces parallel algorithms on texts, and discusses a parallel version of the Karp-Miller-Rosenberg algorithm. Chapter 10 is devoted to compression techniques for texts. Ziv-Lempel algorithm and text factorization are discussed. Algorithms on approximate patterns are discussed in Chapter 11, and two-dimensional pattern matching is analyzed in Chapter 12. Chapter 13 presents advanced material on three different time-space optimal string-matching algorithms, while the topic of Chapter 14 consists of optimal parallel algorithms on texts, continuing the considerations in Chapter 9. The last Chapter 15 contains several miscellaneous problems such as tree-pattern-matching, shortest common superstring computation, maximal suffixes, and Lyndon factorizations. The book comprises also a set of 62 proposed exercises, a rich bibliography, and an useful index. This (text) book succeeds to cover the gap between practical and theoretical problems on text (word) algorithms, bringing together both the basic but also many new results dispersed in the journal article literature.
Reviewer: N.Curteanu (Iaşi)


68R15 Combinatorics on words
68U15 Computing methodologies for text processing; mathematical typography
68N20 Theory of compilers and interpreters
68W30 Symbolic computation and algebraic computation
68W15 Distributed algorithms
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science