Technical Report TR-1995-01

BibliographyZiegler, Bernhard: Initialisierung der Verschiebefunktionen zur Mustersuche in Texten.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1995/01.
27 pages, german.
CR-SchemaF.2.2 (Nonnumerical Algorithms and Problems)
H.3.3 (Information Search and Retrieval)
KeywordsWortsuche; Mustererkennung; Boyer-Moore
Abstract

Die schnellsten Algorithmen zur Mustersuche in Texten sind Varianten des genialen Algorithmus BoMo von Boyer und Moore. Wenn Text und Muster nicht zusammenpassen, verwendet BoMo Tabellen, um die größten zulässigen Verschiebungen zu ermitteln. Eine effiziente Berechnung dieser Tabellen wurde von Knuth angegeben.

Hier wird sowohl auf die den Algorithmen KMP von Knuth, Morris und Pratt, BoMo und ESS zugrundeliegenden Ideen eingegangen, als auch die Implementierung ihrer Verschiebetabellen detailliert beschrieben.

The fastest known algorithms for pattern matching in strings are derivatives of the ingenious algorithm BoMo of Boyer and Moore. On mismatch tables are used by BoMo to ascertain the largest possible pattern shifts. An efficient scheme of computing these tables was given by Knuth.

In this report we recapitulate the key ideas underlying the algorithms KMP of Knuth, Morris and Pratt, BoMo, and ESS, as well as presenting the implementation of their shift tables in detail.

Full text and
other links
HTML (generated from PostScript)
Department(s)University of Stuttgart, Betriebssoftware
Entry dateMay 13, 1996
   Publ. Computer Science