Jewels of Stringology [Paperback]

Wojciech Rytter (Author), Maxime Crochemore (Author)

Book Description

Publication Date: May 2003 | ISBN-10: 9810248970 | ISBN-13: 978-9810248970

The term "stringology" is a popular nickname for text algorithms, or algorithms on strings. This work 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 text 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 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.

Editorial Reviews

Review

.,." nicely covers material from the famous KMP and BM algorithms to suffix trees ..."

Product Details

• Paperback: 320 pages
• Publisher: World Scientific Publishing Company (May 2003)
• Language: English
• ISBN-10: 9810248970
• ISBN-13: 978-9810248970
• Product Dimensions: 9 x 6.1 x 0.6 inches
• Shipping Weight: 14.4 ounces
• Average Customer Review: 4.3 out of 5 stars  See all reviews (3 customer reviews)
• Amazon Best Sellers Rank: #1,746,729 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

4 of 4 people found the following review helpful:

5.0 out of 5 stars nice book, March 16, 2004

By 

Thierry Lecroq (Rouen (France)) - See all my reviews

This review is from: Jewels of Stringology (Hardcover)

The book is an excellent presentation of algorithms on the conceptual level and
avoids implementation details. This does not mean that it
has no practical value. The understanding and simplification of an algorithm
is the first main step towards its practicality. The issues of implementation
details would double the size of the book and obscure the main ideas.
The great advantage of the currenct version are conciseness and simplicity.
Despite that it is a "parade" of a huge number of classical important algorithms.
The style is reader-friendly and very algorithmic. The main issue is the
understanding how an algorithm works. Many inherently complex
and famous algorithms are presented in a simplified way.
The book can be used as a companion book in courses on algorithms
and data structures at any level. The required theoretical background
is reduced to minimum. The area is underrepresented in most general
textbooks on algorithms and data structures, and the book fills

the gap nicely.

The title is well chosen, the presented algorithms are real "jewels"
and the word "stringology" is a good nickname for the area, it has
been invented before by other people and is generally accepted in the
community of people doing text algorithmics.

The book is a simplified and modernized version of "Text algorithms" by
the same authors. The difficult algorithms are omitted or rewritten.
The main audience targeted by the book are the undergraduate and

graduate students. Most classical algorithms are easily understandable,
since they use only the very simple data structure: 1-dimenesional array.
It gives a source of algorithmically valuable algorithms (in sense of teaching
algorithm courses) with a very simple implementation, the knowledge of
any programming language at a very beginning level is just enough. Basic
string algorithms can be swallowed by an undergraduate student much easier
than for example graph algorithms.

Altogether the book is an excellent text on algorithms.

7 of 9 people found the following review helpful:

3.0 out of 5 stars Theoretical rather than practical, February 27, 2004

By A Customer

Amazon Verified Purchase

This review is from: Jewels of Stringology (Paperback)

The book loses one star because it's primarily a presentation of algorithms that are theoretically interesting, rather than algorithms that are good to use. I doubt very much that the authors have any real software engineering experience.

It loses another star because the writing style is so awkward and painful to read. The authors don't appear to be native speakers of English, and it shows. The text really needs to be cleaned up by an editor familar with idiomatic English.

Bottom line: If you actually need to implement a string search, look elsewhere for guidance...

2 of 3 people found the following review helpful:

5.0 out of 5 stars This book is a jewel, July 8, 2009

By 

lew "lwndw123" (Connecticut, USA) - See all my reviews

Amazon Verified Purchase

This review is from: Jewels of Stringology (Paperback)

Absolutely fantastic book! Short, but deep. Presents algorithms that are very hard to find elsewhere.

Warning: this is not to "copy and paste" book. If you expect that there will be ready to use code, look for O'Reilly catalog. To use algorithms presented in the book, you have to actually think before you start coding.

Book is hard to get: I waited few month until Amazon provided a copy. But it was worth waithing