Datei durchsuchen

[Techcrawler]

Hallo erstmal,

ich habe nun schon dieses Forum durchsucht und auch in der Code-Library nachgesehen, doch das alles erfüllt nicht den gesuchten Zweck.

Die Frage: Ich möchte eine Datei nach einem String durchsuchen. Ich will ja an dieser Stelle gar keinen fertigen Code, sondern vielmehr eine Diskussion, welche Möglichkeiten es gibt und welche davon die wohl geeignetste ist.

Das Problem: Eine Datei beliebiger Größe (also von Byte bis Gigabyte) soll nach einem String durchsucht werden - geneauer gesagt, nach einem (oder mehreren) Hexcode(s), die Funktion für die Hexcodes habe ich bereits fertig - und dies natürlich möglichst schnell und effektiv.

Idee 1: Ich öffne die Datei mit FileOpen, dann wird per FileSeek mit Schrittweite 1 durch eine Schleife iteriert, bis das erste Zeichen des gesuchten String gefunden wird. Absprung zu einer Anaylse funktion, die dann Schritt für Schritt alle weiteren Zeichen einliest, ob dies der String ist. Wenn ja, Resultat = true, wenn nein, wieder in die Schleife. Das ganze bis der String gefunden wurde oder das letzte Zeichen der Datei gelesen wurde.
Ich finde das dies zwar eine Lösung darstellt, diese aber nicht besonders "schön" oder effektiv ist, da es, IMHO, zuviel Rechenleistung verbrauchen würde.

Idee 2: Ich lade die Datei in einen String und durchsuche diesen. Allerdings dürfte bei GB Dateien ziemlich schnell eine Speicherüberlauf aufkommen.

Idee 3: Eure Idee!?

Würde mich freuen, wenn ihr eure Ideen präsentieren würdet. Wie gesagt, ich brauche gar keinen fertigen Code, nur die "richtige" Idee will sich derzeit bei mir einfach nicht einstellen.

Danke im vorraus...

[Jelen]

Mein Vorschlag:
Datei "Häppchenweise" per blockread in einen Puffer laden, den Puffer (Variante) als string ansprechen und mit pos() nach dem ersten Zeichen suchen.
Wenn 1. Zeichen gefunden, weiter wie in Idee 1.
Das sollte einigermaßen schnell gehen.
Problematisch wird's natürlich, wenn ausgerechnet das 1. gesuchte Zeichen ständig in der Datei auftritt...

[himitsu]

eventuell auch 'ne alte Spielerei von mir > TPartialTextfile
ok, für Binärdaten nicht wirklich geeignet

MMF's (Memory Mapped Files) wären auch noch eine Alternative
da kann man zwar auch nur soviel ams Stück laden, wie man freien und zusammen hängenden Platz in seinem virtuellen Speicherbereich hat ... aber es belegt kaum reellen RAM (abgesehn von den Teilen welche Windows grad in der File Cache drin hat)

Das alte AssignFile, Reset und BlockRead ginge ebenfalls
und TFileStream gibt es auch noch.



