Tmemorystream durchsuchen

[malabarista]

Hallo zusammen,
ich habe eine grosse Datei (ca. 20MB) und will sie nach einem bestimmten Muster durchsuchen, das Muster ändern und dann die Datei zurückschreiben.
Ich habe mich für Tmemorystream entschieden, weil dies "eigentlich" relativ gut mit grossen Dateien umgehen kann.
Allerdings fehlt jetzt die Information, wie ich diesen Stream durchsuchen kann, und das möglichst effektiv. Die Dokumentation ist da leider etwas dünn, deshalb frage ich jetzt hier.

Code: Alles auswählen

 
      msApp := TMemoryStream.Create;
      try
        msApp.LoadFromFile('m2.dat');
        msApp.Seek(0,soFromBeginning);
 // und nun durchsuchen ??
 

Gibt es etwas Vergleichbares wie
ip:=pos('***MUSTER***', msApp);
??

[af0815]

Du kannst dir Teile in einen Buffer laden und den durchsuchen. Der Buffer kann ja grösser sein, das es effizient wird. 20 MB sind ja nicht so große Mengen.

[wp_xyz]

Und der Puffer, in dem der Memory-Stream seine Daten hält, heißt sinnigerweise MemoryStream.Memory und hat die Größe MemoryStream.Size.

[malabarista]

Stehen dann die 20MB in dem Buffer ?
Oder muss ich den (mit welchem Befehl) nachladen ?

[wp_xyz]

Den Puffer hast du mit LoadFromFile gefüllt. Durch einen Cast zu PChar kannst du den Pointer in einen PChar-String verwandeln und sogar per pos darin suchen:

Code: Alles auswählen

procedure TForm1.Button1Click(Sender: TObject);
var
  m: TMemoryStream;
  p: Integer;
begin
  m := TMemorystream.Create;
  m.LoadfromFile('project1.lpr');
  Showmessage(PChar(m.Memory));
  p := pos('Project1', PChar(m.Memory));
  ShowMessage(IntToStr(p));
  m.Free;
end; 

[malabarista]

Sehr schöne Idee. Danke!

[wp_xyz]

Vorsicht allerdings: Ich könnte mir vorstellen, dass die Suche vorzeitig beendet wird, falls der Buffer Null-Bytes enthält. Und prüfe auch, ob der von pos() zurückgelieferte Index wie bei Strings mit 1 oder wie bei PChar mit 0 beginnt.

[BeniBela]

Für pchar sollte man strpos verwenden, sonst macht das gleich nochmal eine zusätzliche Kopie von den ganzen Daten. Wenn man große Daten hätte, ist das ein no-go,



Wie würde man eigentlich bei großen Daten vorgehen? Im allgemeinen Fall, wenn man eine Funktion schreibt, die mit einem Stream aufgerufen hat, aber man weiß vorher nicht was für ein Stream. Wenn man die Daten nicht vollständig in den Speicher laden kann, geht das mit MemoryStream schlecht. Da würde man dann read von FileStream verwenden, und blockweise vorgehen. Aber wenn die Funktion mit blockweise Vorgehen implementiert wurde und man dann doch einen MemoryStream bekommt, ist das auch wieder schlecht, weil man dann die ganzen Daten sinnlos kopiert.

Apache hat da ein System mit Bucket Brigades.Der Bucket ist der Block und die Brigade der Stream, Von der Brigade kann man dann den nächsten Bucket anfordern, und wenn man alle Buckets durchlaufen hat, hat man alle Daten durchsucht. Und die Brigade wählt die Bucketgröße so, dass möglichst wenig Daten kopiert werden.

[Warf]

Wie würde man eigentlich bei großen Daten vorgehen? Im allgemeinen Fall, wenn man eine Funktion schreibt, die mit einem Stream aufgerufen hat, aber man weiß vorher nicht was für ein Stream. Wenn man die Daten nicht vollständig in den Speicher laden kann, geht das mit MemoryStream schlecht. Da würde man dann read von FileStream verwenden, und blockweise vorgehen. Aber wenn die Funktion mit blockweise Vorgehen implementiert wurde und man dann doch einen MemoryStream bekommt, ist das auch wieder schlecht, weil man dann die ganzen Daten sinnlos kopiert.

Offensichtliche Optimierung:

Code: Alles auswählen

function findInStream(Str: TSTream; pattern: String): Integer;
var State: Integer;
 
