Geschwindigkeit und Effizienz

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Wenn Effizienz ein Thema bei traditionellen NFAs ist (und es ist eines, sobald Backtracking involviert ist), dann ist es erst recht eines bei einem POSIX-NFA, weil da noch viel mehr Backtracking möglich ist. Eine POSIX-NFA-Maschine muss wirklich jeder möglichen Permutation der Regex nachgehen. Einige Beispiele unter Die Kunst, reguläre Ausdrücke zu schreiben zeigen auf, wie ein unvorteilhaft geschriebener regulärer Ausdruck extreme Geschwindigkeitseinbußen erleiden kann.

Effizienz bei DFAs

Die Textsteuerung bei DFAs ist eine hervorragende Möglichkeit, die mühsamen und zeitraubenden Backtracking-Operationen zu vermeiden. Die Geschwindigkeit rührt daher, dass alle möglichen Treffer gleichzeitig verfolgt werden. Wie wird dieses magische Verhalten erreicht?

NFA: Theorie und Praxis Die Bedeutung von NFA in der Mathematik unterscheidet sich ein wenig von dem, was in der Informatik NFA-Regex-Maschine genannt wird. Mathematisch betrachtet sollten eine NFA und eine DFA exakt den gleichen Text erkennen, und sie sollten auch sonst die gleichen Eigenschaften haben. In der Praxis aber hat der Wunsch nach mehr Features und nach ausdrucksstärkerem regulären Ausdrücken zu einer deutlichen Unterscheidung geführt. Wir werden noch einige weitere sehen, aber der wichtigste Unterschied ist die Unterstützung oder Nicht-Unterstützung von Rückwärtsreferenzen. Für den Programmierer ist es relativ einfach, in eine (mathematisch gesprochen) echte NFA-Maschine die Fähigkeit zum Erkennen von Rückwärtsreferenzen einzubauen. Die Art, wie eine DFA aufgebaut ist, verbietet den Gedanken daran, aber bei NFAs geht das leicht. Wenn das gemacht wird, hat man zwar ein wesentlich brauchbareres Werkzeug, aber mit dieser Veränderung ist die Maschine entschieden nicht-regulär geworden (für Mathematiker). Was heißt das für die Praxis? Nun, vielleicht sollte man die Maschine nicht mehr NFA nennen, und man müsste grundsätzlich von »nicht-regulären Ausdrücken« sprechen, denn das beschreibt, mathematisch gesehen, die neue Situation. Niemand tut das, der Name »NFA« ist geblieben, auch wenn die Implementation – für Mathematiker – gar keine NFA mehr ist. Und was bedeutet das für Sie als Benutzer von regulären Ausdrücken? Absolut gar nichts. Als Benutzer sind Sie nicht daran interessiert, ob die Maschine in der Mathematik nun als regulär, nicht-regulär, unregulär, irregulär oder unkontrolliert bezeichnet wird. Wenn Ihnen klar ist, was Sie von der Maschine erwarten können (das wird in diesem Kapitel behandelt), wissen Sie alles, was es zum Gebrauch von regulären Ausdrücken zu wissen gibt. Wer sich mehr für die theoretischen Aspekte von regulären Ausdrücken interessiert, sei auf das Kapitel 3 in Aho, Sethi und Ullman, Compilers – Principles, Techniques, and Tools (Addison-Wesley, 1986, auf Deutsch Compilerbau), verwiesen, das wegen der Illustration auf dem Cover auch das »Drachenbuch« genannt wird.

Ein DFA benutzt einiges an Rechenleistung und Speicher, bevor er sich mit dem String befasst. Dabei wird die Regex gründlicher (und auf andere Art) als bei einem NFA analysiert. Es wird intern eine »Karte« oder eine Entscheidungsstruktur aufgebaut, die Auskunft über den Vorgang gibt: »Wenn dieses oder jenes Zeichen ankommt, gehört es zu diesem oder jenem möglichen Treffer.« Wenn nun aus dem String Zeichen eingelesen werden, folgt der DFA einfach den vorgezeichneten Wegen auf dieser Karte.

Der Aufbau dieser Karte kann manchmal einige Zeit und einiges an Speicher in Anspruch nehmen. Wenn sie einmal für eine bestimmte Regex aufgebaut ist, kann das Resultat für eine unbegrenzte Menge Text verwendet werden.

Es ist wie beim Aufladen der Batterien eines Elektroautos. Das Auto steht in der Garage, ans Ladegerät angehängt. Wenn man es aber braucht, ist die Energie sofort da, ohne Anlasser, Warmfahren des Motors oder gar Vorglühen.

Diesen einmaligen Aufwand vor dem eigentlichen Matching (einmal pro Regex) bezeichnet man als Kompilierung der Regex. Ein DFA baut dabei die genannte interne Karte auf. Auch bei einem NFA gibt es eine Kompilierung, auch hier wird eine interne Darstellung der Regex aufgebaut, aber bei einem NFA ähnelt diese interne Darstellung viel eher einem kleinen Programm, das die Maschine später ausführt.

  

<< zurück

vor >>