Entwickler-Ecke
Dateizugriff - 100MB Datei nach Strings durchsuchen
Tristan - Do 15.05.08 13:58
Titel: 100MB Datei nach Strings durchsuchen
Ich wollte euch einmal um Rat fragen, nachdem ich mit den Boardmitteln nicht mehr weiter komme.
Ich habe ein Logfile, dass in der Textform rund 100MB groß ist. Diese Datei möchte ich nach mehreren Strings durchsuchen. Wird ein String gefunden so soll die gesamte Zeile in ein Memofeld eingetragen werden.
Bis jetzt habe ich die Datei mit Strings.Loadfromfile geladen und anschließend Zeile für Zeile mit Pos durchsucht.
Leider dauert dieser Vorgang sehr lange. Nun habe ich von einem Algorithmus gehört (Moore Boyer) der ein schnelleres Suchen ermöglichen soll - sowie vom Laden in eine Hashliste die wesentlichs schneller sein soll als die Stringlist.
Könnt ihr mir einen Tipp geben wie ich die ganze Sache am Besten angehen könnte?
Gruß Tristan
alzaimar - Do 15.05.08 14:41
Also, Boyer-Moore ist schon sehr schnell. Such mal nach der "FastStrings"-Unit bei Google.
Sooo, ne Hashlist bringt nix, weil Du die ja erst füllen musst.
So richtig schnell geht es aber erst, wenn Du die Datei Blockweise in einen Stream liest (z.B. 64kb weise). Nun hast Du z.B. 1500 Zeilen im Speicher. Nun suchst Du mit BM nach deinen Strings. Von der gefundenen Position rückwärts bis zum #13 (CR) und vorwärts bis zum LF(#10) ist deine Zeile.
Achtung! Durch das blockweise Einlesen kann es passieren, das Du den zu suchenen Text zerteilst, also am Ende des 1.Blockes ist der linke Teil des Suchtextes und am Anfang des nächsten Blockes ist der restliche Teil. Das musst Du beim Einlesen des nächsten Blockes beachten (Du kannst dir z.B. immer den hintersten Teil (N-1 Zeichen, N=Länge des Suchstrings) merken und den nächsten Block im Speicher DAHINTER platzieren. Dann hast Du nicht 64k Zeichen, sondern 64k+N-1!
Gausi - Do 15.05.08 15:21
Bei "mehreren" Strings klingelt bei mir was :idea:
Was sind denn mehrere? Ein paar, ein paar Dutzend oder noch mehr? Und sollen die alle gleichzeitig gesucht werden, oder einer nach dem anderen?
Für einzelne Suche kann man Boyer-Moore verwenden, bzw. eine vereinfachte Variante (die aber meistens schneller ist):
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:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
| type
TBC_IntArray = Array[Char] of Integer;
function PreProcess_BMH_BC(p: String): TBC_IntArray;
var i, m: Integer;
c: Char;
begin
m := Length(p);
for c := low(Char) to High(Char) do
result[c] := m;
for i := 1 to m-1 do
result[p[i]] := m-i;
end;
function Search_BMH_Unrolled(t,p: String): Integer;
var m, n, k, j: Integer;
BC: TBC_IntArray;
BC_last: Integer;
Large: Integer;
begin
m := Length(p);
n := Length(t);
Large := m + n + 1;
BC := PreProcess_BMH_BC(p);
BC_last := BC[p[m]];
BC[p[m]] := Large;
k := m;
result := 0;
while k <= n do
begin
repeat
k := k + BC[t[k]];
until k > n;
if k <= Large then
break
else
k := k - Large;
j := 1;
while (j < m) and (p[m-j] = t[k-j]) do
inc(j);
if j=m then
begin
result := k - j + 1;
k := k + m; end else
begin
if t[k] = p[m] then
k := k + BC_last else
k := k + BC[t[k]];
end;
end;
end; |
Ich würde einfach brutal die 100MB in einen String laden. Filestream erstellen, Länge des Strings auf dessen Größe setzen und einmal Read - das sollte noch gehen. Ist zwar nicht optimal, aber dafür ist dann der Programmieraufwand schön klein ;-).
Wenn du viele Strings gleichzeitig suchen willst, kann ich noch was anderes posten, was nochmal schneller geht. ;-)
alzaimar - Do 15.05.08 15:26
Stimmt, 100MB sind ja heutzutage nicht mehr viel.
Tristan - Do 15.05.08 15:43
Ich habe gerade mal nachgezählt, ich muss mit 20.000 Strings rechnen die als Suchbegriffe dienen.
Nochmal kurz zur Ausgangslage:
- ich habe ein bzw. mehrere Logfiles diese sind zum Teil 100MB groß
- ich habe eine Liste mit 20.000 Pfadangaben (Strings)
- nun soll jedes Logfile nach jedem einzelnen Eintrag der Suchliste durchgegangen werden.
- gibt es eine Übereinstimmung, dann verschiebe den Suchbegriff aus der Suchliste in eine Gefunden-Liste
-->beim nächsten Logfile verringert sich somit die Suchliste.
@Gausi: Ist deine gepostete Funktion auch bei dieser Variante anwendbar? Und was meinst du mit der Länge des Strings bzw. Read? Kann man direkt im Stream suchen oder muss man diesen wieder in einzelne Teile zerhacken?
Gruß Tristan
Gausi - Do 15.05.08 15:56
Autsch...20.000 Strings? Dann solltest du
wirklich was anderes nehmen. Hab ja grade ne Diplomarbeit zu dem Thema fertig - daher kann ich auch da was zu posten. :D
Der Algorithmus von Wu-Manber sollte es da tun. Selbst getestet hab ich den nur mit bis zu 500 Strings, wie sich der bei 20.000 verhält, weiß ich nicht. Das kommt auch sehr darauf an, wie lang die einzelnen gesuchten Strings sind (je länger, desto besser). Die Variante hier listet alle Fundstellen auf, und packt sie in eine Liste.
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:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
| type TMultiTrefferList = TObjectlist;
TTreffer = class
Index: Integer; Position: Integer; constructor Create(idx,p: Integer);
end;
constructor TTreffer.Create(idx,p: Integer);
begin
inherited create;
Index := Idx;
Position := p;
end;
function Search_WuManber(t: String; P: TStrings; Trefferlist: TMultiTrefferList): Boolean;
const MAXHASH = $7FFF; MASK = $1F; var i, r, lmin, mi, B, def, k, n, j, h: Integer;
Shift: Array[0..MAXHASH] of Integer;
Hash: Array[0..MAXHASH] of TList;
Prefix: Array of Integer;
TextPref: Integer;
begin
result := true;
lmin := High(Integer);
for r := 0 to P.Count - 1 do
if lmin > length(p[r]) then lmin := length(p[r]);
if lmin = 1 then
B := 1
else
if (lmin > 2) and (lmin*P.Count > 400) then
B := 3
else
B := 2;
def := lmin - B + 1;
for i := 0 to MAXHASH do
Shift[i] := def;
Setlength(Prefix,P.Count);
for r := 0 to P.Count - 1 do
begin
mi := length(p[r]);
if B=1 then
Prefix[r] := Integer(p[r][mi-lmin+1])
else
Prefix[r] := (Integer(p[r][mi-lmin+1]) shl 8) + Integer(p[r][mi-lmin+2]);
end;
for r := 0 to P.Count - 1 do
begin
mi := length(p[r]);
for i := mi - lmin + B to mi - 1 do
begin
h := Integer(p[r][i]) AND MASK;
if B >= 2 then h := (h shl 5) + (Integer(p[r][i-1]) and MASK);
if B >= 3 then h := (h shl 5) + (Integer(p[r][i-2]) and MASK);
if Shift[h] > mi-i then Shift[h] := mi-i;
end;
h := Integer(p[r][mi]) AND MASK;
if B >= 2 then h := (h shl 5) + (Integer(p[r][mi-1]) and MASK);
if B >= 3 then h := (h shl 5) + (Integer(p[r][mi-2]) and MASK);
Shift[h] := 0;
if not assigned(Hash[h]) then Hash[h] := TList.Create;
Hash[h].Add(Pointer(r));
end;
k := lmin;
n := length(t);
while k <= n do
begin
h := Integer(t[k]) AND MASK;
if B >= 2 then h := (h shl 5) + (Integer(t[k-1]) and MASK);
if B >= 3 then h := (h shl 5) + (Integer(t[k-2]) and MASK);
if shift[h]=0 then
begin
if B=1 then
TextPref := Integer(t[k - lmin + 1])
else
TextPref := (Integer(t[k - lmin + 1]) shl 8) + Integer(t[k - lmin + 2]);
if assigned(Hash[h]) then
begin
for r := 0 to Hash[h].Count - 1 do
begin
i := Integer(Hash[h].Items[r]);
if Prefix[i] = TextPref then
begin
mi := length(p[i]);
if k >= mi then
begin
j := 0;
while (j < mi) and (t[k-j] = p[i][mi-j]) do inc(j);
if j = mi then
begin
if assigned(Trefferlist) then
Trefferlist.Add(TTreffer.Create(i, k - mi+1));
end;
end;
end;
end;
end;
k := k + 1;
end else
k := k + shift[h];
end;
for i := 0 to MAXHASH do
if assigned(Hash[i]) then hash[i].Free;
end; |
Heiko - Do 15.05.08 16:11
Hallo Tristan,
erst einmal Glückwunsch zu deinem 100. Beitrag :beer: .
@Problem: Kannst du mal ein kleines Beispiel geben? Also wie die Logdatei genau aussieht, wie die Suchstrings und wie das Resultat aussehen soll?
Denn bei 20k-Suchstrings würde ich eher den Spieß umdrehen. Log-Datei aus einem MemStream/String Byteweise lesen und immer daran entscheiden, welche regel jetzt nur noch gelten können. Sprich sich durch einen Baum hangeln. Wenn du an ein Blatt kommst, akzeptierst du die zeile, ansonsten lehnst du sie ab. Das dürfte wesentlich schneller sein, als mehrfach mit pos durchzugehen, da du tote Zweige eher ausschließt. Allerdings kann es sein, dass Wu-Manber etc. doch schneller ist. Das hängt immer vom konkreten Fall ab.
Grüße
Heiko
Tristan - Do 15.05.08 16:31
ach Ihr seid Super, wenn ihr eine Frau wärt würde ich mich sofort :lol:
Also der Wu-Manber Algo ist richtig fix. Allerdings habe ich bis jetzt nur die Anzahl der Objects auslesen können (Liste.Count). Muss man die Objectliste durchlaufen um jedes Item als String wieder auszugeben oder wie macht man das am cleversten?
Gruß der Tristan
Gausi - Do 15.05.08 16:37
Ein Treffer ist ja ein Obekt, was nur aus zwei Integern besteht. Der eine gibt den Index des gefundenen Strings an, der andere die Position im Text. Wie man jetzt von der Fundstelle auf die Zeile im Logfile kommt, kann ich nicht genau sagen. Den Inhalt der Zeile sollte man herausbekommen, wenn man vorwärts und rückwärts nach einem Zeilenumburch (#13#10) sucht und dann mit Copy arbeitet.
BenBE - Do 15.05.08 18:59
Alternativ baut man sich aus den Funstellen aller #13#10 einfach einen Bum auf (Binary Search ;-) und nutzt diesen Baum um die nächst kleinere Zahl zu finden, die kleiner= der Fundstelle des Logfile-Strings ist.
Heiko - Do 15.05.08 19:28
Und als kleinen Hinweis: hier reden alle immer von #13#10. Bedenke bitte auch, dass das #13 bzw. das #10 auch alleine stehen kann (MacOSx-Zeilenumbruch respektiv der von Linux). Den von AIX brauchste IMHO nicht beachten (#21), da du höchstwahrscheinlich nicht in Kontakt damit kommst.
Tristan - Do 15.05.08 19:56
 Gausi hat folgendes geschrieben: |
| Ein Treffer ist ja ein Obekt, was nur aus zwei Integern besteht. Der eine gibt den Index des gefundenen Strings an, der andere die Position im Text... |
Was ist da jetzt genau der Unterschied zwischen Index und Position im Text? Wegen den Leerzeichen, ich muss mal schauen vielleicht kann ich einfach den Urlanfang suchen - z.B dem String "http://" Die Unit Faststrings hat doch auch eine optimierte Pos Funktion, allerdings müsste ich ja eigentlich Rückwärts suchen....
Heiko - Do 15.05.08 20:10
| Tristan hat folgendes geschrieben: |
| Was ist da jetzt genau der Unterschied zwischen Index und Position im Text? |
Beispiel:
Suchstring
zu durchsuchender String
Quelltext
1:
| Mich findest du eh nicht. |
Die Suche würde ergeben:
(sieht zwar so doof aus, aber ist dir wahrscheinlich so lieber als die PHP-Notation ;) ).
Der Index ist hier die 0 und 1.
Sprich: über welchen Index du die Position ausliest. Also wie ein normales Array (0 bis x).
Die Position ist dann der Wert des Arrays
Quelltext
1:
| var b = array[0..1] = (2, 20) |
z.B. ergibt
b[0] 2. Sprich das erste "ich" fängt an der Position 2 im String an. Der Index 1 würde dem entsprechend dir sagen, dass an Position 20 die 2. Fundstelle beginnt.
Gruß
Heiko
Gausi - Do 15.05.08 21:21
äh. nein. Das Objekt (2,20) gibt an, dass das 2. Muster in der Stinglist an Position 20 im Text beginnt. (5,100) gibt an, dass das 5. Muster an Position 100 beginnt.
Beispiel: Man sucht die Worte
Quelltext
1:
2:
3:
4:
5:
|
0 he
1 she
2 his
3 hers |
im Text
Quelltext
1:
2:
| 1 5 0 5 0
This is her brothers car. |
Die Ausgabe wäre dann
(2,2), (0,9), (0,17), (3,17)
uko - Do 15.05.08 22:14
Vieleicht auch eine Alternative: reguläre Ausdrücke. DiRegEx (
http://www.yunqa.de/delphi/doku.php/products/regex/index) hat eine demo dabei, die filestreams nach regulären Ausdrücken durchsucht.
Ob's schneller wird: keine Ahnung, hab's nicht getestet :-)
Grüße,
Uli
Heiko - Fr 16.05.08 09:22
@gausi: Ich hatte vergessen, dass mehrere Suchstringsvorkommen und nicht nur einer ;). Aber was macht dein Algo, wenn ein Suchstring mehrfach vorkommt? Oder ist das ein 2D-Array?
Gausi - Fr 16.05.08 09:46
@Heiko: Der Algo bekommt eine Liste mit Suchstrings übergeben, und liefert eine Liste mit Treffern zurück, die während des Durchlaufs erstellt werden. Für die Freigabe der Treffer-Objekte und -Liste ist die aufrufende Prozedur verantwortlich. Wenn da einige mehrfach vorkommen, ist das kein Problem.
@uko: Es kann gut sein, dass es für den speziellen Fall hier wirklich was schnelleres gibt. 100mb Log-Files scheint mir nicht gerade optimal zu sein, und 20.000 Suchstrings auch nicht - da ließe sich bestimmt was an der Wurzel verbessern. :nixweiss:
arj - Fr 16.05.08 10:41
Ich denke zwar nicht dass es schneller ist, aber ausprobieren würde ich es mal:
Hast du schon mal
FGREP versucht?
Tristan - Fr 16.05.08 13:29
also mit der Geschwindigkeit bin ich bis jetzt zufrieden, noch eine Frage an Gausi: ich habe die TMultiTrefferList durch eine Stringliste ersetzt, da ich diese besser auslesen kann - zudem habe ich
Delphi-Quelltext
1:
2:
3:
| if assigned(Trefferlist) then
Trefferlist.Add(TTreffer.Create(i, k - mi+1)); |
durch folgenden Code ersetzt:
Delphi-Quelltext
1:
2:
| If TrefferListe.IndexOf(p[r])=-1 then
TrefferListe.Add(p[r]); |
ich wenn der aktuelle Suchstring gefunden wurde diesen in die Trefferliste eintragen. Eigentlich wollte ich es so machen, dass beim Finden des Suchbegriffs dieser aus der Suchliste gelöscht wird aber daran scheitere ich noch. Auch mit
For r:=P.Count-1 downto 0 do... funktioniert das leider nicht: "Listenindex überschreitet das Maximum"
Tristan - Mo 19.05.08 15:39
Das erste Problem vom letzen Beitrag hat sich erledigt, hier die Lösung:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| var Liste:TMultiTrefferList;
Liste:=TMultiTrefferList.create;
Search_WuManber(HTMLFiles.Text,ReportFile,Liste);
For i:=Liste.Count-1 downto 0 do
Begin
UsedHTMLFiles_Listbox.Items.Add(HTMLFiles[TTreffer(Liste.Items[i]).Index]);
End; |
Aber es bleibt noch eine andere Frage:
kann man die WuManber Methode auch so umbauen, dass man die Suchbegriffe herausbekommt die nicht vorkommen?
Ich bin mir nicht sicher ob man da einfach nur
if j <> mi then... benutzen kann?
Gruß tristan
jaenicke - 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 - 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. ;-)
karlheinz - Mi 18.06.08 00:34
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 - 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:
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. :D
karlheinz - Mi 18.06.08 16:59
@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)
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');
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);
s:=Zaehler.Text;
for I:= x downto 0 do 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 :
Delphi-Quelltext
1:
2:
3:
| 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 - 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
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. ;-)
karlheinz - Mi 18.06.08 18:55
@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 - 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. ;-)
karlheinz - Mi 18.06.08 23:01
@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 - Do 19.06.08 08:44
Du meinst für die Rückgabe der Ergebnisse? Klar gibts den. :D
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.
karlheinz - Do 19.06.08 20:37
@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 :
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 - 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.
jaenicke - 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 - Fr 20.06.08 01:16
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 - So 22.06.08 19:14
@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.
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 - 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. ;-)
karlheinz - So 22.06.08 19:42
@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 :
Delphi-Quelltext
1:
| MyList.Add(IntToStr(k-j+1)); |
und bekomme auch die richtigen Werte.
mfg
karlheinz
Gausi - 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.
karlheinz - So 22.06.08 20:51
@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 - Mi 21.04.10 17:42
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
BenBE - Mi 21.04.10 19:45
Du kannst beim Zugreifen auf ein Zeichen dieses einfach in Groß- oder Kleinschreibung umwandeln. Ansonsten halt ganz normal den Algo verwenden ...
Wichtig ist dann nur, dass deine Suchworte auch alle in Groß- oder Kleinschreibung vorliegen, so wie du auch die Texte dann einliest.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!