To my boys: Miguel, Pedro Julio and Ignacio
and my girls: Ariana and Marta


Preface to the first edition

Computer Science has been, throughout its evolution, more an art than a science. My favourite example which illustrates this point is to compare a major software project (like the writing of a compiler) with any other major project (like the construction of the CN tower in Toronto). It would be absolutely unthinkable to let the tower fall down a few times while its design was being debugged: even worse would be to open it to the public before discovering some other fatal flaw. Yet this mode of operation is being used everyday by almost everybody in software production.

Presently it is very difficult to ``stand on your predecessor's shoulders'', most of the time we stand on our predecessor's toes, at best. This handbook was written with the intention of making available to the computer scientist, instructor or programmer the wealth of information which the field has generated in the last 20 years.

Most of the results are extracted from the given references. In some cases the author has completed or generalized some of these results. Accuracy is certainly one of our goals, and consequently the author will cheerfully pay $2.00 for each first report of any type of error appearing in this handbook.

Many people helped me directly or indirectly to complete this project. Firstly I owe my family hundreds of hours of attention. All my students and colleagues had some impact. In particular I would like to thank Maria Carolina Monard, Nivio Ziviani, J. Ian Munro, Per-Å ke Larson, Doron Rotem and Derick Wood. Very special thanks go to Frank W. Tompa who is also the coauthor of chapter 2. The source material for this chapter appears in a joint paper in the November 1983 issue of Communications of the ACM.

Montevideo G.H. Gonnet

December 1983

Preface to the second edition

The first edition of this handbook has been very well received by the community, and this has given us the necessary momentum for writing a second edition. In doing so, R. A. Baeza-Yates has joined me as a coauthor. Without his help this version would have never appeared.

This second edition incorporates many new results and a new chapter on text searching. The area of text managing, in particular searching, has risen in importance and matured in recent times. The entire subject of the handbook has matured too; our citations section has more than doubled in size. Table searching algorithms account for a significant part of this growth.

Finally we would like to thank the over one hundred readers who notified us about errors and misprints, they have helped us tremendously in correcting all sorts of blemishes. We are especially grateful for the meticulous, even amazing, work of Lynne Balfe, the proofreader. We will continue cheerfully to pay $4.00 (increased due to inflation) for each first report of an error.

Zürich G.H. Gonnet

December 1990

Santiago de Chile R.A. Baeza-Yates

December 1990

© Addison-Wesley Publishing Co. Inc.