Jewels of Stringology: Text Algorithms

封面
World Scientific, 2003 - 310 頁
4 書評
The term “stringology” is a popular nickname for text algorithms, or algorithms on strings. This book deals with the most basic algorithms in the area. Most of them can be viewed as “algorithmic jewels” and deserve reader-friendly presentation. One of the main aims of the book is to present several of the most celebrated algorithms in a simple way by omitting obscuring details and separating algorithmic structure from combinatorial theoretical background. The book reflects the relationships between applications of text-algorithmic techniques and the classification of algorithms according to the measures of complexity considered. The text can be viewed as a parade of algorithms in which the main purpose is to discuss the foundations of the algorithms and their interconnections. One can partition the algorithmic problems discussed into practical and theoretical problems. Certainly, string matching and data compression are in the former class, while most problems related to symmetries and repetitions in texts are in the latter. However, all the problems are interesting from an algorithmic point of view and enable the reader to appreciate the importance of combinatorics on words as a tool in the design of efficient text algorithms.In most textbooks on algorithms and data structures, the presentation of efficient algorithms on words is quite short as compared to issues in graph theory, sorting, searching, and some other areas. At the same time, there are many presentations of interesting algorithms on words accessible only in journals and in a form directed mainly at specialists. This book fills the gap in the book literature on algorithms on words, and brings together the many results presently dispersed in the masses of journal articles. The presentation is reader-friendly; many examples and about two hundred figures illustrate nicely the behaviour of otherwise very complex algorithms.
 

讀者評論 - 撰寫評論

我們找不到任何評論。

內容

Stringology
1
Basic string searching algorithms
19
Preprocessing for basic searchings
33
Online construction of suffix trees
45
More on suffix trees
59
Subword graphs
69
Text algorithms related to sorting
85
Symmetries and repetitions in texts
111
Automat atheoretic approach
163
Approximate pattern matching
183
Matching by dueling and sampling
199
Twodimensional pattern matching
209
Twodimensional periodicities
225
Parallel text algorithms
249
Miscellaneous
271
Bibliography
285

Const antspace searchings
125
Text compression techniques
141

其他版本 - 查看全部

常見字詞

關於作者 (2003)

Professor Maxime Crochemore received his PhD in 1978 and his Doctorat d'etat in 1983 at the University of Rouen. He got his first professorship position at the University of Paris-Nord in 1975 where he acted as President of the Department of Mathematics and Computer Science for two years. He became professor at the University Paris 7 in 1989 and was involved in the creation of the University of Marne-la-Vallee where he is presently Professor. He also created the Computer Science research laboratory of this university in 1991, which has now more than fifty permanent researchers. He was the director of the laboratory until 2005. Professor Crochemore is Senior Research Fellow at King's College London since 2002.

書目資訊