Regex auf riesige Texte

Hallo Leute,

weiß jemand von Euch, wie ich einen Regulären Ausdruck auf einen Text anwenden kann, der größer als 2 Gigabyte ist?
Die Regex Klasse unterstützt ja nur Strings als Input und die können nunmal nicht beliebig groß sein. Eine Regular Expression kann man daher nicht direkt auf einen Stream loslassen. Was mache ich aber, wenn ich eine beliebige Regex auf eine beliebig große Textdatei anwenden muß? Die Regex nur auf Teile des Textes loszulassen ist nur möglich, wenn die Regex nicht nach Textanfang oder Textende sucht...

Die Grenze 2GB ist ja auch nur die theoretische Grenze. Praktisch dürfte sie deutlich kleiner sein, da man selbst einen 1GB großen Text wohl kaum laden kann (OutOfMemoryException).
Selbst 200MB große Texte würde ich eher ungern komplett in den Speicher laden um sie zu prüfen, denn bei mehreren parallelen Anfragen würde ich irgendwann auch wieder zu einer OutOfMemoryException kommen.
Das eine Regex auf einem Stream sicher deutlich langsamer arbeiten würde ist klar, aber wer mit so riesigen Texten arbeitet, erwartet auch nicht blitzschnelle Prüfung...

Das Problem ist für mich im Moment nur theoretischer Natur, da so große Texte wohl eher selten vorkommen und viele parallele Anfragen auch nicht ganz so wahrscheinlich sind, aber wenn es eine Lösung gibt, wäre das natürlich schön...

Gruß und vielen Dank schonmal für Eure Antworten
T-Man

du könntest es so machen:

immer nur 500 zeichen aus dem stream lesen, einen string erstellen, der aus den vorherigen 500 zeichen besteht, und aus den gerade gelesenen zeichen. regex anwenden, und ergebnisse merken. weitere 500 zeichen einlesen und mit den vorherigen 500 verbinden .....

Das Problem bei der Variante ist, das etwaige Treffer, die genau an den Stringübergängen sind (zwischen den 500er Blöcken) nicht getroffen werden vom Regex, da es eben nicht das Pattern erfüllt (durch den Abbruch).

Was mache ich aber, wenn ich eine beliebige Regex auf eine beliebig große Textdatei anwenden muß?

In dem Fall fällt JAck30lena's Vorschlag weg, da es ja auch ein RegEx sein kann der z.B. ein 1794 Zeichen langes Match finden kann es aber auf die vorgeschlagene Weise nicht finden würde.

Ich würde sagen wer einen beliebigen RegEx auf einen beliebig langen Text anwenden will braucht halt genug RAM oder Auslagerungsdatei um sicherzustellen das nichts übersehen wird.

Hallo Femaref,

nein. deswegen nehme ich die vorigen 500 zeichen um genau diese problem zu vermeiden.

Hallo Bakachan,

wenn man erwartet, das der match evtl 2000 zeichen lang sein könnte, dann ließt man eben 2000 zeichen pro durchgang ein. die 500 zeichen habe ich jetzt einfach mal so festesetzt.

mir ist klar, das wenn man ein derartigen regexausdruck hat, das x zeichen zwischen zwei gesuchten bedingungn haben darf, das es in diesem fall nciht funktinieren würda, aber da könnte man das regex vorher umbauen (z.b. in 2 teile zerhacken) und wenn teil 1 erfüllt ist, z.b. eine variable setzen das teil 1 erfüllt ist und dann auf teil 2 warten, und erst bei erfüllung einen match registrieren.

Oh, hast Recht. Sorry.

Hallo T-Man,

wie intensiv machst du denn von den Fähigkeiten des Regex Gebrauch?

Am besten wäre es meiner Ansicht nach, wenn du einen Algorithmus finden würdest, der das komplette Einlesen überflüssig machen und das zeichenweise Durchgehen ermöglichen würde; dass du also auf Regex verzichten kannst. IMHO machen das auch Parser von Skriptsprachen usw. so.

Moin!

