Binäre (Hex) Suche

[Alter Mann]

Hallo,

ich brauche mal jemanden der mir auf die Sprünge hilft:wink:.

Ich möchte eine binäre Datei nach einer speziellen Bytefolge durchsuchen und das mit höchst
möglicher Geschwindigkeit. Die zu durchsuchenden Dateien können bis zu 4 TB Groß sein.
Ich habe schon die Suche genötigt und mir heute fast alle Treffer durch gelesen, es war nur
nichts gescheites dabei. Das lag aber wohl nur daran, dass entweder Strings, Records oder einzelne
Bytes gesucht wurden.
Ich möchte nach bytefolgen alá

Delphi-Quellcode:

array of byte

oder

Delphi-Quellcode:

array[0..19] of byte

suchen.
Eine Anpassung der JsTextSearch.pas von Jens Schumann an das Vorhaben
brachte leider nicht den gewünschten Erfolg. Das Verfahren kommt bei bestimmten bytefolgen

Delphi-Quellcode:

[1B58323232AAEF..]

in einen loop bzw. dauert bei einer 512MB-Datei 1.13sec.

Wer also eine Idee hat, her damit.

Vielen Dank

[jfheins]

Binäre Suche kannste knicken wenn deine Daten nicht sortiert sind.

Bleiben noch Suchalgorithmen wie z.B. http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus
Falls du keine fertige Implementierung findest, musst du ihn wohl selbst implementieren.

Ach ja, und natürlich eine anständige Puffergröße verwenden. 4kB Mindestens.

[Furtbichler]

Boyer moore bietet sich hier an: Hier mal eine Delphi-Implementierung

http://www.delphigeist.com/2010/04/b...lphi-2010.html

Wie lang ist denn die zu suchende Bytefolge?

[p80286]

Such mal hier nach Boyer Moore, da gab es for ein paar Jahren eine Diskussion über die effizentest weiterentwicklung.

Gruß
K-H

[Furtbichler]

Welcher Algorithmus (BM, BM-Horspool, KMP, Quicksearch) der beste ist, kann pauschal nicht beantwortet werden, sondern ist vielmehr abhängig von der Alphabetgröße (hier: 256 Zeichen) und vor allen Dingen von der Länge des zu suchenden Teilstückes.

BM und Derivate spielt seine Stärken bei langen Substrings und großen Alphabeten aus.

[Alter Mann]

Wie immer,

schnell und zuverlässig:thumb:.