function searchMem(buff: PChar; buffSize: Integer): Integer;
begin
  For Result:=0 to buffSize - 1 do
  begin
    if pattern.chars = buff[state] then
      Inc(state)
    else
      state := 0;
    if State = pattern.length then break;
  end;
end;
 
var buff: array[0..1023] of char;
  len: Integer;
begin
  Str.Position := 0;
  State := 0;
  Result := 0;
  if (Str is TMemoryStream) then
  begin
    with TMemoryStream(Str) do
      Result := searchMem(Memory, Size);
    if State < pattern.length then Result := -1;
    exit;
  end;
  repeat
    len := Str.Read(buff[0], 1024);
    Inc(Result, searchMem(@buff[0], len));
    if State = pattern.length then
    begin
      Dec(Result, pattern.length);
      exit;
    end;
  until len < 1024;
  Result := -1;
end;

[af0815]

Meiner Meinung nach, darfst dudie Blõcke nicht um einfach 1024 verschieben. Wenn das Pattern über die Buffergrenze geht. Ich würde 1024 um die Länge des Pattern mvermindern Poitioniert nachladen, die Lä nge kann ja mit 1024 gleich bleiben.

[Warf]

Meiner Meinung nach, darfst dudie Blõcke nicht um einfach 1024 verschieben. Wenn das Pattern über die Buffergrenze geht. Ich würde 1024 um die Länge des Pattern mvermindern Poitioniert nachladen, die Lä nge kann ja mit 1024 gleich bleiben.

Bei meinem ansatz ist die Patterngrenze egal, da der State zwischen zwei memory scans sich nicht verändert. Wenn der z.B. nach Welt! sucht bei 4 bytes block größe in "Hallo Welt!!" sucht würde das so ablaufen:
1. Buffer "Hall" -> Result(checkmem) = 4 State = 0 (es ist am ende kein teil von Welt drin)
2. Buffer "o We" -> Result = 4, State = 2 (zwei 2 des patterns gefunden bevor ende)
3. Buffer "lt!!" -> Result = 3 (nach nur 3 zeichen frühzeitig terminiert weil gefunden) State = 5 (alle 5 teile des patterns gelesen)
das ergebnis wäre also Result1 + Result2 + Result3 - "Welt!".length = 4+4+3-5 = 6. Das Pattern steht also an Position 6 des streams.

Übrigens, man kann das ganze auch als generische Klasse für beliebige Typen bei denen der Gleichheitsoperator überladen ist bauen, man kann also nicht nur nach texten suchen, man kann auch in einem Array von Objekten oder Klassen suchen. Wenn man komplexer suchen will kann man diesen Automaten (letzendlich ists nichts anderes als ein Deterministischer Endlicher Automat) auch auf Regex erweitern.

[braunbär]

Wenn nicht ganz simpel ein einziger Teilstring gesucht wird, sondern die Suche nur geringfügig komplizierter ist, dann ist regex das Mittel der Wahl, um Muster in einem String zu finden.
Das reduziert den Programmieraufwand wirklich auf einen Bruchteil gegenüber dem "manuellen" Duchsuchen des Strings.

[af0815]

Bei meinem ansatz ist die Patterngrenze egal, da der State zwischen zwei memory scans sich nicht verändert.

Danke für die Erklärung. Der Ansatz ist verdammt gut, ich glaube den Code werde ich mir (mit deiner Erlaubnis) klauen

[Warf]

Danke für die Erklärung. Der Ansatz ist verdammt gut, ich glaube den Code werde ich mir (mit deiner Erlaubnis) klauen

Gerne, das ist im grunde nur Automaten Theroie. Das ist die selbe technik wie auch Regex verwendet oder auch Compiler, da es extrem effizient ist, da du dir nur einen Charakter auf einmal anschauen musst (ich fass es nur zu blöcken zusammen wegen der Zugriffszeit) und im einfachen Fall (also text suche) man nur einmal drüber laufen muss. Schau dir einfach mal Deterministische Endliche Automaten an, das was ich gebaut hab ist einfach nur ein DFA mit den States 0, ..., n mit n = pattern.length wobei man vom State i nach i+1 kommt wenn man den richtigen buchstaben hat und bei einem falschen fällt man in state 0 zurück (state n ist Endzustand).

Sehr mächtiges Konzept, und sehr gut zum effizienten parsen von großen streams

[malabarista]

@warf:
Wow, klasse!