Binäre (Hex) Suche

[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