Doch leider nicht so das Richtige:wink:.
Die JsTextSearch.pas von Jens ist eine Implementierung von Boyer Moore, habe
sie an Byte angepasst, läuft auch, aber kommt unter Umständen in einen Loop und es dauert:(.
Mit Strings ist sie Super schnell(512MB in 3sec.):thumb:.
Werde mal die Fragen aufteilen, vielleicht findet sich ja die Lösung auf eine andere Art:wink:.

Danke an Alle und ein schönes Wochenende.

[Aphton]

Ich habe die BM-Suche implementiert und bei dieser Datei (genauer hier, vorgestellt von SemperVideo) eine Suche gestartet.
Weiters habe ich das ganze per FileMapping gelöst - damit das System per Paging & Optimierungen (und was halt sonst noch so dazu gehört) da mitmischen kann.

Die Datei ist 15.696.118.781 bytes groß (14.6 GB).
Ich habe nach den letzten 7 Stellen gesucht. Das ganze hat im Schnitt um die 169 Sekunden gedauert. Dh 14.6 GB in 169 Sekunden (169136 ms) mit 7 Zeichen durchsucht.

Das wären dann 92801761 Bytes/Sek.

Im Vergleich zu deinen 512mb in 1.13 sec:
Ich habe mir 20 Bytes genau bei 512 rausgesucht und danach suchen lassen (gleiche Situation/Verhältnisse).
Die Suche hat im Schnitt 900 ms gedauert.

Falls Interesse besteht, kann ich die kleine Demo ja hochladen!

[Furtbichler]

Vorsicht, werden hier vielleicht Äpfel mit Birnen verglichen? Also vielmehr: IO vs. Cache?

Bei Dateien dieser Größe kommt es imho in erster Linie auf die Art des Einlesens an. Hier hat Sebastian Jänicke eine Textreader-Klasse mit Memory mapped files implementiert, die nach seinen Aussagen das schnellste ist, was es diesbezüglich gibt.

Ich kann mir vorstellen, das man seine Klasse auf Bytestreams anpassen kann.

Zitat:

Zitat von Alter Mann (Beitrag 1207623)

...habe sie an Byte angepasst, läuft auch, aber kommt unter Umständen in einen Loop und es dauert:(.
Mit Strings ist sie Super schnell(512MB in 3sec.):thumb:.

Zeig mal den Code, denn ein String ist ja nichts anderes als ein Bytestream (wenn man unicode mal außen vor lässt).

[MeierZwoo]

Ich benutze bei solchen Aufgaben einfach einlesen in einen String und dann die String-Function pos.

Wenn das Einzulesende (die Datei) > 4GB ist, dann über einen Schiebepuffer.

Über die Zeit habe ich mir noch keine Gedanken gemacht, weil, wenn es bei (realisierte Anwendung) 1600 Dateien unter 1 sec ist, mache ich mir keinerlei Gedanken mehr in Punkto Optimierung.

[Alter Mann]

Moin, Moin,

da es mit Boyer Moore nicht geht:pale:, hier der Code:

Delphi-Quellcode:

unit uHexSearch;

interface

uses
  SysUtils, Classes;

type
  THexSearchFoundEvent  = procedure(Sender     : TObject;
                                    Position   : Integer;
                                    var Cancel : Boolean) of object;

  THexSearchSkipTable   = Array[0..255] of Byte;

  PHexByteArray         = ^THexByteArray;
  THexByteArray         = Array of Byte;

  THexSearch            = class(TComponent)
  private
    FBytes              : THexByteArray;
    FCanCancel          : Boolean;
    FSkipTable          : THexSearchSkipTable;
    FStream             : TStream;
    FOnFound            : THexSearchFoundEvent;
    procedure InitSkipTable(var SkipTable : THexSearchSkipTable;
                            const aBytes  : THexByteArray);
    procedure Search(aStream      : TStream;
                     SkipTable    : THexSearchSkipTable;
                     const aBytes : THexByteArray);
    function  GetArrayOfByte(Source  : Array of Byte;
                             Index, Count : Integer) : THexByteArray;
    function  EqualBytes(Source, Dest : Array of Byte) : Boolean;
  protected
    procedure DoFound(Position : Integer; var Cancel : Boolean); virtual;
  public
    procedure Execute;

    property Cancel      : Boolean        read FCanCancel write FCanCancel;
    property Stream      : TStream        read FStream    write FStream;
    property SearchBytes : THexByteArray  read FBytes     write FBytes;
  published
    property OnFound : THexSearchFoundEvent read FOnFound write FOnFound;
  end;

implementation


const
  iBufferSize = 4096;

procedure THexSearch.DoFound(Position : Integer; var Cancel : Boolean);
begin
  If Assigned(FOnFound) then FOnFound(Self,Position, Cancel);
end;

procedure THexSearch.Execute;
begin
  InitSkipTable(FSkipTable, FBytes);
  Search(FStream, FSkipTable, FBytes);
end;

procedure THexSearch.InitSkipTable(var SkipTable : THexSearchSkipTable;
                                   const aBytes  : THexByteArray);
var
  I : Integer;
  L : Integer;
begin
  L := Length(aBytes);
  FillChar(SkipTable,SizeOf(THexSearchSkipTable), L);
  for I := 0 to L do
    SkipTable[aBytes[I]]:= L - I;
end;

procedure THexSearch.Search(aStream      : TStream;
                            SkipTable    : THexSearchSkipTable;
                            const aBytes : THexByteArray);
var
  ReadLen         : Integer;
  TextLen         : Integer;
  SourcePos       : Integer;
  SubStrPos       : Integer;
  aBuffer         : Array[1..iBufferSize] of Byte;
  ReadBufferCount : Integer;
  A               : Integer;
begin
  FCanCancel      := false;
  ReadBufferCount := 0;
  TextLen         := Length(aBytes);
  ReadLen         := 0;
  aStream.Seek(0, soFromBeginning);
  While aStream.Position<aStream.Size do
    begin
    A := 0;
    SourcePos := TextLen;
    ReadLen := aStream.Read(aBuffer, SizeOf(aBuffer));
    Repeat
      SubStrPos := TextLen;
      Repeat
        If aBuffer[SourcePos]= aBytes[SubStrPos] then
          begin
          Dec(SourcePos);
          Dec(SubStrPos);
          end
          else
          begin
            If SkipTable[aBytes[SubStrPos]]>SkipTable[aBuffer[SourcePos]] then
              SourcePos := SourcePos + TextLen
            else
              SourcePos := SourcePos  +SkipTable[aBuffer[SourcePos]];
            If SourcePos>ReadLen then
            begin
              SourcePos := ReadLen;
              Inc(A);
            end;
            SubStrPos := TextLen;
          end;
      Until (SubStrPos=0) or (SourcePos>ReadLen) or (A=2);
      If SubStrPos = 0 then // Text gefunden
      begin
        DoFound(ReadBufferCount*SizeOf(aBuffer)+SourcePos-ReadBufferCount*TextLen, FCanCancel);
        SourcePos := SourcePos + 2 * TextLen;
      end;
      If FCanCancel then  Exit;
    Until (SourcePos>ReadLen) or (A=2); // Block ist abgearbeitet
    Inc(ReadBufferCount);

    If (EqualBytes(GetArrayOfByte(aBuffer, ReadLen-TextLen+1, TextLen), aBytes)) and
       (Stream.Position < Stream.Size) then
      aStream.Seek(-(TextLen),soFromCurrent);
    end;
end;

function  THexSearch.GetArrayOfByte(Source  : Array of Byte;
                                    Index, Count : Integer) : THexByteArray;
var
  I : Integer;
begin
  SetLength(Result, Count);
  for I := 0 to Count do
    Result[I] := Source[Index + I];
end;


function  THexSearch.EqualBytes(Source, Dest : Array of Byte) : Boolean;
var
  SA, DA : String;
  I      : Integer;
begin
  SA := '';
  DA := '';
  for I := 0 to Length(Source) do SA := SA + IntToHex(Source[I], 2);
  for I := 0 to Length(Dest)   do DA := DA + IntToHex(Dest[I], 2);
  Result := CompareText(SA, DA) = 0;
end;

end.

Das Problem wird jedem Klar wenn nach folgender bytefolge gesucht wird:

Code:

DA010000DE010000E2010000E6010000

Den daraus wird

Code:

(218, 1, 0, 0, 222, 1, 0, 0, 226, 1, 0, 0, 230, 1, 0, 0)

und da in der Skiptable für jeden Wert die Schiebeposition vermerkt wird, werden
die Positionen für den Wert 0 immer überschrieben.


Schönes Wochenende

[lbccaleb]

Zitat:

Zitat von Aphton (Beitrag 1207627)

... Falls Interesse besteht, kann ich die kleine Demo ja hochladen!

Also ich würd mal Intresse anmelden :)

[Alter Mann]

Hi,

ich habe ein halbwegs brauchbares Ergebnis. Die Frage ist nun: geht das auch schneller?

Delphi-Quellcode:

unit uHexSearch;

interface

uses
  SysUtils, Classes;

type
  THexSearchFoundEvent  = procedure(Sender     : TObject;
                                    Position   : Integer;
                                    var Cancel : Boolean) of object;
  THexSearchProgressEvent = procedure(Sender   : TObject;
                                      Position : WORD;
                                      Max      : Int64) of Object;

  THexByteArray         = Array of Byte;

  TFiFoByteBuffer       = class(TObject)
  private
    FBuffer             : THexByteArray;
    FCount              : Int64;
    function    GetHasData : Boolean;
    function    GetByteStr : String;
  public
    constructor Create(aSize : Integer);
    procedure   Add(Value : Byte);
    property    HasData : Boolean read GetHasData;
    property    ByteStr : String  read GetByteStr;
  end;

  THexSearch            = class(TComponent)
  private
    FBytes              : String;
    FBuffer             : TFiFoByteBuffer;
    FCanCancel          : Boolean;
    FStream             : TStream;
    FSearchTime         : TDateTime;
    FOnFound            : THexSearchFoundEvent;
    FOnProgress         : THexSearchProgressEvent;
    procedure Search(aStream      : TStream;
                     const aBytes : String);
    function  EqualBytes(aSource, aSearchStr : String) : Boolean;
  protected
    procedure DoFound(Position : Integer; var Cancel : Boolean); virtual;
    procedure DoProgress(Position : WORD; Max : Int64); virtual;
  public
    procedure Execute;

    property Cancel      : Boolean    read FCanCancel write FCanCancel;
    property Stream      : TStream    read FStream    write FStream;
    property SearchBytes : string     read FBytes     write FBytes;
    property SearchTime  : TDateTime  read FSearchTime;
  published
    property OnFound     : THexSearchFoundEvent    read FOnFound    write FOnFound;
    property OnProgress  : THexSearchProgressEvent read FOnProgress write FOnProgress;
  end;

implementation

constructor TFiFoByteBuffer.Create(aSize : Integer);
begin
  SetLength(FBuffer, aSize);
  FCount := 0;
end;

procedure   TFiFoByteBuffer.Add(Value : Byte);
var
  I : WORD;
begin
  for I := Low(FBuffer) to High(FBuffer) -1 do
   FBuffer[I] := FBuffer[I+1];
  FBuffer[High(FBuffer)] := Value;
  Inc(FCount);
end;

function    TFiFoByteBuffer.GetHasData : Boolean;
begin
  Result := FCount >= Length(FBuffer);
end;

function    TFiFoByteBuffer.GetByteStr : String;
var
  I  : Integer;
begin
  Result := '';
  for I := 0 to Length(FBuffer)-1 do Result := Result + IntToHex(FBuffer[I], 2);
end;

procedure THexSearch.DoFound(Position : Integer; var Cancel : Boolean);
begin
  If Assigned(FOnFound) then FOnFound(Self,Position, Cancel);
end;

procedure THexSearch.DoProgress(Position : WORD; Max : Int64);
begin
  If Assigned(FOnProgress) then FOnProgress(Self,Position, Max);
end;

procedure THexSearch.Execute;
begin
  FSearchTime := Now;
  Search(FStream, FBytes);
  FSearchTime := Now - FSearchTime;
end;

procedure THexSearch.Search(aStream      : TStream;
                            const aBytes : String);
var
  Buffer      : Byte;
  FileSize    : Int64;
begin
  FCanCancel  := false;
  FileSize    := aStream.Size;
  FBuffer     := TFiFoByteBuffer.Create(Length(aBytes) div 2);
  try
  aStream.Seek(0, soFromBeginning);
    While (aStream.Position < aStream.Size) do
    begin
      aStream.Read(Buffer, SizeOf(Buffer));
      FBuffer.Add(Buffer);
      DoProgress(aStream.Position, FileSize);
      if FBuffer.HasData then
        if EqualBytes(FBuffer.ByteStr, aBytes) then
          DoFound(aStream.Position, FCanCancel);
      if FCanCancel then Break;
    end;
  finally
    FBuffer.Free;
  end;
end;

function  THexSearch.EqualBytes(aSource, aSearchStr : String) : Boolean;
begin
  Result := CompareText(aSource, aSearchStr) = 0;
end;

end.

Das durchsuchen einer 5GB dauert 0.328 sec, bzw. nach dieser Zeit ist die
Bytefolge gefunden worden.

VG

[Aphton]

Zitat:

Zitat von Alter Mann (Beitrag 1207691)

Das durchsuchen einer 5GB dauert 0.328 sec, bzw. nach dieser Zeit ist die
Bytefolge gefunden worden.

VG

Das sagt nicht viel aus. Wichtig ist, an welcher Stelle sie gefunden wird. Dann kann man nämlich sagen, wie viele Bytes pro Zeiteinheit du damit durchkämmen kannst!

Die Geschwindigkeit dürfte übringens auch von Festplatte zu Festplatte verschieden sein. Eig. kann man nur lokal bzw. angewandt auf derselben HD Vergleiche aufstellen!

Achja - ich weiß nicht, ob man da noch was rausholen kann oder ob das eig. Unfug ist - so wie ich mit CreateFileMapping() umgegangen bin. Ich erfreue mich jedoch über Belehrung!

Edit: Ich wende mal deinen Algorithmus an, mal sehen, wenn er schneller ist, brauchste die Demo erst gar nicht runterzuladen!

Edit2: Dein Algorithmus läuft bei mir mit einer sehr geringen Geschwindigkeit. Für 1 mb habe ich 5 Sek. gebraucht :(
Ich wende sie übrigens auf ein FileStream an (genauso wie ich es auch bei meinem getan habe).
Wie hast du die angegebene Zeit Zustande gebracht?