In Binärdatei suchen

[Ares]

Hallo!

Ich suche nach einer Möglichkeit wie ich in einer Binärdatei nach bestimmten Inhalten suchen kann. Die Suche sollte natürlich möglichst effizent sein.

Die Binärdatei wird mit einem TFileStream geöffent. Nun bräuchte ich eine Funktion die ein bestimmtes Bytemuster sucht, also z.B. Seek(myStream, 0x112233), und mir dann das Offset der Fundstelle mitteil... (Ich weiß, dass Seek nicht zum Suchen benutzt wird).

Gibt es solche eine Funktion oder muss man sich das selber basteln?

Besten Dank
Ares

[marabu]

Hallo,

für den Suchvorgang musst du die Daten vom externen Speicher in den Hauptspeicher laden - es führt kein Weg daran vorbei. Wie du dann weiter suchst ist eine Frage der Komplexität deiner Suche: einfaches oder reguläres Suchmuster? Pos() und Regex() helfen dir da weiter.

Grüße vom marabu

[r2c2]

Pos und Regex finktionieren doch aber nur mit Strings, oder?

==> Daten in TFileStream laden und Byteweise vergleichen...

mfg

Chtistian

[marabu]

Hallo Christian,

sowohl das Suchmuster, als auch der Datenstrom, lassen sich in Delphi als String betrachten. Das erspart die Implementierung einer speziellen Funktion, die lediglich die Signatur der Funktion Pos() anpassen würde - intern werden schon die vom Prozessor angebotenen Instruktionen für das register-gesteuerte Suchen eines Byte-/Wort-Wertes verwendet.

Freundliche Grüße

[Ares]

Es geht um teilweise sehr große Dateien in denen ich nach bestimmte (festen) Bytemustern suchen muss. Die Muster markieren Stellen an denen bestimmte Informationen zu finden sind. Die Muster sind immer gleich, reguläre Ausdrücke sind also nicht notwendig.

Zitat:

Pos und Regex finktionieren doch aber nur mit Strings, oder?

Ich meine auch, aber ich werde es nachher mal mit Streams versuchen.

Zitat:

==> Daten in TFileStream laden und Byteweise vergleichen...

Das ist natürlich die einfachste Möglichkeit aber wohl auch das uneffizenteste was es gibt. Wie gesagt sind die Dateien teilweise sehr groß. Daher sollte die Suche so effizient wie möglich sein, z.B. mit dem Knuth-Morris-Pratt Algrorithmus.

Gibt es hierfür bereits Funktionen die das können? Weiß jemand welche Algorithmen pos() verwendet? Ist das effizient?

Gruß
Ares

[Ares]

Zitat von marabu:

sowohl das Suchmuster, als auch der Datenstrom, lassen sich in Delphi als String betrachten. Das erspart die Implementierung einer speziellen Funktion, die lediglich die Signatur der Funktion Pos() anpassen würde - intern werden schon die vom Prozessor angebotenen Instruktionen für das register-gesteuerte Suchen eines Byte-/Wort-Wertes verwendet.

Mmh, das wäre natürlich eine Möglichkeit. Aber kann ich beliebt große Daten in einen String laden? Gibt es da keine Beschränkungen?

[r2c2]

@Marabu:
So weit so klar, aber gibt das nicht Probleme mit #0?
Oder is die CompilerMagic da wieder so schlau, dass die sich nicht dran stört? Ich meine mich dran erinner zu können, dass ich mal Probleme mit #0 hatte. Kann aber sein, dass das intern mit PChars zu tun hatte, und die kommen ja mit Sicherheit nicht (ohne weiteres) mit #0 im String klar...

@Ares:

Zitat:

Das ist natürlich die einfachste Möglichkeit aber wohl auch das uneffizenteste was es gibt. Wie gesagt sind die Dateien teilweise sehr groß. Daher sollte die Suche so effizient wie möglich sein,

Pos macht intern auch nix anderes. Ohne alles zu vergleichen, kannst du nicht suchen. Klar, man kann sowas effizient und ineffizient programmieren, aber das Prinzip ist eigentlich immer das geleiche...

Zitat:

z.B. mit dem Knuth-Morris-Pratt Algrorithmus.

Kenn ich gar nicht... gleich mal nachgucken...

Zitat:

Mmh, das wäre natürlich eine Möglichkeit. Aber kann ich beliebt große Daten in einen String laden? Gibt es da keine Beschränkungen?

Beschränkung ist 2GB = ansprechbarer RAM in nem 32Bit-System(die anderen 2GB sind fürs OS)...

//Edit: grad gemerkt, dass es noch gar keine 325Bit-Systeme gibt...

mfg

Christian

[juergen]

@ Christian,
der Vollständigkeitshalber

Zitat:

Beschränkung ist 2GB = ansprechbarer RAM in nem 32Bit-System(die anderen 2GB sind fürs OS)...

Es gibt einen von MS dokumentierten Parameter für die Boot.ini -> /3GB
Das hebt die Beschränkung zumindest schonmal von 2 GB auf 3 GB, aber somit nur noch 1 GB für das OS.
Manchmal kann das hilfreich sein...

[Ares]

Öhm, ich stehe gerade etwas auf dem Schlauch. Wie kann ich den Streaminhalt in einen String einlesen?

Mein erster Versuch tut es jedenfalls schon mal nicht

Delphi-Quellcode:

   stream := TFileStream.Create('MeineDatei.bin', fmOpenRead);
   stream.Read(test, 25);
   showMessage(test);

[marabu]

Die Funktion Pos() selbst wird durch einen null character im String nicht behindert:

Delphi-Quellcode:

var
  s: String;
  i: Integer;
begin
  s := '01234'#0'56789';
  ShowMessage(IntToStr(Pos('6', s))); // liefert 8
end;

Ich sage ja auch nicht, dass hier eine Stringverarbeitung vorliegt, sondern dass man durch geschicktes Agieren bestehende Funktionalität für lau nutzen kann.

Pos() implementiert den brute force Ansatz, wenn ich richtig informiert bin. Was die Suchalgorithmen angeht, so hängt sehr viel von der Länge des (einfachen) Suchmusters (synonym für substring) ab. Für kleine Zeichenketten bis zur Länge drei ist der brute force Algorithmus optimal, für größere hat sich in der Fachwelt bis dato (1994) Boyer-Moore-Horspool durchgesetzt.

Die Aussage "das Prinzip ist immer das gleiche" ist so alleine nicht richtig. Komplexe Suchverfahren bedienen sich bei ihren elementaren Schritten natürlich auch des Byte-Vergleichs, aber anstelle des simplen loop-and-compare werden da für den Laien erstaunliche Eigenschaften des Suchstrings analysiert und nutzbar gemacht.

Das Buch String Searching Algorithms von Graham A. Stephen vermittelt einen recht guten und kompakten Überblick über die Materie.

Freundliche Grüße


Einlesen in einen String-Buffer:

Delphi-Quellcode:

const
  BUFSIZE = 64 shl 10;
var
  buffer: String;
  s: Stream;
  chunk: Integer;
begin
  // ...
  chunk := Max(BUFSIZE, s.Size - s.Position);
  if chunk < Length(buffer) 
    then SetLength(buffer, chunk)
    else SetLength(buffer, BUFSIZE);
  s.Read(s[1], chunk);
  // ...
end;

Getippt und nicht getestet