Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


19. Suchen in Zeichenfolgen



Kurzer historischer Abriß

Die Algorithmen, die wir untersuchen werden, haben eine interessante Geschichte; wir wollen dazu hier einen Überblick geben, der helfen soll, die verschiedenen Methoden einzuordnen.

Es gibt einen offensichtlichen »groben« Algorithmus für die Verarbeitung von Zeichenfolgen, der weit verbreitet ist. Auch wenn er im ungünstigsten Fall eine Laufzeit besitzt, die proportional zu MN ist, führen die Zeichenfolgen, die in vielen Anwendungen auftreten, zu einer Laufzeit, die praktisch immer proportional zu M + N ist. Außerdem ist er gut an die Architekturmerkmale der meisten Computersysteme angepaßt, so daß eine optimierte Variante einen »Standard« liefert, der sich mit einem komplizierteren Algorithmus schwer übertreffen läßt.

Im Jahre 1970 bewies S. A. Cook ein theoretisches Ergebnis zu einem speziellen Typ abstrakter Maschinen, aus dem folgte, daß ein Algorithmus existiert, der das Problem des Pattern Matching in einer Zeit löst, die im ungünstigsten Fall proportional zu M + N ist. D. E. Knuth und V. R. Pratt folgten mit viel Mühe der Konstruktion, die Cook für den Beweis seines Theorems verwendet hatte (die in keiner Weise auf praktische Anwendungen abzielte), und erhielten einen Algorithmus, den sie dann verfeinern konnten, so daß sich ein relativ einfacher praktischer Algorithmus ergab. Dies schien ein seltenes und erfreuliches Beispiel für ein theoretisches Ergebnis mit unmittelbarer (und unerwarteter) praktischer Anwendbarkeit zu sein. Doch es zeigte sich, daß J. H. Morris praktisch den gleichen Algorithmus als Lösung für ein lästiges praktisches Problem entdeckt hatte, mit dem er bei der Implementation eines Texteditors konfrontiert wurde (er wollte nicht ständig in der Text-Zeichenfolge »zurückkehren«). Die Tatsache jedoch, daß ein und derselbe Algorithmus im Ergebnis zweier derart unterschiedlicher Ansätze erhalten wurde, untermauert die Annahme, daß er als eine grundlegende Lösung für das Problem betrachtet werden kann.

Knuth, Morris und Pratt gelang es erst 1976, ihren Algorithmus zu veröffentlichen, und in der Zwischenzeit entdeckten R. S. Boyer und J. S. Moore (und unabhängig von ihnen R. W. Gosper) einen Algorithmus, der in vielen Anwendungsfällen wesentlich schneller ist, da er oft nur einen Teil der Zeichen in der Text-Zeichenfolge untersucht. Viele Texteditoren benutzen diesen Algorithmus, um eine beträchtliche Verkürzung der Reaktionszeit bei der Suche nach Zeichenfolgen zu erzielen.

Sowohl der Algorithmus von Knuth-Morris-Pratt als auch der von Boyer-Moore erfordern eine gewisse komplizierte Vorverarbeitung des Musters, die schwer verständlich ist und den Einsatz dieser Algorithmen einschränkt. (Tatsächlich wird erzählt, daß ein unbekannter Systemprogrammierer den Algorithmus von Morris zu kompliziert fand, um ihn zu verstehen, und ihn durch eine »grobe« Implementation ersetzte.)

Im Jahre 1980 stellten R. M. Karp und M. O. Rabin fest, daß sich das Problem nicht so stark vom herkömmlichen Suchproblem unterscheidet, wie es zunächst schien, und schlugen einen Algorithmus vor, der beinahe ebenso einfach ist wie der grobe Algorithmus und der praktisch immer in einer zu M + N proportionalen Zeit abläuft. Außerdem läßt sich ihr Algorithmus leicht auf zweidimensionale Muster und Texte verallgemeinern, wodurch er für die Bildverarbeitung nützlicher ist als andere.

Diese Entwicklung macht deutlich, daß die Suche nach einem »besseren Algorithmus« noch immer sehr oft gerechtfertigt ist; tatsächlich ist zu vermuten, daß selbst für dieses Problem noch weitere Entwicklungen bevorstehen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]