* x Bytes in einen Puffer(String) laden
1:
* Zeichenfolge suchen > Pos(SuchString, Puffer)
* x Bytes - Length(Suchdaten) am Anfang löschen > [Delete(Puffer, 1, x - Length(SuchDaten) + 1)
* neuen Teil laden und an und an den vorher übriggebliebenen PufferAnteil anhängen
* weiter zu 1

[Techcrawler]

Ich hab nun mal folgende Idee gehabt:

Ich lese einen Block von 256 Zeichen aus. Ist die gesuchte Zeichenkette drin -> bingo, wenn nicht, gehe ich mit FileSeek die Anzahl von Zeichen zurück, die der längsten Zeichenkette entsprechen, die ich suche. Damit sollte ich den Fall kompensieren können, der auftritt, wenn die ZK grade nur zum Teil im ausgelesenen Puffer liegt. Das ganze bis zum Dateiende.
Theoretisch sollte das doch gehen, oder?

Dummerweise funktioniert es nicht, warum auch immer, hier mal mein Code dazu:

Delphi-Quellcode:

function TForm2.HexcodeInFile(HexCodeList: array of string): boolean;
var
    bufferBig:          array [0..255] of char;
    sHexBigBuffer,
    sTmpBuffer:         string;
    iHexListCounter,
    iFileSeekResult,
    iFileReadResult,
    iMaxHexCode,
    i:                  integer;
begin

    Result          := false;
    Label4.Caption  := '';
    iMaxHexCode     := 0;

    for i := 0 to Length(HexCodeList) - 1 do
    begin
        if Length(HexCodeList[i]) > iMaxHexCode then
            iMaxHexCode := Length(HexCodeList[i]);
    end;

    iFileSeekResult := FileSeek(hFileHandle,0,0);
    while not iFileSeekResult < 0 do
    begin

        iFileReadResult := FileRead(hFileHandle,bufferBig,256);
        sHexBigBuffer   := ParseHex(bufferBig);

        for iHexListCounter := 0 to Length(HexCodeList) - 1 do
        begin

            sTmpBuffer := HexCodeList[iHexListCounter];

            if not (StrPos(PChar(sHexBigBuffer),PChar(sTmpBuffer)) = nil) then
            begin
                Result := true;
                Exit;
            end;

        end;

        if iFileReadResult < 256 then
            Exit;

        iFileSeekResult := FileSeek(hFileHandle,-iMaxHexCode-1,1);
        Label4.Caption  := IntToStr(iFileSeekResult);
        Application.ProcessMessages;
                    
    end;
   
end;

ParseHex ist eine Funktion, die mit Zeichen für Zeichen eines Strings in den entsprechenden HexCode verwandelt. Die Labels sind nur für mich zur Anzeige gedacht, die Datei wird vor dem Funktionsaufruf mit FileOpen geöffnet und dannach wieder per FileClose geschlossen, hFileHandle ist dazu das entsprechende Handle auf die Datei.

Ich gebe nun also eine Datei hinein, von der ich ganz genau weiß, dass diese das gesuchte enthält. Allerdings erhalte ich immer ein Result false zurück.

Ich frage mich nun, warum nur?

[himitsu]

hmmm , komm in HexCodeList z.B. die #0 als Zeichen vor?
bzw, wie sieht denn der Inhalt von HexCodeList aus?
[add]achsi, du wandelst die eingelesenen Daten in einen HexString um ... da mußt du aber aufpassen, daß die Suchposition auch der Startposition einen Zeichens entspricht

Daten 12AB
Suchwort 2A
wäre ja sint enthalten, aber nicht nicht in der Datei drin
[/add]


deine PChar-Functionen brechen dort ab.

Den vohin oben nacheditieren Vorschlag:
(zwar jetzt nur für einen String, aber das sollte sich ändern lassen ... und beim Löschen des Puffers den die Länge des längsten String verwenden)

Delphi-Quellcode:

Const BufferSize = 65536;

Var F: TFileStream;
  P, L: Int64;
  Buffer: AnsiString;
  i: Integer;

Begin
  F := TFileStream.Create(FileName, fmOpenRead);
  L := F.Size;
  Buffer := '';
  While P + Length(Buffer) < L do Begin
    i := Length(Buffer);
    SetLength(Buffer, i + BufferSize);
    SetLength(Buffer, i + F.Read(Buffer[i + 1], BufferSize));
    If Pos(SerarchData, Buffer) > 0 Then
      Found;
    Delete(Buffer, 1, Length(Buffer) - Length(SearchData) + 1);
  End;
  F.Free;
End;

[SirThornberry]

Ich würde das ganze von der Datei entkoppeln. Also einfach eine Funktion von der du Zeichen für Zeichen abfragst und diese Funktion kümmert sich darum die Datei in großen Stücken zu lesen. Wenn du also dann von der Funktion ein Zeichen abfragst welches nicht mehr im Buffer ist lädt sie nach. Dann bist du auch flexibel wenn es von einer lokalen Datei irgendwann über geht zu einer Datei die im www liegt etc.

[Techcrawler]

Zitat von himitsu:

hmmm , komm in HexCodeList z.B. die #0 als Zeichen vor?

Danke für den Tipp, hab da mal gedebugged und siehe da, Steuerzeichen werden von dem Parser nicht übersetzt.
Da lag auch der Fehler, da der HexString also unvollständig war (es fehlten die Steuerzeichen in der Mitte).

Jetzt suche ich natürlich einen Weg, meine 'ParseHex' Funktion entsprechend aufzubohren.
Ganz 'Quick & Dirty' natürlich mit if...then, aber das ist ja nur eine Notlösung.
Wie werte ich die Steuerzeichen nun mit aus?
Anbei mal meine Funktion (nicht meckern, quick´n´dirty eben).

StrToHex übersetzt die Zeichen, aber eben keine Steuerzeichen

Delphi-Quellcode:

function TForm2.ParseHex(SourceBuffer: array of Char): String;
var
    i: Integer;
    StringBuffer: string;
begin
    StringBuffer := '';
    for i := 0 to Length(SourceBuffer)-1 do
    begin

        if SourceBuffer[i] = #17 then
            StringBuffer := StringBuffer + '11'
        else if SourceBuffer[i] = #0 then
            StringBuffer := StringBuffer + '00'
        else if SourceBuffer[i] = #1 then
            StringBuffer := StringBuffer + '01'
        else if SourceBuffer[i] = #2 then
            StringBuffer := StringBuffer + '02'
        else if SourceBuffer[i] = #3 then
            StringBuffer := StringBuffer + '03'
        else if SourceBuffer[i] = #4 then
            StringBuffer := StringBuffer + '04'
        else if SourceBuffer[i] = #5 then
            StringBuffer := StringBuffer + '05'
        else if SourceBuffer[i] = #6 then
            StringBuffer := StringBuffer + '06'
        else if SourceBuffer[i] = #7 then
            StringBuffer := StringBuffer + '07'
        else if SourceBuffer[i] = #8 then
            StringBuffer := StringBuffer + '08'
        else if SourceBuffer[i] = #9 then
            StringBuffer := StringBuffer + '09'
        else if SourceBuffer[i] = #10 then
            StringBuffer := StringBuffer + '0A'
        else if SourceBuffer[i] = #11 then
            StringBuffer := StringBuffer + '0B'
        else if SourceBuffer[i] = #12 then
            StringBuffer := StringBuffer + '0C'
        else if SourceBuffer[i] = #13 then
            StringBuffer := StringBuffer + '0D'
        else if SourceBuffer[i] = #14 then
            StringBuffer := StringBuffer + '0E'
        else if SourceBuffer[i] = #15 then
            StringBuffer := StringBuffer + '0F'
        else if SourceBuffer[i] = #16 then
            StringBuffer := StringBuffer + '10'
        else if SourceBuffer[i] = #26 then
            StringBuffer := StringBuffer + '1A'
        else if SourceBuffer[i] = #32 then
            StringBuffer := StringBuffer + '20'

        else
            StringBuffer := StringBuffer + StrToHex(SourceBuffer[i]);
    end;
    Result := StringBuffer;
end;

[himitsu]

StrToHex sollte doch eigentlich alle Zeichen behandeln?
ist ja schließlich ein Vorteil der Delphistrings (mit Längenangabe)

Aber an deiner stelle würde ich das ganz anders angehen.
Wandle deine HexStrings am Anfang in Binärfolgen um und suche diese direkt ... so brauchst du nicht die ganze rießige Datei umzuwandeln, sondern nur die kleinen SuchStrings

mal schnell umgebaut:

Delphi-Quellcode:

Function HexcodeInFile(Const FileName: String; Const HexCodeList: Array of String): Boolean;
  Const BufferSize = 65536;

  Var Data: Array of String;
    F: TFileStream;
    L: Int64;
    Buffer: AnsiString;
    i, MaxDataSize: Integer;

  Begin
    Result := False;
    MaxDataSize := 0;
    SetLength(Data, Length(HexCodeList));
    For i := 0 to High(HexCodeList) do Begin
      SetLength(Data[i], Length(HexCodeList[i]) div 2);
      HexToBin(PChar(HexCodeList[i]), PChar(Data[i]), Length(Data[i]));
      If Length(Data[i]) > MaxDataSize Then MaxDataSize := Length(Data[i]);
    End;
    F := TFileStream.Create(FileName, fmOpenRead or fmShareDenyWrite);
    Try
      L := F.Size;
      Buffer := '';
      While F.Position + Length(Buffer) < L do Begin
        i := Length(Buffer);
        SetLength(Buffer, i + BufferSize);
        SetLength(Buffer, i + F.Read(Buffer[i + 1], BufferSize));
        For i := 0 to High(Data) do
          If Pos(Data[i], Buffer) > 0 Then Begin
            Result := True;
            Break;
          End;
        Delete(Buffer, 1, Length(Buffer) - MaxDataSize);
      End;
    Finally
      F.Free;
    End;
  End;

[Techcrawler]

Zitat von himitsu:

StrToHex sollte doch eigentlich alle Zeichen behandeln?
ist ja schließlich ein Vorteil der Delphistrings (mit Längenangabe)

Hatte ich auch gedacht, doch bei den Steuerzeichen macht die Funktion schlapp

Zitat von himitsu:

Aber an deiner stelle würde ich das ganz anders angehen.
Wandle deine HexStrings am Anfang in Binärfolgen um und schuche diese direkt ... so brauchst du nicht die ganze rießige Datei umzuwandeln, sondern nur die kleinen SuchStrings

Nicht nötig, denke ich. Ich habe eben eine 200MB große Datei durchsucht, ob dort 3 HexCodes auftauchen, es hat ganze 12 sekunden gedauert. Ich denke, dass ist völlig ausreichend, vor allem, weil ein voller Datei-Scan bei meinem Tool nur in knapp 25% aller Fälle auftritt und selbst dann ist es selten, dass es eine Datei mit mehr als 20 MB sein wird.
Mir reicht das nun erstmal, nur die Steuerzeichen will ich noch umgewandelt wissen, dann kann ich das Tool beruhigt fertigstellen

[himitsu]

nja, probier den Unterschied mal bei den GB-Dateien

Wobei es hier kaum um die Belastung des Festplatte geht ... die wird wohl als größte Bremse des Ganzen auch den größten Einfluß haben, aber die CPU-Last wird so wohl ein bissl ansteigen (die muß ja mehr rechnen).

[info] siehe mein [Edit] von oben


PS: bei mir bekomm ich in 18s 1,2 GB durch (inklusive einer aufändigeren MD5-Berechnung über die ganze Datei ... siehe FileSplitter)