100MB Datei nach Strings durchsuchen

Tristan · Beiträge: 106

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 · Verfasst: 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!

_________________
Na denn, dann. Bis dann, denn.

Gausi · Verfasst: 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):

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:
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; 

// Suche mit Horspool, direkt die unrolled-Variante. Sehr ähnlich zu BM_Unrolled 
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); 

  // "echten" BC-Shift merken 
  BC_last := BC[p[m]]; 
  // BC(lastCh) mit "Large" überschreiben 
  BC[p[m]] := Large; 

  k := m; 
  result := 0; 

  while k <= n do 
  begin 
      //fast loop 
      repeat 
        k := k + BC[t[k]]; 
      until k > n; 

      //undo 
      if k <= Large then 
        //Muster nicht gefunden 
        break 
      else 
        k := k - Large; 

      j := 1; 
      // slow loop 
      while (j < m) and (p[m-j] = t[k-j]) do 
        inc(j); 

      if j=m then 
      begin 
        // Muster gefunden 
        result := k - j + 1; 
        k := k + m; //oder: k+1, oder: break; je nachdem, wie man den Text komplett durchsucht haben will 
      end else 
      begin 
          // Muster verschieben 
          if t[k] = p[m] then 
            k := k + BC_last    // Hier dann den original-Wert nehmen 
          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. ;-)

_________________
We are, we were and will not be.

alzaimar · Verfasst: Do 15.05.08 15:26

Stimmt, 100MB sind ja heutzutage nicht mehr viel.

_________________
Na denn, dann. Bis dann, denn.

Tristan · Beiträge: 106

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 · Verfasst: 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.

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.

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:
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;    // Index des gefunden Musters in der Musterliste
      Position: Integer; // Position des Musters im Text
      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;  // Array-Größe: 2^15, 0 - 2^15-1
      MASK = $1F; // = binär 11111
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;
  // Preprocessing
  // Länge des kürzesten Musters und Gesamtlänge bestimmen
  lmin := High(Integer);
  for r := 0 to P.Count - 1 do
    if lmin > length(p[r]) then lmin := length(p[r]);

  // Größe der Blöcke B bestimmen
  if lmin = 1 then
    B := 1
  else
    if (lmin > 2) and (lmin*P.Count > 400) then
      B := 3
    else
      B := 2;

  // Shift-Tabelle initialisieren
  def := lmin - B + 1;
  for i := 0 to MAXHASH do
    Shift[i] := def;

  // "Präfix-Hash" der Muster bestimmen
  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;

  // Shift- und Hash-Array ermitteln
  for r := 0 to P.Count - 1 do
  begin
    mi := length(p[r]);
    //for i := B to mi - 1 do
    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] > lmin-i then Shift[h] := lmin-i;
      if Shift[h] > mi-i then Shift[h] := mi-i;

    end;

    // Shift + Hash für Suffix des Musters der Länge B
    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;

    // Aktuelles Muster in die Liste an Hash[h] eintragen
    if not assigned(Hash[h]) then Hash[h] := TList.Create;
    Hash[h].Add(Pointer(r));
  end;

  // Suchphase
  k := lmin;
  n := length(t);
  while k <= n do
  begin
    // h für aktuelles Suffix bestimmen
    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
      // möglicherweise ein Muster gefunden
      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
        // (Das sollte aber immer so sein)
        // Muster in dieser Liste überprüfen
        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]);
              // "Präfix"-Hash stimmt auch überein
              if k >= mi then
              begin
                  // Muster ist auch lang genug - Überprüfen
                  j := 0;
                  while (j < mi) and (t[k-j] = p[i][mi-j]) do inc(j);

                  if j = mi then
                  begin
                      // Muster r tatsächlich gefunden
                      if assigned(Trefferlist) then
                        Trefferlist.Add(TTreffer.Create(i, k - mi+1));
                  end;
              end;

          end;
        end;
      end;

      // Überprüfung auf Mustervorkommen komplett,
      // Verschiebung um 1
      k := k + 1;
    end else
      // shift[h]>0, verschieben
      k := k + shift[h];
  end;

  for i := 0 to MAXHASH do
    if assigned(Hash[i]) then hash[i].Free;
end;

_________________
We are, we were and will not be.

Heiko · Beiträge: 3169 Erhaltene Danke: 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 · Beiträge: 106

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 · Verfasst: 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.

_________________
We are, we were and will not be.

BenBE · Verfasst: 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.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Heiko · Beiträge: 3169 Erhaltene Danke: 11

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 · Beiträge: 106

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 · Beiträge: 3169 Erhaltene Danke: 11

Tristan hat folgendes geschrieben:

Was ist da jetzt genau der Unterschied zwischen Index und Position im Text?

Beispiel:

Suchstring

markieren

Quelltext

1:

ich

zu durchsuchender String

markieren

Quelltext

1:	Mich findest du eh nicht.

Die Suche würde ergeben:

markieren

Quelltext

1:	array[0..1] = (2, 20)

(sieht zwar so doof aus, aber ist dir wahrscheinlich so lieber als die PHP-Notation

).

Der Index ist hier die 0 und 1.

markieren

Quelltext

1:	array[0..1] = (2, 20)

Sprich: über welchen Index du die Position ausliest. Also wie ein normales Array (0 bis x).

Die Position ist dann der Wert des Arrays

markieren

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 · Verfasst: 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

markieren

Quelltext

1:
2:
3:
4:
5:

 
0 he
1 she
2 his
3 hers

im Text

markieren

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)

_________________
We are, we were and will not be.

uko · Verfasst: Do 15.05.08 22:14

Vieleicht auch eine Alternative: reguläre Ausdrücke. DiRegEx (www.yunqa.de/delphi/...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 · Beiträge: 3169 Erhaltene Danke: 11

@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 · Verfasst: 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:

_________________
We are, we were and will not be.

arj · Verfasst: 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 Suche bei Google

FGREP versucht?

Tristan · Beiträge: 106

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

markieren

Delphi-Quelltext

1:
2:
3:

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

durch folgenden Code ersetzt:

markieren

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 · Beiträge: 106

Das erste Problem vom letzen Beitrag hat sich erledigt, hier die Lösung:

markieren

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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme