100MB Datei nach Strings durchsuchen

jaenicke · Verfasst: Mo 19.05.08 21:29

Du hast ja in den Treffern als erste Zahl die Angabe welches Muster an der Stelle gefunden wurde. Du könntest jetzt einfach ein array of Boolean nehmen, alles auf false setzen und dann alle Treffer durchgehen und den Eintrag im Array auf true setzen für jeden Treffer. Wird ein Muster mehrfach gefunden wird es eben erneut auf true gesetzt, aber alle, die auf false noch stehen am Ende wurden nie gefunden.

Gausi · Verfasst: Mo 19.05.08 21:43

So in etwa würde ich das auch machen. Das mit dem j<>mi funktioniert auf jeden Fall nicht. ;-)

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

Hallo Leute
erstmal möchte ich mich vorstellen,
mein Name ist Karl-Heinz - und ich bin ein Delphi-Anfänger.

Auch ich hatte das Problem ca. 20000 Datensätze schnellstmöglich
durchsuchen zu müssen- deshalb ist dieser Thread genau richtig gewesen.

Ein besonderen Dank an " Gausi" für den "WuManber"...und die Erklärungen.
Das Teil ist "sauschnell" - auch bei so vielen Datensätzen.
Auch die Rückwärtssuche vom Treffer bis zum Anfang der StringListe klappt
über #13#10 einwandfrei - sodass ich darüber den Datensatz ermittlen kann.

Ich bin so begeistert,dass ich mich nun hier angemeldet habe - um
mich nochmal ganz herzlich zu bedanken.

Allerdings habe ich auch noch das gleiche Prob' wie Tristan - ich kann die
ObjectListe( TMultiTrefferList) noch nicht auslesen,sodass ich sie auch
durch eine normale StringList ersetzt habe.
Die Treffer erhalte ich aber nach Gausis beispiel.
Vielleicht hat ja jemand Lust mir auf die Sprünge zu helfen ???

mfg
karlheinz

Gausi · Verfasst: Mi 18.06.08 09:19

Ich bin mir zwar nicht sicher, ob du hier das richtige Verfahren anwendest, aber ok. Wu-Manber braucht man nicht, um viele Datensätze zu durchsuchen, sondern um einen großen Datensatz (einen langen String) nach vielen Datensätzen (einer Stringlist) gleichzeitig zu durchsuchen.

Das mit den Treffern sollte in etwa so gehen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

MeineTrefferList := TMultiTrefferList.Create;
Search_WuManber(MeinLangerString, MeineSuchStrings, MeineTrefferlist);

for i := 0 to MeineTrefferList.Count - 1 do
begin
  Memo1.lines.add('Muster '
                  + IntToStr(TTreffer(MeineTrefferList[i]).Index)
                  + ' gefunden an Position'
                  + IntToStr(TTreffer(MeineTrefferList[i]).Position)
                 );
end;

Wenn du viele Datensätze nach einem String durchsuchen willst, dann führt kaum was dran vorbei, jeden einzelnen Datensatz zu durchsuchen. Man kann das mit Boyer-Moore machen, wenn man die Vorbereitung auslagert und somit nur einmal durchführt, oder einfach mit Pos.

Edit: Upps, vergessen: :welcome:

in der Entwickler-Ecke.

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi-
danke - für die superschnelle Antwort ( passt zum Algo :-)

..)
Ja -ob das Verfahren unbedingt das Richtige ist - kann ich z.z. auch
noch nicht beurteilen.
Ich war aber auf deiner HP und habe mir die CD von deiner Diplomarbeit
gezogen- sodass ich jetzt viel probieren kann.( KLASSE )
Naja -der Algo ist auch nur superschnell- wenn man die gesamte StringList als
einen String übergibt.Hier habe ich mal mit der Suche von UltraEdit verglichen -
und komme auf gefühlte gleich-schnelle Ergebnisse.Also String direkt nach
ButtonClick gefunden.
Wesentlich langsamer wird es - wenn ich jeden String einzeln übergebe und
durchsuche- dabei benötigt dieser Algo dann auch gefühlte 2-3 sec.- um die
Liste zu durchlaufen- Hab' ich natürlich auch probiert.Aber klar die Zeiten
addieren sich.
Boyer-Moore habe ich vorher erfolgreich im Einsatz gehabt- aber es ist bei
mir nicht so schnell wie "WuManber"- vielleicht hab' ich aber auch was falsch
gemacht ???

