Technischer Bericht TR-1993-14

Bibliograph.
Daten
Ziegler, Bernhard: QuickSearch : ein schneller Algorithmus zur Mustersuche in Zeichenfolgen.
Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1993/14.
11 Seiten, deutsch.
CR-Klassif.I.5 (Pattern Recognition)
F.2.2 (Nonnumerical Algorithms and Problems)
H.3.3 (Information Search and Retrieval)
KeywordsMustererkennung; Boyer-Moore; Wortsuche
Kurzfassung

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.

Volltext und
andere Links
HTML (aus PostScript generiert)
Abteilung(en)Universität Stuttgart, Institut für Informatik, Betriebssoftware
Eingabedatum23. April 1996
   Publ. Informatik