Tmemorystream durchsuchen

Für Fragen von Einsteigern und Programmieranfängern...

Tmemorystream durchsuchen

Beitragvon malabarista » 19. Jan 2019, 12:23 Tmemorystream durchsuchen

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);
??
malabarista
 
Beiträge: 305
Registriert: 11. Jun 2016, 11:16
Wohnort: Konstanz
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0 | 
CPU-Target: 64Bit
Nach oben

Beitragvon af0815 » 19. Jan 2019, 12:55 Re: Tmemorystream durchsuchen

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).
af0815
 
Beiträge: 3582
Registriert: 7. Jan 2007, 10:20
Wohnort: Niederösterreich
OS, Lazarus, FPC: FPC 3.2 Lazarus 2.0 per fpcupdeluxe | 
CPU-Target: 32Bit (64Bit)
Nach oben

Beitragvon wp_xyz » 19. Jan 2019, 13:38 Re: Tmemorystream durchsuchen

Und der Puffer, in dem der Memory-Stream seine Daten hält, heißt sinnigerweise MemoryStream.Memory und hat die Größe MemoryStream.Size.
wp_xyz
 
Beiträge: 2800
Registriert: 8. Apr 2011, 08:01

Beitragvon malabarista » 19. Jan 2019, 14:36 Re: Tmemorystream durchsuchen

Stehen dann die 20MB in dem Buffer ?
Oder muss ich den (mit welchem Befehl) nachladen ?
malabarista
 
Beiträge: 305
Registriert: 11. Jun 2016, 11:16
Wohnort: Konstanz
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0 | 
CPU-Target: 64Bit
Nach oben

Beitragvon wp_xyz » 19. Jan 2019, 15:05 Re: Tmemorystream durchsuchen

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;
wp_xyz
 
Beiträge: 2800
Registriert: 8. Apr 2011, 08:01

Beitragvon malabarista » 19. Jan 2019, 15:18 Re: Tmemorystream durchsuchen

Sehr schöne Idee. Danke!
malabarista
 
Beiträge: 305
Registriert: 11. Jun 2016, 11:16
Wohnort: Konstanz
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0 | 
CPU-Target: 64Bit
Nach oben

Beitragvon wp_xyz » 19. Jan 2019, 16:50 Re: Tmemorystream durchsuchen

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.
wp_xyz
 
Beiträge: 2800
Registriert: 8. Apr 2011, 08:01

Beitragvon BeniBela » 19. Jan 2019, 17:27 Re: Tmemorystream durchsuchen

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

Beitragvon Warf » 19. Jan 2019, 21:33 Re: Tmemorystream durchsuchen

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;
Warf
 
Beiträge: 1067
Registriert: 23. Sep 2014, 16:46
Wohnort: Aachen
OS, Lazarus, FPC: Mac OSX 10.11 | Win 10 | FPC 3.0.0 | L trunk | 
CPU-Target: x86_64, i368, ARM
Nach oben

Beitragvon af0815 » 20. Jan 2019, 13:07 Re: Tmemorystream durchsuchen

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).
af0815
 
Beiträge: 3582
Registriert: 7. Jan 2007, 10:20
Wohnort: Niederösterreich
OS, Lazarus, FPC: FPC 3.2 Lazarus 2.0 per fpcupdeluxe | 
CPU-Target: 32Bit (64Bit)
Nach oben

Beitragvon Warf » 20. Jan 2019, 16:44 Re: Tmemorystream durchsuchen

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.
Warf
 
Beiträge: 1067
Registriert: 23. Sep 2014, 16:46
Wohnort: Aachen
OS, Lazarus, FPC: Mac OSX 10.11 | Win 10 | FPC 3.0.0 | L trunk | 
CPU-Target: x86_64, i368, ARM
Nach oben

Beitragvon braunbär » 20. Jan 2019, 18:20 Re: Tmemorystream durchsuchen

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.
braunbär
 
Beiträge: 285
Registriert: 8. Jun 2017, 17:21

Beitragvon af0815 » 20. Jan 2019, 19:02 Re: Tmemorystream durchsuchen

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).
af0815
 
Beiträge: 3582
Registriert: 7. Jan 2007, 10:20
Wohnort: Niederösterreich
OS, Lazarus, FPC: FPC 3.2 Lazarus 2.0 per fpcupdeluxe | 
CPU-Target: 32Bit (64Bit)
Nach oben

Beitragvon Warf » 20. Jan 2019, 20:09 Re: Tmemorystream durchsuchen

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
Warf
 
Beiträge: 1067
Registriert: 23. Sep 2014, 16:46
Wohnort: Aachen
OS, Lazarus, FPC: Mac OSX 10.11 | Win 10 | FPC 3.0.0 | L trunk | 
CPU-Target: x86_64, i368, ARM
Nach oben

Beitragvon malabarista » 20. Jan 2019, 20:21 Re: Tmemorystream durchsuchen

@warf:
Wow, klasse!
malabarista
 
Beiträge: 305
Registriert: 11. Jun 2016, 11:16
Wohnort: Konstanz
OS, Lazarus, FPC: Linux Mint 18.1 L1.6.2-1 FPC 3.0.0 | 
CPU-Target: 64Bit
Nach oben

» Weitere Beiträge siehe nächste Seite »
Nächste

Zurück zu Einsteigerfragen



Wer ist online?

Mitglieder in diesem Forum: braunbär und 6 Gäste

porpoises-institution
accuracy-worried