Mein Probeversuch sieht erstmal so aus :
(Änderung mit StringList)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

P:=TStringList.Create;
P.Add('Gre0064');
//P.Add('1365EGre0064');
//P.Add('she');
//P.Add('his');
//P.Add('hers');

Search_WuManber(Zaehler.Text,P,Trefferlist);
Label1.Caption:='Anzahl der Treffer = '+InttoStr(TrefferList.Count);

   for i:=0 to TrefferList.Count-1 do
     ListBox1.Items.Add(TrefferList.Strings[i]);

s:=Copy(TrefferList.Strings[0],3,Length(TrefferList.Strings[0]));
x:=StrtoInt(s);   //erster Treffer

s:=Zaehler.Text;  // also alles brutal in den String

for I:= x downto 0 do // Rückwärtssuche
   begin
     if s[i]=#10 then ln:=true;
     if s[i]=#13 then cr:=true;
    if ln and cr then
     begin
       z:=z+1;
       ln:=false;
       cr:=false;
     end;
   end;

die Änderung in "WuManber" so :

markieren

Delphi-Quelltext

1:
2:
3:

                     // Muster r tatsächlich gefunden
                      if assigned(Trefferlist) then
                         TrefferList.Add(IntToStr(i)+','+IntToStr(k - mi+1));

ich denke - das ist OK - oder ???
natürlich werde ich deinen Vorschlag gleich heute abend ausprobieren-danke dafür.

Meine Datenbank ist aus Access konvertiert und enthält nunmehr keinerlei Formatierungen,
sodass ich auf ca. 3mb bei 19668 Datensätze komme.

aufgebaut so : Feld0|Feld1|Feld2|...........Feldn

Vielleicht hast du ja einen Vorschlag - wie man sowas auf eine andere Art
schnellstmöglich durchsuchen kann ???

...die Auswertung mit dem Zeilenumbruch gefällt mir auch noch nicht- da in den
Feldern auch Bemerkungstext mit Umbruch stehen kann - hier werde ich wohl
auf den Umbruch von C ( '\n' ) ausweichen.

Naja - erstmal herzlichen Dank für alles.

puuhhh - war das lang... :-)

mfg
karlheinz

Gausi · Verfasst: Mi 18.06.08 17:18

Sag einfach nochmal, was du als Daten gegeben hast, und was du mit diesen Daten anstellen willst. :gruebel:

So wie ich dein Beispiel interpretiere, hast du eine Liste mit Strings, die aus einer Datenbank kommt. Ob das nun ein langer String mit Zeilenumbrüchen oder tausend kurze sind, ist erstmal egal. Und diese Liste/String willst du nach etwas durchsuchen. Und hier ist die Frage: nach was? Möchtest du a.) ab und zu mal einen String darin suchen (z.B. "Gre0064") oder b.) simultan ganz viel darin suchen (z.B. Gre0064, Ott0021, dan0027, duz0992, hju7272, hallo, welt, wort, 42, sinn, mathe, delphi, satanarchäolügenialkohöllischer wunschpunsch, hausnummer, computer, elefantenjagd, informatiker, neun, [...nochmehr, und alles auf einmal, in einem Durchlauf]).

Im Fall b.) ist Wu-Manber sinnvoll, dafür ist der ja gedacht. Im Fall a.) ist Wu-Manber ungefähr so sinnvoll, wie mit nem 120-Tonnen-Sattelschlepper in Urlaub fahren, weil man 2 Koffer Gepäck hat. ;-)

Für Fall a. sollte bei 20.000 Strings eigentlich so etwas wie

markieren

Delphi-Quelltext

1:
2:
3:

