RegEx-Hardcore: Lange laufende Prüfungen

[Jürgen Auer]

Ein kleines Rätsel zu Weihnachten, in den letzten Tagen in der praktischen Arbeit darüber gestolpert:


Man hat ein Dokument. Dieses enthält eine Html-Tabelle, links stehen Beschriftungen, rechts der Inhalt.

Der Inhalt soll extrahiert werden.

Grundidee: Man führt einen RegEx mit diversen Gruppen aus. Anschließend stehen die Ergebnisse in den Gruppen:

Start:

CODE _rE = New RegEx("(?is:""abcd"">(?'subId'.+?), (?'Hauptname'.+?)</td>" & _
".*?>Name</td>.*?<td.*?>(?'Name'.*?)</td>" & _
".*?>Strasse/Postf\.:</td>.*?<td.*?>(?'Strasse'.*?)</td>" & _
".*?>PLZ, Ort: </td>.*?<td.*?>(?'PLZ'.*?) (?'Ort'.*?)</td>" & _
".*?>Telefon: </td>.*?<td.*?>(?'Telefon'.*?)</td>" & _
".*?>Telefax: </td>.*?<td.*?>(?'Telefax'.*?)</td>" & _
".*?>E-Mail: </td>.*?<td.*?>(?'EMail'.*?)</td>" & _
".*?>Homepage: </td>.*?<td.*?><a href=""(?'Homepage'.*?)"".*?</td>)")



(?is:...) setzt die SingleLine-Option, damit der Punkt als Suchmuster auch Zeilenumbrüche findet.

Die Ausdrücke & _ am Zeilenende sind lediglich Stringverkettungen innerhalb von VB.NET, tun also inhaltlich nichts zur Sache. "abcd" ist im Quelldokument ein Attributwert eines Attributes, steht dort in Hochkommata, die müssen in VB.NET doppelt maskiert werden.

Ansonsten:

QUOTE ".*?>Name</td>.*?<td.*?>(?'Name'.*?)</td>" & _

Finde minimal beliebige Zeichen (.*?), dann schließende Spitzklammer, das Wort Name gefolgt von </td>, minimaler Zwischenraum, <td, dann folgen irgendwelche Attribute, dann eine schließende Spitzklammer. Das danach bis </td> packe in die Gruppe 'Name' usw.

Einerseits: Passt die Quelldatei zu dieser Definition, funktioniert alles - die Ausführungszeit ist vernachlässigbar.

Andererseits: Fügt man nach dem Text ein Leerzeichen (oder eines mehr als dasteht) ein

Alt:

CODE ".*?>Strasse/Postf\.:</td>.*?<td.*?>(?'Strasse'.*?)</td>" & _

Neu:

CODE ".*?>Strasse/Postf\.: </td>.*?<td.*?>(?'Strasse'.*?)</td>" & _


dann wird nichts gefunden. Das alleine wäre noch kein Problem. Das Problem liegt darin, daß das eingefügte Leerzeichen bei Name zu einer Laufzeit von 10 Sekunden, bei Strasse/Postf zu einer Laufzeit von 18 Sekunden führt - das terminiert also nicht mehr innerhalb einer realistischen Zeit. Je später die Nicht-Übereinstimmung, umso länger die Laufzeit. Tatsächlich kommen noch mindestens zehn Zeilen dazu, das Problem potenziert sich also.


Rätsel: Wie läßt sich das Problem - durch einen verbesserten RegEx - lösen?

 

[profo]

Das Problem dürften die vielen ".*?" sein, Du bekommst damit einen riesigen Backtracking-Graphen.

