Binäre (Hex) Suche

[Alter Mann]

Hallo,

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

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á array of byte oder 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
[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.

Doch leider nicht so das Richtige.
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.).
Werde mal die Fragen aufteilen, vielleicht findet sich ja die Lösung auf eine andere Art.

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 von Alter Mann:

...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.).

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, 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