Tmemorystream durchsuchen

Für Fragen von Einsteigern und Programmieranfängern...
malabarista
Beiträge: 321
Registriert: Sa 11. Jun 2016, 12:16
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0
CPU-Target: 64Bit
Wohnort: Konstanz

Tmemorystream durchsuchen

Beitrag von 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);
??

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6199
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Tmemorystream durchsuchen

Beitrag von 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.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Tmemorystream durchsuchen

Beitrag von 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
Beiträge: 321
Registriert: Sa 11. Jun 2016, 12:16
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0
CPU-Target: 64Bit
Wohnort: Konstanz

Re: Tmemorystream durchsuchen

Beitrag von malabarista »

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

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Tmemorystream durchsuchen

Beitrag von 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
Beiträge: 321
Registriert: Sa 11. Jun 2016, 12:16
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0
CPU-Target: 64Bit
Wohnort: Konstanz

Re: Tmemorystream durchsuchen

Beitrag von malabarista »

Sehr schöne Idee. Danke!

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Tmemorystream durchsuchen

Beitrag von 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
Beiträge: 308
Registriert: Sa 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4)
CPU-Target: 64 Bit

Re: Tmemorystream durchsuchen

Beitrag von 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
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Tmemorystream durchsuchen

Beitrag von 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;

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6199
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Tmemorystream durchsuchen

Beitrag von 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.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Tmemorystream durchsuchen

Beitrag von Warf »

af0815 hat geschrieben: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
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Tmemorystream durchsuchen

Beitrag von 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.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6199
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Tmemorystream durchsuchen

Beitrag von af0815 »

Warf hat geschrieben: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 :-)
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Warf
Beiträge: 1908
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Tmemorystream durchsuchen

Beitrag von Warf »

af0815 hat geschrieben: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
Beiträge: 321
Registriert: Sa 11. Jun 2016, 12:16
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0
CPU-Target: 64Bit
Wohnort: Konstanz

Re: Tmemorystream durchsuchen

Beitrag von malabarista »

@warf:
Wow, klasse!

Antworten