(sehr) große Datei SCHNELL nach mehreren Strings durchsuchen

[wth]

Hallo,

Ich habe eine große Datei (2 GB oder größer) und versuche gerade diese nach mehreren Zeichenketten zu durchsuchen.
Das ganze muss möglichst schnell sein.

So mache ich es bisher:

1. Lese ich einen Block aus der Datei. (~20000 Zeichen oder mehr; "BlockRead()")
2. Splitte/Explode ich diesen Block in ein String-Array mit dem Delimiter CRLF.
3. Sortiere ich das Array. ("Quicksort()")
4. Suche ich die Zeichenketten mittels einer Binären-Suche, da das Array ja sortiert ist. (das geht auch noch recht schnell)

Das Auslesen und das Suchen geht recht schnell, nur das Aufsplitten und das Sortieren des Arrays verbrauchen viel zu viel Zeit. (hauptsächlich wohl das Splitten)
Ich habe schon versucht den Block mit Pos() zu durchsuchen und die Datei zeilenweise auszulesen und zu vergleichen, ist aber beides einfach zu (viel) langsam.
Die Datei ist ganz einfach aufgebaut, jede Zeile eine Zeichenkette getrennt durch CRLF's.
Ich habe schon mehrere Split/Explode Varianten ausprobiert, auch die optimierte Version hier aus dem Forum.
Man kann die Datei auch nicht komplett in den Speicher laden, dafür ist sie zu groß.
Bisher lese ich die Datei mit den Pascal-Dateiroutinen, habe es aber auch schon mit FileStream versucht, ist aber genauso langsam. :oops:

Hat jemand noch ne Idee, wie das vielleicht schneller gehen könnte? :idea:

Danke schonmal.

[alzaimar]

"grep" ist ein Kommandozeilentool, das das sehr schnell macht.

Ansonsten wäre Quicksearch, Boyer-Moore o.ä. etwas für Dich. Dabei musst Du allerdings deine Strategie überdenken, denn wenn du einfach Blockweise einliest, überliest du die Zeichenketten, die am Ende des einen Blocks anfangen und am Anfang des nächsten Blockes aufhören.

Eine sehr schnelle Stringmatching-Suche findest Du bei der 'FastString' Sammlung oder dem FastCode-Projekt (einfach mal googeln).

[Bernhard Geyer]

Ich glaube es ist schon länger her, aber in einer c't stand einmal ein Artikel über Mustersuche. Ich glaube es war dieser Artikel

[SirThornberry]

Ich glaube bei der ursprünglichen Methode fängt der Performanceverlust bei Schritt 2 an. Beim Splitten werden alle Daten schon angerührt und nach einem CRLF durchsucht. Wenn man sich das 2 bis 3 mal auf der Zunge zergehen lässt weiß man wo man schon ansetzen kann. Wenn man nach einem CLRF sucht kann man auch gleich nach dem richtigen Muster suchen.
Auf jeden Fall sollten die Daten so wenig wie möglich angefasst werden, im optimalfall eben nur einmal.
Ich frage mich bei solchen Sachen immer: "wie macht man das im Alltag als Mensch"
Ich für meinen Teil würde den ersten Teil mit einem Blick erfassen und darin den Anfang des zu suchenden versuchen zu erspähen. Wenn ich den Anfang erspähe schaue ich genauer hinn, wenn ich ihn nicht erspähe wandern meine Augen auf das nächste Stück. Das gleiche würde ich dann versuchen in Quelltext zu fassen.

[wth]

Danke erstmal an alle. Ich probiere mal alles aus und melde mich dann wieder. :-D

Bis demnächst!

[Gausi]

Es gibt auch Algorithmen, um simultan nach mehreren Strings in einem Text zu suchen. Eine Variante habe ich hier mal gepostet, ein paar weitere solcher Algorithmen gibts hier.

[olee]

Ich würde auch sagen, dass es am besten ist, erst nur nach dem Anfangsbuchstaben
zu suchen, und danach erst genauer hinzuschauen.

Wenn du das nich so machst, MUSST du jeden Teil mehrmals anpacken.

Außerdem sollte es viel schneller sein, nur nach einem einzigen Byte zu suchen.

MFG

[alzaimar]

olee, schau Dir mal die von mir erwähnten Algorithmen an. Dein Ansatz ist eben der Langsamste.

[himitsu]

Bezüglich des Suchens, was interessiert dich denn da?
- nur "ist mindestens eine der Zeichenfolgen irgendwo in der Datei enthalten?"
- oder willst du auch noch wissen was davon und wo es in der Datei (Zeile oder Dateiposition/Byte) gefunden wurde?

- entspricht das Gesuchte jeweils einer ganzen Zeile und nur einem Teil einer Zeile?

- Und wird CaseSensitive gesucht?



PS:
Sortieren = alles miteinander Vergleichen
Suchen = einwas mit durchschnittlich einem Teil vergleichen

ich weiß jetzt nicht wieviele Zeichenketten du suchen mußt, aber so wie es aussieht, kann es auch schneller sein garnicht zu sortieren und direkt im unsortierten zu suchen

PSS:

Zitat:

1. Lese ich einen Block aus der Datei. (~20000 Zeichen oder mehr; "BlockRead()")

hast du auch bedacht, was passiert, wenn das Gesuchte gerade im Übergang zweier Blöcke liegt?
(also Zeichenkettenangang am Ende des einen Blocks und das Zeichenkettenende am Anfang des nachfolgenden Blocks)