Ich möchte jede beliebige Regex anwenden können.
Es geht um ein DMS. Die Leute sollen beliebige Dateien reinschmeissen können. Aus denen wird der Text extrahiert. Später soll man die Möglichkeit haben mit beliebigen Regex nach Texten zu suchen.
Der Normaluser wird nur nach worten suchen, weil er Regex nicht kann. Für den bräuchte ich also keine Regex. Mir geht es aber um den Poweruser, der Regex versteht und es auch beliebig anwenden können soll.
Der Poweruser kann dann auch für den Normaluser komplexe Suchabfragen erstellen, die der dann anwenden kann.
Wenn ich auf regex verzichte, muss ich auf Dauer alles mögliche an Suchmöglichkeiten hinzufügen, also viel programmieren, worauf ich gerne verzichte...

GRuß
T-Man

ich fürchte, das du wohl entweder das speicherproblem in kauf nimmst oder einiges an logik implementieren musst, um die beliebige anzahl an zeichen zwischen 2 oder mehr bedingungen zu ermöglichen.

Freien regex Code, den ich anpassen und benutzen könnte gibt es wahrscheinlich nicht!? Ich könnte ja mal Bill fragen, ob ich die Regex von .net erweitern darf 😉

deine methode bekommt doch den pattern. und den musst du nur noch parsen...

der code von regex wird dir nichts nützen. aber wenn du ihn dir ansehen willst, dann lade dir die sourcen vom framework runter.

Nur noch parsen: Genau das ist es ja, das Parsen. Im .net Framework ist so ein Parser drin. Wenn ich den Code umschreiben könnte, so dass er auch auf einem Stream funktioniert, dann hätte ich genau das, was ich benötige...
Ich schätze, den .net Code darf ich mir zwar ansehen, aber wohl kaum modifiziert verwenden...

T-Man

ich denke, das du nicht verstehst was ich meine.

selbst wenn du die sourcen direkt bei microsoft ändern dürftest, würde es auf einem stream NICHT funktionieren, da regex der gesamte string bekannt sein muss.

die einzige möglichkeit ist, den vorher zu parsen und eine eigene logik drum herum zu bauen, damit man mit dem beliebig vielen zeichen zwischen bedingungen kein problem mehr hat. aber das geht so auch ganz gut. kostet nur ein wenig aufwand.

Ich denke nicht, dass der Parser unbedingt den ganzen Text auf einmal im Speicher benötigt. Der Parser geht den Text ja zeichenweise durch. Er könnte also jedes Zeichen einzeln aus dem Stream abrufen. Und im Stream kann man hin und her "spulen", ohne den kompletten Stream im Speicher haben zu müssen.

ok da hast du recht. aber warum wehrst du dich so gegen meinen vorschlag? ^^

Ich sehe nicht, wie das für beliebige Regex funktionieren soll. Ich müsste die Regex erstmal selber zerlegen etc.
Das scheint mir sehr viel Aufwand zu sein. Beinahe soviel Aufwand, wie selber einen Parser zu schreiben.

Vielleicht habe ich aber auch Dein Beispiel noch nicht richtig verstanden.
Hast Du mal ein konkretes simples Beispiel?

es geht doch nur um die Quantoren. hier musst du eine logik implementieren.

du zerlegst das pattern seppariert nach denen.

simples beispiel: "a\w*a" -> match bei "asdfa" kein match bei "asdf"

also zerlegst du das pattern in "a" und "a"

dann gehst du in den stream und schaust ob bedingung 1 "a" erfüllt ist und hast schon den anfang des matches. wenn ja dann suchst du im stream weiter nach bedingung 2. wenn diese dann werfüllt ist, hast du das ende des matches.

zum schliss holst du dir den gesamten vermeintlichen match heraus und testest den gegen das originalpattern.

Vielleicht könntest du die genannte Möglichkeit so anwenden (ist jedoch immer noch nicht ein vollwertiger Ersatz):

• Zeichen 0 bis 200.000 (das dürfte Regex schaffen)
• Zeichen 100.000 - 300.000 (überlappten Teil etwas übertrieben...)
• Zeichen 200.000 - 400.000
• ...

mfg
webstarg

Edit: Länger als 100.000-Zeichen wird ein Suchtreffer in der Regel nicht sein. 😉 Hoffentlich.

Ich kann das Pattern leider nicht einfach dort zerlegen, wo Quantoren vorkommern, da es nämlich Klammern gibt, die beachtet werden müssen. Außerdem müsste ich wohl auch zwischen greedy und lazy unterscheiden. Dann gibt es noch das Oder...
Und vielleicht gibt es (z.B. in Zusammenhang mit Lookaround) noch weitere Probleme, die mir gerade nicht einfallen, die zu beachten wären. Ich müsste also zunächst alle Möglichkeiten von Regex durchgehen und käme am Ende wahrscheinlich zu einer sehr komplexen Logik, die der des Parses nahe kommt...