for i := 0 to myList.Count-1 do
  if pos(Suchstring, myList[i]) > 0 then
    Memo1.lines.add(myList[i] + ' enthält ' + suchstring );

reichen. Man kann das mit Boyer-Moore schneller machen, wenn (Achtung, sehr wichtig!) man die Vorbereitungsphase, also die Berechnung von Good-Suffix und Bad-Character-Array nur einmal durchführt und diese Arrays als Parameter der eigentlichen Suche mit übergibt. Ich habe (bald) ein ganz ähnliches Problem, und erste Tests haben ergeben, dass bei so einer Suche das Nadelöhr der Zugriff auf die einzelnen Objekte/Stings in der Liste ist. Ob man da Pos oder Boyer-Moore anwendet, ist eher weniger ausschlaggebend - da bin ich aber noch was am austüfteln. ;-)

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

ich denke - dass ich eher im Fall A - liege.
meine Felder sind wie oben beschrieben aufgebaut und enthalten
Gerätedaten(Nummern),Kd-Nummern,Adressen etc.
allerdings variiert die Anzahl der Felder zwischen 20 und 30.
d.h. die eine Datenbank hat 20 Felder - die Andere 30.
Durchsuchen muss ich aber nur die ersten 5-7 Felder.
also auch Einlesen,Verändern,neue Datensätze hinzufügen etc.
Das ganze läuft z.z. mit Access und ist "schweinelangsam".

Wenn ich dich richtig verstehe - schiesse ich also mit dem
"WuManber-Algo" - hier mit Kanonen auf Spatzen.

Leider hab' ich aber keine Ahnung wie man das mit dem Boyer-Moore-Algo
also die Vorbereitungsphase " die Berechnung von Good-Suffix ,Bad-Character-Array"
macht.Bin halt eben Anfänger.Was ich in Betrieb hatte - war wohl eine
abgespeckte Variante vom BM.

Ja das Nadelöhr ist wirklich der Zugriff bzw. die Übergabe von Einzelstrings
an die Suchroutine.

Wenn du was tolles herauskriegst - wäre es schön- wenn du es mich wissen lässt.
Ansonsten probier' und lern ich mal noch ein bischen :-)

THX - für alles...

mfg
karlheinz

Gausi · Verfasst: Mi 18.06.08 19:22

Dann nimm einfach die Variante mit Pos - und versuche, den Zugriff auf die Daten effizienter zu gestalten - das wäre dann aber langsam was für ein neues Topic. ;-)

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

das mit der Objectliste klappt nun auch - thx

noch eine Frage :

gibt es einen besonderen Grund warum du eine TObjectList
anstatt einer TStringList benutzt ???

mfg
karlheinz

Gausi · Verfasst: Do 19.06.08 08:44

Du meinst für die Rückgabe der Ergebnisse? Klar gibts den.

Da ich mehrere Strings simultan suche, möchte ich wissen, an welcher Stelle welcher String gefunden wurde, und nicht nur, welche Strings irgendwo gefunden werden. Für die Info (String-Nr, Position) habe ich mir halt die Klasse TTreffer definiert, und mehrere Treffer kommen in eine Objectlist.

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

Ja - das mit der Klasse TTreffer ist mir schon klar.

Nur da ich es vorher ja nicht verstanden hatte - habe ich das
Gleiche mit einer StringList gemacht.

so :

markieren

Delphi-Quelltext

1:	TrefferList.Add(IntToStr(i)+','+IntToStr(k - mi+1));

wobei "i" ja der Index - und "k - mi+1" - die Position ist.

ich erhalte so die gleiche TrefferList wie du - nur komme ich so ohne die
Klasse TTreffer aus.

Hier hätte ich gerne gewusst ob es besondere Gründe gibt - warum du es anders gemacht
hast.Es geht mir hier nur um Lernzwecke und Verständnis.
( ...will dich nicht nerven )

mfg
karlheinz

Gausi · Verfasst: Do 19.06.08 20:46

Naja, wenn ich TTreffer nehme, kann ich hinterher die Treffer leichter checken, nach gefundenem String oder Position im durchsuchten String sortieren oder sonstwie aufarbeiten.

