Technical Report TR-1993-14

BibliographyZiegler, Bernhard: QuickSearch : ein schneller Algorithmus zur Mustersuche in Zeichenfolgen.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1993/14.
11 pages, german.
CR-SchemaI.5 (Pattern Recognition)
F.2.2 (Nonnumerical Algorithms and Problems)
H.3.3 (Information Search and Retrieval)
KeywordsMustererkennung; Boyer-Moore; Wortsuche
Abstract

Quicksearch ist eine neue Variante des Algorithmus BoMo von Boyer und Moore zur Mustersuche in Texten. Sie ist bei Texten in natürlichen Sprachen, das heißt solchen mit relativ großen Alphabeten, und bei der Suche nach relativ kurzen Mustern den bisher bekannten BoMo-Varianten ebenbürtig, übertrifft sie aber bei langen Mustern und kleinen Alphabeten, wie sie bei der Suche nach Genetischem Code vorkommen, um einen Faktor von ca. 1.25 bei der Musterlänge 10 und bis zu einem Faktor > 2 bei Mustern ab der Größe 40.

QuickSearch is a new variant of BoMo, the Boyer-Moore algorithm for pattern matching in strings. For strings with relatively large alphabets such as natural-language texts and for short patterns, it matches with presently known BoMo variants; for long patterns and short alphabets as do occur in Genetic Code, it surpasses these variants by a factor 1.25 at pattern length 10, and up to a factor > 2 for patterns of length greater 40.

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