dann müssen deine user mit einem hohen speicherverbrauch auskommen.

ps: die idee von webstarg finde ich auch nicht schlecht. evtl könnte man das ganze ja parametrierbar halten.
a: ganze datei komplett einlese
b: nur buffergröße x verwenden (wobei die buffergröße ja einstellbar sein kann)

so könnte man für komplexe regex varianten, wo man mir einem ganz großen treffer rechnet, die ganze datei einlesen und für die eher simplen pattern könnte man nur einen kleineren buffer nehmen.

Vielleicht könntest du die genannte Möglichkeit so anwenden (ist jedoch immer noch nicht ein vollwertiger Ersatz):

• Zeichen 0 bis 200.000 (das dürfte Regex schaffen)
• Zeichen 100.000 - 300.000 (überlappten Teil etwas übertrieben...)
• Zeichen 200.000 - 400.000
• ...

mfg
webstarg

Edit: Länger als 100.000-Zeichen wird ein Suchtreffer in der Regel nicht sein. 😉 Hoffentlich. Hm, da fällt mir folgendes Pattern ein:

.*+Anhang

Also alles vom Anfang, bis zum letzten Auftreten des Wortes Anhang. Das kann sehr viel werden.
Ein beliebiger Regulärer Ausdruck kann auch beliebig lange Treffer haben...
Und ich möchte nichts einschränken.

deswegen kann dan nder user selbst entscheiden ob er einschränkungen zwecks performance machen möchte.

Vielleicht sollte ich mir tatsächlich den .net Code vornehmen und ihn so erweitern, dass Regex auch mit Streams umgehen kann. Dann könnte ich den Code an Microsoft schicken und hoffen, dass die den im nächsten Framework einbauen.

😁

Ich denke, ich werde wohl dokumentieren, dass Regex nicht auf beliebig grosse Texte anwendbar ist und evtl. die Möglichkeit anbieten eine Regex auf die Ersten x bzw. die letzten x Zeichen vorzunehmen... das muss dan reichen.

Hallo T-Man,

kein einzelner Text wird größer sein als 2GB. Selbst ein eng beschriebenes Buch mit 10000 Seiten (mit je 100 Zeilen à 150 Zeichen) hat in Unicode nicht mehr als 300MB. Daher stellt sich dein Problem gar nicht!

Im Gegenteil. Es wäre sogar falsch, mehrere Texte in einen String zu packen und dann mit Regex womöglich den Anfang in einem und das Ende in einem ganz anderen Text zu matchen.

Ich fürchte aber, dass Regex bei einer sehr großen Gesamtmenge von Text zu langsam wird und du stattdessen mit Indexierung o.ä. arbeiten musst.

herbivore

Ich habe vor sowohl einen Index aufzubauen, als auch eine völlig freie Regex Suche anzubieten. Wenn jemand riesige Texte mit Regex durchsuchen möchte, dann muss er damit leben, dass das länger dauern kann. Sucht er bloß einzelne Worte, geht es fixer...

Ich hätte vielleicht auch mal rechnen sollen...
Wer tatsächlich vor hat riesige Texte zu Speichern und diese auch per Regex durchsuchen zu lassen, der muss sich auch die 3GB Arbeitsspeicher gönnen und davon soviel wie möglich meiner Applikation gönnen...
Die Wahrscheinlichkeit, dass mehrere Anwender eine Suche starten, bei der gleichzeitig mehrere riesige Texte geladen werden müssen und es dabei zu einer OutOfMemoryException kommt ist sehr gering. Und dann kann man es ja einfach nochmal versuchen...

Vielen Dank nochmal für die Anregungen
T-Man

Nur mal so als anregung, so eine Volltest suchmaschine gibt es schon als Opensource.

Nennt sich http://www.codeproject.com/KB/aspnet/DotLuceneSearch.aspx
Kann schon von haus aus mit einigen dateiformaten umgegen.

Und da gibt es einiges als erweiterungen zu.
http://www.codeproject.com/KB/aspnet/cuyahogafulltext.aspx