frage zum suchen in grossen text-dateien

folgende frage:

bei einer aufgaben-stellung wie

- es sind grosse (mehrere 100MB) textdateien nach suchmustern zu scannen
(suchmuster sind reine strings oder regulaere ausdrücke (ggf. multi-line)
- es ist c++ mit standard libs (STL, BOOST) ggf. QT zu verwenden
- suchanfragen bei obiger datei-groesse duerfen auf einem "normalen"
pc (3000+GHz CPU, 1GB Ram) nicht zu lange dauern (im sekunden-bereich)

Hat jemand schonmal erfahrungen zu solch einem vorhaben gesammelt ?
Interessant waeren fuer mich herangehensweisen, die obiges moeglicht
elegant/effizient loesen koennen. ich moechte mir einen ueberblick
ueber die moeglichkeiten mit ggf. vor- nachteilen verschaffen.
konkret geht es um ein vorhaben, ggf. einen logfile scanner mit obigen
anforderungen zu schreiben.

vielen dank vorab.

Das haengt stark davon ab, wie die Datei aufgebaut/formatiert sind. Wenn das ne ordentlich Struktur hat und das Suchmuster klar definiert ist, dann geht das ruckzuck. Ein Logfile sieht klar strukturiert aus.

ok, jedoch im speziellen bei regulaeren ausdruecken, die ggf. im multi-line
modus gesucht werden sollen, kann das vielleicht schon etwas schwieriger werden.

was mich interessieren wuerde (besonders beim multi-line scanning, also bei der suche nach mustern, die sich ueber mehrere zeilen erstrecken) wie man da dann das file-handling umsetzt:

datei-inhalt muesste erstmal in eine geeignete datenstruktur eingelesen werden, die dann der entsprechenden such-engine uebergeben werden kann.
bei mehreren 100MB einen riesen-string draus zu machen erscheint mir bedenklich.

ich bin auf der suche nach bekannten (standard) mustern, wie man sowas machen koennte.

Darfst du vorverarbeiten?
(Vorverarbeitung heißt du kriegst die Textdatei und konvertierst die in irgendwas. Nachdem du damit fertig bist beginnt die Zeitmessung und du bekommst Suchanfragen. Ohne Vorverarbeitung heißt die Zeitmessung startet mit der Übergabe der Textdatei.)

Wenn du nicht Vorverarbeiten darfst und der Inhalt der Textdatei völlig unbekannt ist bietet sich der KMP an. Das ist quasi der Standard-Stringmatcher. Er kann nach beliebig vielen Suchmustern inklusive einigen (allen?) regulären Ausdrücken in O(n) suchen.
Er ist nur durch Boyer-Moore-artige Algorithmen zu schlagen, wenn es sehr wenige Treffer, ein großes Alphabet und nur eine Suchanfrage gibt.
Wenn der Inhalt der Textdatei teilweise bekannt ist (Es ist eine Logdatei der Form ...) lässt sich wahrscheinlich darauf optimieren.

Mit Vorverarbeitung bietet sich eine Indexstruktur an (reverse index oder so), wo du für jedes Wort oder besser für jede mögliche Suchanfrage eine Liste der Textstellen angibst und bei der Suchanfrage einfach nur in der Liste den Eintrag mit den Ergebnissen abliest.

Ich verstehe nicht was du mit Multiline Scanning meinst. Das Newline-Zeichen ist ein Zeichen wie jedes andere auch. Oder steht in der Aufgabenstellung dass das besonders behandelt werden muss?

Beim File-Handling würde ich einfach etwa ein kB Speicher nehmen, per fread die Datei kB-weise einlesen und den KMP drüber rattern lassen. Wenn du noch ein Bienchen willst, kannst du 2 Threads machen und den einen einlesen lassen während der andere auswertet (2 Buffer). Wahrscheinlich bringt das aber wegen Readahead-Tricks des Betriebssystems eh nichts. (und meist werden bei solchen Aufgaben nicht die Echtzeit, sondern die Rechenzeit gemessen, sodass Multithreading kontraproduktiv ist)

Ein paar Fragen, um das genauer beantworten zu können:
Welchen Umfang hat das Alphabet, aus dem die Textdateien bestehen?
Welche Länge haben deine Suchpattern? (ungefähr)
Wieviele Pattern möchtest du suchen?

Werner Salomon

pepe75 schrieb:

bei einer aufgaben-stellung wie

- es sind grosse (mehrere 100MB) textdateien nach suchmustern zu scannen
(suchmuster sind reine strings oder regulaere ausdrücke (ggf. multi-line)

Hallo pepe75,

also bei der Größe lohnt es sich auf die streambuf-Ebene abzusteigen. Wie das geht, da gibt es hier schon ein Beispiel im Forum. Hier gibt es noch ein paar Erläuterungen dazu.
Für einen eine einfachen 'grep' (suche eine Zeichenfolge) kann man dann einen search-Algorithmus bauen. Der std::search setzt leider Forward-Iteratoren voraus, aber wenn man direkt aus einer Datei liest, so hat man nur istream_buf-Iteratoren - also Input-Iteratoren - zur Verfügung. D.h. diesen search müsste man sich selber schreiben.

So nach den ersten Tests komme ich auf ca. 1s/100MB Suchgeschwindigkeit - schnell genug?.

In wie weit das std::regex mit input-Iteratoren zurecht kommt weiß ich (noch!) nicht.

Gruß
Werner