Das kannst Du vereinfachen, indem Du den Punkt Stern jeweils genau spezifizierst. Das kann dann sinngemäß zum Beispiel ein \s* (whitespace), ein [^<]* ("bis zum nächsten Kleiner-Zeichen&quot, ein [^"']* ("bis zum nächsten einfachen oder doppelten Anführungszeichen) oder dergleichen sein.

Die Parse-Zeiten sollten sich dann von 18 Sekunden auf etwa 18 Millisekunden verbessern

 

[Jürgen Auer]

QUOTE (profo @ Fr 25.12.2009, 16:05)Das Problem dürften die vielen ".*?" sein, Du bekommst damit einen riesigen Backtracking-Graphen.

Das kannst Du vereinfachen, indem Du den Punkt Stern jeweils genau spezifizierst. Das kann dann sinngemäß zum Beispiel ein \s* (whitespace), ein [^<]* ("bis zum nächsten Kleiner-Zeichen&quot, ein [^"']* ("bis zum nächsten einfachen oder doppelten Anführungszeichen) oder dergleichen sein.

Die Parse-Zeiten sollten sich dann von 18 Sekunden auf etwa 18 Millisekunden verbessern

In der Theorie hatte ich mir das zunächst heute nachmittag auch gesagt - getan, geändert - hurra, die negative Prüfung war unter einer Sekunde.

Dumm nur, daß da ein kleiner Fehler drin war - die positive Prüfung scheiterte nämlich auch.

Alt:


CODE ".*?>PLZ, Ort: </td>.*?<td.*?>(?'PLZ'.*?) (?'Ort'.*?)</td>" & _


Zwischenzustand:


CODE ".*?>PLZ, Ort: </td>.*?<td[^>]>(?'PLZ'.*?) (?'Ort'.*?)</td>" & _


Korrekt:


CODE ".*?>PLZ, Ort: </td>.*?<td[^>]*?>(?'PLZ'.*?) (?'Ort'.*?)</td>" & _


Das war schneller - 4 Sekunden bei fehlerhafter Telefonzeile. Aber schon die folgende Telefax-Zeile brauchte erneut etwa 21 Sekunden.

Ersetzt man sehr viel mehr, dann kommt man auf Werte unter 0,1 Sekunden, wobei alles unter 1 - 5 Sekunden unproblematisch ist. Allerdings steigt dann der Codierungsaufwand massiv an.

Deshalb tendiere ich inzwischen zu einer ganz anderen Lösung:

Nicht mehr ein RegEx, sondern einer pro Zeile, der immer dort weitermacht, wo der alte aufgehört hat.
Damit lassen sich die Prüfausdrücke relativ schnell erstellen. Der Rest sind Schleifen.

 

[chricke]

ich würde sowas nie selber mit regex machen...

mit welcher programmiersprache machst du das denn? da gibts doch bestimmt einen (html-/)xml-parser der dir die möglichkeit gibt den dom ordentlich zu parsen und dann direkt auf die elemente zuzugreifen?

 

[Jürgen Auer]

QUOTE (chricke @ Fr 25.12.2009, 23:57)ich würde sowas nie selber mit regex machen...

mit welcher programmiersprache machst du das denn? da gibts doch bestimmt einen (html-/)xml-parser der dir die möglichkeit gibt den dom ordentlich zu parsen und dann direkt auf die elemente zuzugreifen?

In der Theorie würde ich so etwas auch nie freiwillig mit RegEx machen, sondern zu Xml greifen.


In der Praxis sind die Seiten beliebig schräg - sprich: Das würde schon beim Einlesen knallen.

Ich brauche allerdings eine möglichst nicht knallende, möglichst fehlertolerante Lösung

 

[chricke]

in python gibts mit beautifulsoup einen parser der auch "schräge" seiten ordentlich parsen kann - zumindest ist mir damit noch nichts unter gekommen was der nicht hätte verkraften können...

vielleicht gibts dazu was vergleichbares in der programmiersprache die du verwendest?

 

[Sascha Ahlers]

Und was ist, wenn erst ein Tidy drüber läuft und dann mit XML-Parser gearbeitet wird?

 

[Jürgen Auer]

Die Programmierumgebung ist - wie im ersten Thread erwähnt - .NET.

Beide Vorschläge - beautifulsoup / Tidy - nutzen m.E. nach nur begrenzt.

Denn es werden ja die Suchphrasen 'Name' usw. benötigt. Gefunden werden muß dann das, was in der Zelle danach kommt.

Ferner soll der Code stark parametrisierbar sein. D.h., das ganze ist eine Funktion, die RegEx werden als Parameter übergeben und sollen außerhalb möglichst leicht generierbar sein.

Die jetzige n-Zeilen / n-RegEx - Lösung läßt sich 'fast schon' mit Copy/Paste bereitstellen.

 

[profo]

QUOTE (Jürgen Auer @ Fr 25.12.2009, 21:15)
CODE ".*?>PLZ, Ort: </td>.*?<td[^>]*?>(?'PLZ'.*?) (?'Ort'.*?)</td>" & _

... Ersetzt man sehr viel mehr, dann kommt man auf Werte unter 0,1 Sekunden, wobei alles unter 1 - 5 Sekunden unproblematisch ist. Allerdings steigt dann der Codierungsaufwand massiv an.


Noch mal kurz zur Theorie: mit jedem mehrfachen .* *potenzierst* Du die Suchdauer bis zu einem erfolgreichen Match - mehr oder weniger. Meide die deshalb unbedingt, schon allein um Deinen CO2-Verbrauch durch hohe Rechnerlast zu minimieren

Der Codierungsaufwand sollte dann eigentlich aber nicht steigen. Speichere einfach ein paar passende Subpatterns in eigenen Variablen, damit vermeidest Du Copy&Paste-Fehleingaben. Dann hättest Du am Ende so etwas in der Art (Pseudocode):

CODE
$tdAuf = '\s*<td[^>]*>\s*';
$tdZu = '\s*</td>\s*';
$bisAuf = "[^<]+?";
$bisWS = "[^<\s]+?;
$pattern = $tdAuf."PLZ, Ort:$tdZu$tdAuf(?'PLZ'$bisWS)\s*(?'Ort'.$bisAuf)$tdZu



Wie gesagt, nur zur Verdeutlichung. Wahrscheinlich findest Du dann noch praktischere Subpatterns...

 

[Jürgen Auer]

QUOTE (profo @ Sa 26.12.2009, 20:21)mit jedem mehrfachen .* *potenzierst* Du die Suchdauer bis zu einem erfolgreichen Match - mehr oder weniger.


Das ist klar. Aber ich muß, wenn ich auf .*? verzichte, detailliert codieren - zumindes WhiteSpaces, Html-Elemente und schließende Klammern (als [^>] bei Startelementen bis nach dem Attribut).


QUOTE (profo @ Sa 26.12.2009, 20:21)Speichere einfach ein paar passende Subpatterns in eigenen Variablen, damit vermeidest Du Copy&Paste-Fehleingaben.


Das nutzt nichts. Denn die RegEx werden später effektiv als Feldeinträge in einer Tabelle definiert, so daß überhaupt keine Variablen zur Verfügung stehen. Das soll - durch solche Einträge in Tabellen - später erweiterbar sein. Es soll nicht bei jeder Änderung neu kompiliert werden müssen.


Ich bin aus zwei anderen Gründen inzwischen endgültig auf die Lösung mit vielen RegEx umgeschwenkt.

Zum einen ist es nicht auszuschließen, daß eine ganze Zeile fehlt, daß also nicht bsp. Telefax links notiert ist, die Zelle rechts einfach leer ist, sondern daß das Wort Telefax komplett fehlt. Folglich müßte man alle Zeilen mit {0, 1} o.ä. markieren - das verteuert. Bei einer Array-Lösung macht man an der letzten Fundstelle weiter.

Zum anderen ist die Fehleranfälligkeit bei der Version mit einem einzigen RegEx enorm. Stimmt da irgendetwas nicht, wird insgesamt nichts gefunden - dann sucht man sich erst einmal dusselig. Bei der Array-Lösung sind die Suchausdrücke erheblich übersichtlicher, da man mit


CODE >Telefax:</td>\s*?<td[^>]*?>(?'Telefax'.*?)</td>


starten kann und - angesichts der Kürze - dann auch problemlos .*? nutzen kann. Und ist irgendwo ein Verschreiber drin, wird alles davor und danach korrekt gefunden, damit ist die kritische Stelle auch schnell eingegrenzt.


Sprich (Erkenntnis nach diesem Thread): Es gibt Fälle, wo zu lange und zu komplexe RegEx noch an anderen Stellen zu Problemen führen, dann lieber splitten.