_________________
We are, we were and will not be.

jaenicke · Verfasst: Do 19.06.08 21:47

Der Vorteil ist vor allem, dass du dann die Daten direkt hast. Wenn du eine StringList stattdessen benutzt, dann musst du, um die Treffer im Programm auswerten zu können, die Daten aus den Zeilen der StringList auslesen. Dazu musst du dann die Zeile auseinandernehmen, die Teile in Zahlenwerte zurück umwandeln, und so weiter. Das kostet bei vielen Treffern dann enorm viel Zeit.

karlheinz · Hält's aus hier Beiträge: 9

Hallo ihr Beiden

ich danke Euch ganz herzlich für die Erklärungen.
So ganz überzeugt bin ich allerdings noch nicht.
Weil ich so oder so eine Typ-Umwandlung vornehmen
muss.Hab't aber bitte ein wenig Geduld mit mir.

THX - für alles...

mfg
karlheinz

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

Ich habe deinen Rat beherzigt und versuche mich z.z. an dem
Boyer-Moore-Algo.

Aber ich habe mal wieder Probs mit dem Auslesen des Wertes.

markieren

Delphi-Quelltext

1:	Trefferlist.Add(Pointer(k-j+1));

Hier benutzt du einen Zeiger. Das "k-j+1" meine Position ist - ist mir schon
klar.Ich habe es vorerst auch wieder mit einer StringList gemacht - würde es
aber gerne - wie oben benutzen.

Kannst du mir nochmal helfen ???

mfg
karlheinz

Gausi · Verfasst: So 22.06.08 19:26

Bei Boyer-Moore benutze ich eine einfache TList zum Speichern der Treffer. Dafür caste ich den Integer (= Position des Suchmusters im Text) nach Pointer, denn das will die TList haben. Eine Stringlist bringt hier gar nichts, was soll denn da rein? Der gefundene String? Davon gibts nur einen. Die Position? Das ist ein Integer, kein String.

Aber nochmal, oder etwas genauer: Der Unterschied zwischen Boyer-Moore und dem Pos ist bei 10MB Gesamtdaten ca. 50ms (zumindest bei mir). Wenn deine Suche zu lange dauert, dann liegt das nicht an der Suche selbst, sondern an dem drumherum. Daher: Nimm lieber die Variante mit Pos, das ist für den Anfang auch weniger fehleranfällig und leichter zu verstehen. Und optimiere den Zugriff auf die Daten. ;-)

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

versteh' mich bitte nicht falsch - denn es klappt ja alles-

ich bin nur mal wieder zu blöd' - den Pointer auszulesen.

Ich durchsuche nun String für String und es ist sehr schnell.

z.z. lese ich die Position so :

markieren

Delphi-Quelltext

1:	MyList.Add(IntToStr(k-j+1));

und bekomme auch die richtigen Werte.

mfg
karlheinz

Gausi · Verfasst: So 22.06.08 19:47

Aus der TList auslesen geht dann genau andersrum - da muss man den in der Liste enthaltenen Pointer nach Integer casten. Also Integer(myList[i]). Das kann man dann wieder in ein IntToStr einpacken, wenn man das irgendwo anzeigen will.

_________________
We are, we were and will not be.

karlheinz · Hält's aus hier Beiträge: 9

@Gausi

manchmal sieht man vor lauter Wald - die Bäume nicht.
Ja - TList war das Stichwort. TSimpleTrefferList ist vom Typ TList.
Ich habe da eine ObjectList raus gemacht :oops:

THX - läuft...

mfg
karlheinz

MicAlter · Hält's aus hier Beiträge: 1

Hallo gausi,
hallo zusammen,

ich habe den Wu-Manber-Algorithmus mal getestet - ist richtig super und genau das, was ich brauche (viele Filter auf einen Text). :zustimm:

Nun habe ich festgestellt, dass dieser Algorithmus "case-sensitiv" arbeitet. An welcher Schraube kann man drehen, um dieses abzustellen bzw. ist das überhaupt möglich?

lg,
Michael

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme